CMap#
- class discopy.cmap.CMap(dom, cod, boxes, edges, loops=(), *, check=True)[source]#
Bases:
CompactCategory,discopy.utils.Result,GenericAn open combinatorial map, i.e. a diagram represented as a bijection between its ports.
Contrary to the abstract definition, which has unstructured nodes arising from the given orientation permutation, we take DisCoPy boxes as nodes and derive a canonical clockwise port orientation on boxes: every box of arity \(m\) and coarity \(n\) maps to a \((m+n)\)-cycle in the generated permutation, consisting of contiguous port indices. Additionally, we allow two kinds of scalars:
scalar loops arising from composing cups and caps, parametrized by an atomic type;
scalar boxes, i.e. boxes with empty domain and codomain
As for the open structure, we represent the map boundary by a virtual apex node, whose signature is the dagger of the that of the overall map.
By default, CMap defines the free compact category over a set of boxes, but we also want to be able to encode weaker structure, disallowing cups and caps or even traced structure altogether. We therefore further distinguish port sides by assigning a negative polarity on domain ports and a positive polarity on codomain ports by equipping the map with a polarity assignment \(m : P \rightarrow \{-1, +1\}\).
Following
Hypergraph, the map is parametrised by a category. The functor used byfrom_diagram()is read fromcategory.functor_factory;Diagram.to_map()parameterisesCMapwith the concrete diagram category automatically. A map is always compact, whatever the category that hosts it, so that every compact operation is available when manipulating maps. It isto_diagram()that needs the structure ofcategory:cups and caps, i.e. same-polarity pairings \(e; m = m\) (see
is_monogamous), are made explicit bymake_monogamous(), which needs a category with cups and caps;traces, i.e. cycles and loops (see
is_acyclic), are made explicit bymake_causal(), which needs a traced category.
- Parameters:
dom (C0) – The domain of the map.
cod (C0) – The codomain of the map.
boxes (tuple[Box, ...]) – The boxes inside the map.
edges (Iterable[int]) – A fixpoint-free involution on ports.
loops (tuple[C0, ...]) – The types of closed wire components with no ports.
check (bool) – Whether to
validate()the involution and the wire types.
Example
>>> from discopy.compact import Ty, Box, CMap >>> from discopy.python.finset import Permutation >>> x, y, z = map(Ty, "xyz") >>> f, g = map(CMap.from_box, [ ... Box("f", x @ y, x @ z), ... Box("g", z @ z, z), ... ]) >>> cm = f @ z >> x @ g >>> # apex: 10 : x, 11 : z ⊢ 2 : x, 1 : y, 0 : z >>> # f: 3 : x, 4 : y ⊢ 6 : x, 5 : z >>> # g: 7 : z, 8 : z ⊢ 9 : z >>> cm.edges == Permutation.from_cycles([ ... (0, 3), (1, 4), (2, 8), (5, 7), (6, 10), (9, 11)], 12) True >>> cm.orientation == Permutation.from_cycles([ ... (2, 1, 0, 10, 11), (3, 4, 5, 6), (7, 8, 9)], 12) True >>> cm.draw( ... doctest="docs/_static/cmap/simple-cmap.dot", ... port_indices=True, ... show=False, ... )
Swaps affect the edge permutation but leave the vertex permutation fixed:
>>> f, g = map(CMap.from_box, [ ... Box("f", x @ y, z @ x), ... Box("g", z @ z, z), ... ]) >>> cm = (f >> CMap.swap(z, x)) @ z >> x @ g >>> cm.draw( ... doctest="docs/_static/cmap/swapped-cmap.dot", ... port_indices=True, ... show=False, ... )
- property n_ports: int#
The number of ports.
- property faces: Permutation#
The face permutation, computed as
edges ; orientation.
- property n_vertices: int#
The number of vertices, including the boundary apex if present.
- property n_edges: int#
The number of edges.
- property n_faces: int#
The number of faces, including closed scalar components.
- property euler_characteristic: int#
Euler characteristic
V - E + Fwith boundary at infinity.For maps with non-empty domain or codomain, the input and output ports are treated as one virtual boundary/apex, ordered clockwise as inputs left-to-right followed by outputs right-to-left. Fully closed maps have no boundary apex.
>>> from discopy.symmetric import Ty, Box, Swap >>> x, y, z = map(Ty, "xyz") >>> f = Box("f", x @ y, z) >>> f.to_map().euler_characteristic 2 >>> (Swap(y, x) >> f).to_map().euler_characteristic 0
- property is_scalar: bool#
Whether the map is a scalar, i.e. an endomorphism of the unit.
Scalars are the maps with no boundary, so they are closed under tensor:
>>> from discopy.compact import Ty, Box, CMap >>> x = Ty("x") >>> loop = CMap.caps(x.r, x) >> CMap.cups(x.r, x) >>> box = Box("s", Ty(), Ty()).to_map() >>> assert loop.is_scalar and box.is_scalar >>> assert (loop @ box).is_scalar >>> assert not CMap.id(x).is_scalar
- property genus: int#
The genus of a connected map, i.e. the number of handles of the smallest orientable surface it embeds in without crossings.
This is \((2 - \chi) / 2\) for the Euler characteristic \(\chi\) of
euler_characteristic, which it defers to and which raisesValueErroron a map that is not connected.A map with no vertex, i.e. a loop, has genus zero: a circle does embed in the sphere, but Euler’s formula only counts it once a vertex has subdivided it, which a loop by definition has not. This is the only degenerate case – a closed map is a scalar and has a genus like any other.
>>> from discopy.symmetric import Ty, Box, Swap >>> x, y, z = map(Ty, "xyz") >>> f = Box("f", x @ y, z) >>> f.to_map().genus 0 >>> (Swap(y, x) >> f).to_map().genus 1
- property is_planar: bool#
Whether the combinatorial map is planar, i.e. all of its components have
genuszero.
- property orientation: Permutation#
The closed orientation permutation.
The first cycle is the boundary apex, when the boundary is non-empty. Each following non-empty cycle is the contiguous port interval of a box in canonical order: domain ports, then codomain ports.
>>> from discopy.compact import Ty, Box, CMap >>> from discopy.python.finset import Permutation >>> x, y, z = map(Ty, "xyz") >>> f, g = Box('f', x @ y, x @ z), Box('g', z @ z, z) >>> cm = (f @ z >> x @ g).to_map() >>> assert cm.orientation == Permutation.from_cycles([ ... (2, 1, 0, 10, 11), # boundary ... (3, 4, 5, 6), # f ... (7, 8, 9), # g ... ], 12), f"got {cm.orientation.cycles()!r}"
- property boundary_cycle: tuple[int, ...]#
The clockwise cycle of the virtual boundary apex.
- property connected_components: list[CMap]#
The connected components, with the boundary component first.
- splice(edges, glue, ports)[source]#
Compute the edges and scalars created by a gluing operation.
- Parameters:
edges (Permutation)
glue (Permutation)
ports (list[Port])
- Return type:
tuple[Permutation, tuple]
- classmethod validate_wire(source, target)[source]#
Validate type compatibility for a wire between two ports.
- property is_monogamous: bool#
Checks monogamy, i.e. every wire connects a positive to a negative port, so that the map has no cups or caps. This is the analogue of
Hypergraph.is_monogamous, in which case the map lives in a traced category.>>> from discopy.compact import Ty, CMap >>> x = Ty("x") >>> assert CMap.id(x).is_monogamous >>> assert not CMap.cups(x, x.r).is_monogamous
- property box_edges: Iterable[tuple[int, int]]#
The directed wires from the codomain of a box to the domain of another, as pairs of source and target port indices.
- property box_ranks: tuple[int, ...] | None#
The rank of each box, i.e. the longest directed path of
box_edgesthat reaches it, orNoneif there is a cycle.
- property is_acyclic: bool#
Whether the directed wiring has no cycles or scalar loops, i.e. whether
box_edgesadmits a topological sort.>>> from discopy.compact import Ty, Box >>> x = Ty("x") >>> f = Box("f", x, x).to_map() >>> assert f.is_acyclic >>> assert not f.trace().is_acyclic
- property is_topologically_ordered: bool#
Whether every directed wire points forward in the box order, i.e. every wire from the codomain of a box to the domain of another goes to a box of greater
Port.depth.>>> from discopy.compact import Ty, Box >>> x = Ty("x") >>> f, g = Box("f", x, x), Box("g", x, x) >>> assert (f.to_map() >> g.to_map()).is_topologically_ordered >>> snakes = f.transpose(left=True) >> g.transpose(left=True) >>> assert not snakes.to_map().is_topologically_ordered
- reorder(order)[source]#
Relabel ports to put boxes in the given order.
- Parameters:
order (Iterable[int])
- Return type:
- topological_order()[source]#
Reorder the boxes so that every directed wire points forward.
This relabels the box order without touching the wiring. It is the identity on
is_causalmaps.- Raises:
AxiomError – If the map has a directed cycle, i.e. it is not
is_acyclic, so that no such order exists.- Return type:
>>> from discopy.compact import Ty, Box >>> x = Ty("x") >>> f, g = Box("f", x, x), Box("g", x, x) >>> snakes = (f.transpose(left=True) >> g.transpose(left=True)) >>> assert not snakes.to_map().is_topologically_ordered >>> assert snakes.to_map().topological_order().boxes == (g, f) >>> ordered = (f.to_map() >> g.to_map()) @ f.to_map() >>> assert ordered.topological_order() is ordered >>> f.to_map().trace().topological_order() Traceback (most recent call last): ... discopy.utils.AxiomError: ... has a directed cycle, ...
- property is_causal: bool#
Checks causality, i.e. the map is
is_monogamouswith no loops andis_topologically_ordered, which impliesis_acyclic. A causal map lives in a symmetric category, i.e. it can be drawn using only swaps.>>> from discopy.compact import Ty, Box, CMap >>> x = Ty("x") >>> f = Box("f", x, x).to_map() >>> assert (f >> f).is_causal >>> assert not f.trace().is_causal >>> assert not CMap.cups(x, x.r).is_causal
- classmethod id(dom=None)[source]#
The identity map, with each input wired to its output.
- Return type:
- classmethod from_glued(dom, cod, images)[source]#
Glue a sequence of maps onto a scan of open wires, in one pass.
Each wire of the result is a connected component of the wires of the
images, computed by union-find as they are glued. This is the colimit of the diagram of gluings, i.e. the same map as the iteratedthen()of theimageswhiskered at their offsets, but built once rather than rebuilt at every step.- Parameters:
- Return type:
>>> from discopy.compact import Ty, Box, CMap >>> x = Ty("x") >>> f, g = map(CMap.from_box, [Box("f", x, x), Box("g", x, x)]) >>> CMap.from_glued(x, x, [(f, 0), (g, 0)]) == f >> g True >>> CMap.from_glued(Ty(), Ty(), [ ... (CMap.caps(x.r, x), 0), (CMap.cups(x.r, x), 0)]).loops == (x, ) True
- classmethod from_diagram(old)[source]#
Turn a
Diagraminto aCMap.Structure available at the map’s categorical level becomes wiring; structure from the next level remains represented by boxes.
The image of each box is computed by the functor into
cls, then the images are glued in a single pass withfrom_glued().>>> from discopy.braided import Ty, Braid >>> from discopy.monoidal import CMap >>> x, y = map(Ty, "xy") >>> CMap.from_diagram(Braid(x, y)).boxes == (Braid(x, y),) True >>> from discopy.symmetric import Ty as STy, Swap >>> x, y = map(STy, "xy") >>> Swap(x, y).to_map().boxes ()
- classmethod ev(base, exponent, left=True)[source]#
Evaluation is kept as an explicit box by default, or comes from the wiring of cups when the host category is rigid.
- curry(n=1, left=True)[source]#
Currying is kept as an explicit curry box by default, the more rigorous representation, or comes from the wiring of caps when the host category is rigid.
- Parameters:
n (int) – The number of objects to curry.
left (bool) – Whether to curry on the left or right.
- Return type:
>>> from discopy.compact import Ty, Box >>> x, y, z = map(Ty, "xyz") >>> f = Box("f", x @ y, z).to_map() >>> assert f.curry(left=False).uncurry(left=False) == f >>> f.curry(left=False).draw( ... doctest="docs/_static/cmap/compact-curry.dot", show=False)
- base_and_exponent(n, left)[source]#
The base and exponent that
uncurry()evaluates, read off the codomain as in the host category.
- dagger()[source]#
Reverse a combinatorial map: swap the boundary, dagger each box in reverse order and conjugate the edges by the port relabeling.
Boundary ports keep their order while each box block is reversed: the clockwise port order of a daggered box is the reversed clockwise order of the original.
>>> from discopy.compact import Ty, Box >>> x, y = map(Ty, "xy") >>> f, g = Box('f', x, y @ y), Box('g', y @ y, x) >>> assert (f >> g).dagger().to_map() == (f >> g).to_map().dagger() >>> assert (f >> g).to_map().dagger().dagger() == (f >> g).to_map()
- Return type:
- classmethod spiders(n_legs_in, n_legs_out, typ, phases=None)[source]#
Spiders are kept as boxes, including their phase data.
Example
>>> from discopy.tensor import CMap, Dim, Tensor >>> assert CMap.spiders(1, 2, Dim(2, 3)).eval().is_close( ... Tensor.spiders(1, 2, Dim(2, 3)))
- then(other)[source]#
Compose maps by gluing output ports to input ports.
Closed components created by gluing are retained in
loops.>>> from discopy.compact import Ty, CMap >>> x = Ty("x") >>> scalar = CMap.caps(x.r, x) >> CMap.cups(x.r, x) >>> scalar.boxes () >>> scalar.loops == (x,) True
- trace(n=1, left=False)[source]#
Trace boundary wires by splicing the selected inputs and outputs.
- Parameters:
n (int) – The number of wires to trace.
left (bool) – Whether to trace the leftmost rather than rightmost wires.
- Return type:
- interchange(i, j)[source]#
Interchange boxes at indices
iandj.The edges permutation is relabeled so that ports follow the canonical order induced by the new box order. Unlike
Diagram.interchange(), the boxes need not commute: the result is the same map with its boxes out of order, whichtopological_order()can put back.>>> from discopy.compact import Ty, Box >>> x, y = map(Ty, "xy") >>> f, g = Box("f", x, x), Box("g", y, y) >>> cmap = f.to_map() @ g.to_map() >>> cmap.interchange(0, 1).boxes == (g, f) True >>> assert not (f.to_map() >> f.to_map()).interchange( ... 0, 1).is_topologically_ordered
- Parameters:
i (int)
j (int)
- Return type:
- plug_input(input_index, box, cod, root_index=0)[source]#
Plug an input boundary and the output root into a new box.
If
self : A @ x -> yandbox : y -> z @ x, thenself.plug_input(i, box, z)removes thei-th input, wires the old output to the domain ofbox, wires the removed input to the non-root output ofbox, and leavesroot_indexas the new root.The new box comes last but wires back to the domain of an earlier box, so this can introduce a cycle, which needs a traced category.
- explicit_trace(left=False)[source]#
The trace of a map with explicit boxes (trace, cup or cap).
- Parameters:
left (bool) – Whether to trace on the left or right.
- Return type:
Note
When
category.trace_factoryis a class, e.g. for symmetric diagrams, then the result is just one big trace box wrapped up as a map. Otherwise it is a class method, e.g. for compact diagrams, in which case we use it to introduce cup and cap boxes.
- make_monogamous()[source]#
Introduce cup and cap boxes to make self
is_monogamous, i.e. so that every wire connects a positive and a negative port.The boxes come from
category.cup_factoryandcategory.cap_factory, so this needs a rigid category.Example
>>> from discopy.compact import Ty, Cup, Cap, CMap >>> x = Ty("x") >>> assert CMap.cups(x, x.r).make_monogamous()\ ... == CMap.from_box(Cup(x, x.r)) >>> assert CMap.caps(x.r, x).make_monogamous()\ ... == CMap.from_box(Cap(x.r, x))
- Return type:
- make_causal()[source]#
Make self
is_causal, i.e. so that every wire points forward and there are no loops. Boxes that are merely out of order are put back in order withtopological_order(); only a wire that closes a cycle is cut into a trace, which needs a traced category.Example
>>> from discopy.traced import Ty, Box, Trace, CMap >>> f = Box("f", Ty("x"), Ty("x")) >>> assert f.to_map().trace().make_causal()\ ... == CMap.from_box(Trace(f))
- Return type:
- to_compact()[source]#
Open every curry bubble into its argument followed by the dagger of
ev(), traced over the curried wires: the map is decoded and the image of each box is glued back, likefrom_diagram().Example
>>> from discopy.closed import Ty, Box, CMap >>> x, y, z = map(Ty, "xyz") >>> f = Box("f", x @ y, z) >>> assert f.to_map().curry().to_compact()\ ... == (f.to_map() >> CMap.ev(z, y).dagger()).trace()
- Return type:
- eval(*args, **params)[source]#
Evaluate the map directly with the
evalof the host category, e.g. contract a tensor map in a singleeinsumcall, seediscopy.tensor.Diagram.eval().
- to_diagram()[source]#
Downgrade to a diagram directly, preserving box orientation.
This is where a map has to be a morphism of
category: its cups, caps and traces are made explicit withmake_monogamous()andmake_causal(), which raise unless the category is rigid resp. traced, then its boxes are put in the order in which they are applied withtopological_order().>>> from discopy.monoidal import Ty, Box, CMap >>> x = Ty("x") >>> f = Box("f", x, x) >>> CMap(Ty(), Ty(), (f, ), (1, 0)).to_diagram() Traceback (most recent call last): ... discopy.utils.AxiomError: monoidal.Diagram has no traces for the cycles of this map.
What remains is decoded like in
Hypergraph.to_diagram(): we scan the currently open wires from left to right, for each box we swap its domain wires to the front, apply the box, and replace the consumed domain labels by the box codomain labels.>>> from discopy.compact import Ty, Box, CMap >>> x, y = map(Ty, "xy") >>> cmap = Box("f", x, y).to_map() >>> cmap.to_diagram().to_map() == cmap True
- Return type:
- to_hypergraph()[source]#
Forget orientation and return the underlying bijective hypergraph given by the edge permutation. See documentation of :func:
Hypergraph.from_mapfor an example.
- to_dot(engine='dot', seed=None, graph_attr=None, port_indices=False)[source]#
Encode the combinatorial map as Graphviz DOT.
The drawing has HTML-table nodes for the boundary interfaces and for each box, with one table port for each object in the signature, and one direct edge per 2-cycle of
edges.- Parameters:
engine – The Graphviz layout engine.
seed – An optional Graphviz layout seed.
graph_attr – Additional graph attributes.
port_indices – Whether to display port indices.
- Return type:
str
>>> from discopy.compact import Ty, CMap >>> CMap.id(Ty("x")).to_dot().startswith("graph cmap") True
- draw(path=None, doctest=None, engine='dot', format=None, seed=None, show=None, graph_attr=None, port_indices=False, block=True, tol=20)[source]#
Draw as a combinatorial map using Graphviz.
This is intended for map-like pictures rather than the usual DisCoPy box-and-wire drawing.
If
pathends in.dotor.gv, write DOT source. Otherwise, render with Graphviz. Whenshowis true, display the rendered graph in a matplotlib window.- Parameters:
path – The output path, or
Noneto display the map.engine – The Graphviz layout engine.
format – The rendered format, inferred from
pathby default.seed – An optional Graphviz layout seed.
show – Whether to display the rendered image.
graph_attr – Additional Graphviz graph attributes.
port_indices – Whether to display port indices.
block – Whether displaying blocks execution.
Scalar loops are drawn as dots with a loop, but the combinatorial map structure does not let us retain inclusion of such loops:
>>> from discopy.compact import Ty, CMap >>> x, y, z = map(Ty, "xyz") >>> (CMap.caps((x @ y).r, x @ y) >> CMap.cups((x @ y).l, x @ y)).draw( ... doctest="docs/_static/cmap/scalar-loop.dot", show=False)