CMap

class discopy.cmap.CMap(dom, cod, boxes, edges, offsets=None, loops=())

Bases: CompactCategory, discopy.abc.Result, Generic

An 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\}\).

Four knobs are available to restrict the structure:

• require_planar: the port orientation give us a way to easily compute whether the map is planar by computing its component-wise Euler characteristic, i.e. disallow swaps;

• require_causal: checks that the edges are in causal order, i.e. they link positive ports to negative ports with higher rank, i.e. no traced wires;

• require_oriented: checks that we connect positive to negative wires, and disallow same-polarity pairings, i.e. we can enforce \(e; m = -m\) to disallow cups and caps;

• require_connected: ensures the map forms a single connected component

Note that require_causal implies require_oriented since cups and caps give rise to traced structure. We can therefore represent the categorical structures we can guarantee by the following diagram:

Note that combinatorial maps as such cannot faithfully represent free monoidal diagrams as there is no way to account for the nesting of connected components, hence the bottom-left corner rather corresponds to the free spacial category, i.e. diagrams where entire isolated components can go through wires at once without intermediate overlapping (see [Sel10]).

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.

• offsets (tuple[int | None, ...] | None) – Optional drawing offsets, preserved through conversion.

• loops (tuple[C0, ...]) – The types of closed wire components with no ports.

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(
...     path="docs/_static/cmap/simple-cmap.png",
...     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(
...     path="docs/_static/cmap/swapped-cmap.png",
...     port_indices=True,
...     show=False,
... )

property ports: list[Port]

The ports in canonical orientation order.

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 + F with 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 scalar, i.e. a single box with no ports, or a single scalar loop.

property is_planar: bool

Whether the combinatorial map is planar, i.e. all of its non-scalar components have an Euler characteristic of 2.

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.

validate()

Validate the edges involution, wires and required planarity.

property connected_components: list[CMap]

The connected components, with the boundary component first.

splice(edges, glue, ports)

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_equal_types(source, target)

Validate a wire between equal types.

Parameters:

• source (Port) –

• target (Port) –

classmethod validate_adjoint_types(source, target)

Validate a wire between adjoint types.

Parameters:

• source (Port) –

• target (Port) –

classmethod validate_wire(source, target)

Validate type compatibility for a wire between two ports.

Raises:

AxiomError – If the types or orientations are incompatible.

Parameters:

• source (Port) –

• target (Port) –

validate_forward_edges(ports)

Validate that box-to-box causal wires are acyclic.

Parameters:

ports (list[Port]) –

classmethod id(dom=None)

The identity map, with each input wired to its output.

Return type:

CMap

classmethod from_box(box)

Embed a box, wiring its boundary to fresh box ports.

Parameters:

box (Box) –

Return type:

CMap

classmethod from_diagram(old)

Turn a Diagram into a CMap.

Structure available at the map’s categorical level becomes wiring; structure from the next level remains represented by boxes.

>>> 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
()

Parameters:

old (Diagram) –

Return type:

CMap

classmethod swap(left, right)

The symmetry encoded as boundary wiring.

Parameters:

• left (Ty) –

• right (Ty) –

Return type:

CMap

classmethod cups(left, right)

A cup encoded as boundary wiring between adjoint types.

Parameters:

• left (Ty) –

• right (Ty) –

Return type:

CMap

classmethod caps(left, right)

A cap encoded as boundary wiring between adjoint types.

Parameters:

• left (Ty) –

• right (Ty) –

Return type:

CMap

classmethod copy(typ, n=2)

Copy is kept as a box: one input cannot wire to many outputs.

Parameters:

• typ (Ty) –

• n (int) –

Return type:

CMap

classmethod merge(typ, n=2)

Merge is kept as a box: many inputs cannot wire to one output.

Parameters:

• typ (Ty) –

• n (int) –

Return type:

CMap

classmethod discard(typ)

Discard is kept as a box.

Parameters:

typ (Ty) –

Return type:

CMap

classmethod ev(base, exponent, left=True)

Evaluation kept as a box.

Parameters:

• base (Ty) –

• exponent (Ty) –

• left (bool) –

Return type:

CMap

curry(n=1, left=False)

Curry a combinatorial map using compact wiring.

Note

This will use the free compact structure obtained from the map representation by introducing adjoint ports, even if the host category already has compact structure.

Parameters:

• n (int) – The number of objects to curry.

• left (bool) – Whether to curry on the left or right.

Return type:

CMap

>>> from discopy.compact import Ty, Box
>>> x, y, z = map(Ty, "xyz")
>>> f = Box("f", x @ y, z).to_map()
>>> assert f.curry().uncurry() == f
>>> f.curry().draw(
...     path="docs/_static/cmap/compact-curry.png", show=False)

uncurry(n=1, left=False)

Uncurry a combinatorial map.

Parameters:

• n (int) – The number of objects to uncurry.

• left (bool) – Whether to uncurry on the left or right.

Return type:

CMap

This is inverse to curry() when applied on the same side.

classmethod spiders(n_legs_in, n_legs_out, typ, phases=None)

Spiders are kept as boxes, including their phase data.

Parameters:

• n_legs_in (int) –

• n_legs_out (int) –

• typ (Ty) –

Return type:

CMap

then(other)

Compose maps by gluing output ports to input ports.

Closed components created by gluing are retained in scalars.

>>> 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

Parameters:

other (CMap) –

Return type:

CMap

trace(n=1, left=False)

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:

CMap

tensor(other)

Tensor product given by disjoint union of the two maps.

Parameters:

other (CMap) –

Return type:

CMap

interchange(i, j)

Interchange boxes at indices i and j.

The edges permutation is relabeled so that ports follow the canonical order induced by the new box order.

>>> 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

Parameters:

• i (int) –

• j (int) –

Return type:

CMap

plug_input(input_index, box, cod, root_index=0)

Plug an input boundary and the output root into a new box.

If self : A @ x -> y and box : y -> z @ x, then self.plug_input(i, box, z) removes the i-th input, wires the old output to the domain of box, wires the removed input to the non-root output of box, and leaves root_index as the new root.

Raises:

ValueError – If the map or box does not have the required arity, or either index is out of range.

Parameters:

• input_index (int) –

• box (Box) –

• cod (C0) –

• root_index (int) –

Return type:

CMap

to_diagram()

Downgrade to a diagram directly, preserving box orientation.

The construction scans the currently open wire labels from left to right. For each box, it swaps boundary wires until the box domain wires are adjacent at the requested offset, applies the box, and replaces consumed domain labels by the box codomain labels.

>>> from discopy.compact import Ty, Box
>>> x, y = map(Ty, "xy")
>>> cmap = Box("f", x, y).to_map()
>>> cmap.to_diagram().to_map() == cmap
True

Return type:

Diagram

to_hypergraph()

Forget orientation and return the underlying bijective hypergraph given by the edge permutation. See documentation of :func:Hypergraph.from_map for an example.

to_dot(engine='dot', seed=None, graph_attr=None, port_indices=False)

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, engine='dot', format=None, seed=None, show=None, graph_attr=None, port_indices=False, block=True)

Draw as a combinatorial map using Graphviz.

This is intended for map-like pictures rather than the usual DisCoPy box-and-wire drawing.

If path ends in .dot or .gv, write DOT source. Otherwise, render with Graphviz. When show is true, display the rendered graph in a matplotlib window.

Parameters:

• path – The output path, or None to display the map.

• engine – The Graphviz layout engine.

• format – The rendered format, inferred from path by 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(
...     path="docs/_static/cmap/scalar-loop.png", show=False)