Hypergraph

class discopy.hypergraph.Hypergraph(dom, cod, boxes, wires, spider_types=None, offsets=None)

Bases: discopy.abc.MonoidalCategory, discopy.abc.Result

A hypergraph is given by:

• a domain, a codomain and an n-tuple of boxes

• a Wiring triple dom_wires, box_wires, cod_wires where

  • (dom_wires, cod_wires) is the Boundary of the hypergraph

  • box_wires: tuple[Boundary, ...] is the boundary of each box

• an optional mapping SpiderTypes from spiders to types

A Boundary is just a pair of input and output Wires.

Wires are n-tuples of Spider labels.

Spider labels can be of any type.

Parameters:

• dom (category.ob) – The domain of the diagram, i.e. its input.

• cod (category.ob) – The codomain of the diagram, i.e. its output.

• boxes (tuple[category, ...]) – The boxes inside the diagram.

• wires (Wiring) – List of wires from ports to spiders.

• spider_types (SpiderTypes) – Optional mapping from spiders to atomic types, if None then this is computed from the types of ports.

• offsets (tuple[int | None, ...]) – tuple[int | None, …] Number of wires left of each box, used by to_diagram().

Note

Abstractly, a hypergraph diagram can be seen as a cospan for the boundary:

range(len(dom)) -> range(n_spiders) <- range(len(cod))

together with a cospan for each box in boxes:

range(len(box.dom)) -> range(n_spiders) <- range(len(box.cod))

Composition of two hypergraph diagram is given by the pushout of the span:

range(self.n_spiders) <- range(len(self.cod)) -> range(other.n_spiders)

Note

The Hypergraph class is parameterised by a Category, i.e. instances of Hypergraph[C] have dom: C.ob and cod: C.ob as boundary and boxes: tuple[C.ar, ...] as generators. For example:

>>> from discopy.frobenius import Hypergraph as H
>>> from discopy.frobenius import Ty, Diagram
>>> assert H.category.ob == Ty and H.category == Diagram

The Functor used by from_diagram() is read off the category itself, i.e. H.functor == H.category.functor_factory.

>>> from discopy.frobenius import Functor
>>> assert H.functor == Functor

Thus subclasses of Diagram get hypergraphs of their own category without a dedicated Hypergraph class, e.g. Hypergraph[Diagram].

Examples

>>> x, y, z = map(Ty, "xyz")

>>> assert H.id(x @ y @ z).n_spiders == 3
>>> assert H.id(x @ y @ z).wires ==((0, 1, 2), (), (0, 1, 2))

>>> assert H.swap(x, y).n_spiders == 2
>>> assert H.swap(x, y).wires == ((0, 1), (), (1, 0))

>>> assert H.spiders(1, 2, x @ y).n_spiders == 2
>>> assert H.spiders(1, 2, x @ y).wires ==((0, 1), (), (0, 1, 0, 1))
>>> assert H.spiders(0, 0, x @ y @ z).n_spiders == 3
>>> assert H.spiders(0, 0, x @ y @ z).wires == ((), (), ())

>>> from discopy.frobenius import Box
>>> f, g = Box('f', x, y).to_hypergraph(), Box('g', y, z).to_hypergraph()

>>> assert f.n_spiders == g.n_spiders == 2
>>> assert f.wires == g.wires == ((0, ), (((0, ), (1, )), ), (1, ))

>>> assert (f >> g).n_spiders == 3
>>> assert (f >> g).wires == ((0,), (((0,), (1,)), ((1,), (2,))), (2,))

>>> assert (f @ g).n_spiders == 4
>>> assert (f @ g).wires == ((0, 1), (((0,), (2,)), ((1,), (3,))), (2, 3))

property spider_wires: list[tuple[set[int], set[int]]]

The input and output wires for each spider of a hypergraph.

Example

>>> from discopy.frobenius import Ty, Box, Hypergraph as H

>>> x, y = map(Ty, "xy")
>>> f = Box('f', x, y).to_hypergraph()
>>> for wires in (f >> H.spiders(1, 2, y)).spider_wires: print(wires)
({0}, {1})
({2}, {3, 4})

property ports: list[Node]

The ports in a diagram.

Examples

>>> from discopy.frobenius import Ty, Box, Hypergraph as H

>>> x, y, z = map(Ty, "xyz")
>>> f = Box('f', x, y @ y).to_hypergraph()
>>> g = Box('g', y @ y, z).to_hypergraph()
>>> for port in (f >> g).ports: print(port)
Node('input', i=0, obj=x)
Node('dom', depth=0, i=0, obj=x)
Node('cod', depth=0, i=0, obj=y)
Node('cod', depth=0, i=1, obj=y)
Node('dom', depth=1, i=0, obj=y)
Node('dom', depth=1, i=1, obj=y)
Node('cod', depth=1, i=0, obj=z)
Node('output', i=0, obj=z)

rebracket(flat_wires, boxes=None, dom=None)

Rebracket a flat list of Spider into a proper Wiring.

Parameters:

flat_wires (list[Any])

property n_spiders

The number of spiders in a hypergraph diagram.

property scalar_spiders

The zero-legged spiders in a hypergraph diagram.

then(other)

Composition of two hypergraph diagrams, i.e. their pushout().

Parameters:

other (Hypergraph)

tensor(other)

Tensor of two hypergraph diagrams, i.e. their disjoint union.

Parameters:

other (Hypergraph)

dagger()

Dagger of a hypergraph diagram, called with [::-1].

Examples

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x, y, z = map(Ty, "xyz")
>>> f = Box('f', x, y).to_hypergraph()
>>> g = Box('g', y, z).to_hypergraph()
>>> assert (f >> g)[::-1] == g[::-1] >> f[::-1]
>>> assert H.spiders(1, 2, x @ y)[::-1] == H.spiders(2, 1, x @ y)

classmethod permutation(xs, doms)

The hypergraph that encodes a given permutation, with the same semantics as discopy.symmetric.Diagram.permutation() but built directly as wires rather than as a chain of swap boxes, i.e. in time linear rather than quadratic in len(xs).

Parameters:

• xs (Sequence[int]) – A list of integers representing a permutation.

• dom – A list of types of the same length as xs.

• doms (Sequence)

Return type:

Hypergraph

transpose(left=False)

The transpose of a hypergraph diagram.

rotate(left=False)

The half-turn rotation of a hypergraph, called with .l and .r.

A half-turn exchanges the two boundaries of everything it turns: of the hypergraph, so that its domain is the rotation of the codomain, and of each box, so that the ports which read its domain come to read its codomain. The spiders are rotated where they stand, being the objects the ports are typed by.

explicit_trace(left=False)

The trace of a hypergraph with explicit boxes (trace, cup or cap).

Parameters:

left – Whether to trace on the left or right.

Note

When category.trace_factory is a subclass of category, e.g. for symmetric diagrams, then the result is just one big trace box wrapped up as a hypergraph.

Otherwise, we assume that the trace factory is a class method, e.g. for compact diagrams, in which case we use this method to introduce cup and cap boxes.

trace(n=1, left=False)

The trace of a hypergraph is its pre- and post-composition with cups and caps to form a feedback loop.

Parameters:

• n – The number of wires to trace.

• left – Whether to trace on the left or right.

interchange(i, j)

Interchange boxes at indices i and j.

Parameters:

• i (int) – The index of the first box.

• j (int) – The index of the second box.

Return type:

Hypergraph

Example

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x = Ty('x')
>>> f = Box('f', Ty(), x).to_hypergraph()
>>> g = Box('g', x, Ty()).to_hypergraph()
>>> print((f >> g).interchange(0, 1))
Cap(x, x) >> g @ x >> f @ x >> Cup(x, x)

simplify()

Simplify by applying interchangers eagerly until the length of the diagram is minimal, takes quadratic time.

Example

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x = Ty('x')
>>> f = Box('f', Ty(), x).to_hypergraph()
>>> g = Box('g', x, Ty()).to_hypergraph()
>>> assert (f >> g).interchange(0, 1).simplify() == f >> g

Return type:

Hypergraph

box_dependencies()

Box-level dependency graph induced by the wiring, used to detect cycles and to compute a canonical box order in linear time, as an alternative to building the full port-level causal_graph().

Returns a producer and a consumer box index for each spider (-1 for the global boundary), a mapping from each spider to its position in dom_wires and the resulting dependents/indegree lists for the boxes.

property is_boundary_connected: bool

Checks boundary-connectedness, i.e. whether the graph with boxes as edges and spiders as vertices is connected, after adding one extra boundary node joined to every spider in dom_wires and cod_wires. The boundary node is always added, even when the boundary is empty, so that e.g. a closed diagram with a non-trivial interior (such as a trace of a tensor, or a scalar spider) is not boundary-connected: the boundary node then has no edges and is its own isolated component.

Note this has nothing to do with acyclicity: there are acyclic diagrams that are not boundary-connected, e.g. a tensor of two scalar boxes, and there are boundary-connected diagrams that are cyclic, e.g. the trace of an endomorphism.

Examples

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x, y, z = map(Ty, "xyz")
>>> f = Box('f', x, x).to_hypergraph()
>>> assert f.is_boundary_connected

>>> # The trace of an endomorphism with a non-empty boundary is
>>> # boundary-connected even though it is cyclic.
>>> g = Box('g', x @ z, y @ z).to_hypergraph()
>>> assert g.trace().is_boundary_connected

>>> # Tracing away the whole domain leaves an empty, closed loop.
>>> assert not f.trace().is_boundary_connected

>>> scalar = Box('s', Ty(), Ty()).to_hypergraph()
>>> assert not (scalar @ scalar).is_boundary_connected
>>> assert not H.spiders(0, 0, x).is_boundary_connected

>>> assert H.id(Ty()).is_boundary_connected

property is_fast_eligible: bool

Whether __eq__() and __hash__() can use the linear-time boundary-rooted canonical form instead of graph isomorphism.

boundary_rooted_canonical()

Canonical form of a monogamous, boundary-connected hypergraph, used to compare such diagrams in linear time instead of checking for graph isomorphism. Computed by a deterministic breadth-first traversal rooted at the boundary, assigning each spider and box a canonical rank the first time it is reached; this tolerates cycles natively, unlike a topological sort. Two hypergraphs are then equal iff their canonical forms have equal boxes and wires (compared as plain attributes, not with ==, to avoid recursing back into __eq__()).

Returns None if the traversal could not certify a complete canonical order, e.g. because of a genuine symmetry between two independent parts of the diagram, in which case the caller should fall back to a slower method.

Return type:

Hypergraph | None

property bijection

Bijection between ports.

:raises ValueError : If the hypergraph is not bijective.:

Examples

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x, y = map(Ty, "xy")
>>> f = Box('f', x, y).to_hypergraph()
>>> for i, port in enumerate(f.ports): print(i, port)
0 Node('input', i=0, obj=x)
1 Node('dom', depth=0, i=0, obj=x)
2 Node('cod', depth=0, i=0, obj=y)
3 Node('output', i=0, obj=y)
>>> for i, j in enumerate(f.bijection): print(f"{i} -> {j}")
0 -> 1
1 -> 0
2 -> 3
3 -> 2

classmethod from_map(old)

Forget orientation and return the underlying bijective hypergraph given by the edge permutation.

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

Return type:

Hypergraph

to_map()

Build a combinatorial map, introducing spider boxes if needed.

property is_bijective: bool

Checks bijectivity, i.e. each spider is connected to two or zero ports. In that case, the diagram actually lives in a compact-closed category, i.e. it can be drawn using only swaps, cups and caps.

Examples

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x, y = map(Ty, "xy")
>>> f = Box('f', x, y).to_hypergraph()
>>> assert f.is_bijective and f.transpose().is_bijective
>>> assert H.cups(x, x).is_bijective and H.caps(x, x).is_bijective
>>> assert H.spiders(0, 0, x).is_bijective
>>> assert not H.spiders(1, 2, x).is_bijective

property is_monogamous: bool

Checks monogamy, i.e. each input connects to exactly one output, formally whether self.wires induces a bijection:

len(self.dom) + sum(len(box.dom) for box in boxes)
== self.n_spiders - len(self.scalar_spiders)
== sum(len(box.cod) for box in boxes) + len(self.dom)

In that case, the diagram actually lives in a traced category.

Examples

>>> from discopy.frobenius import Ty, Box, Hypergraph as H

>>> x, y = map(Ty, "xy")
>>> f = Box('f', x, y).to_hypergraph()

>>> assert f.is_monogamous
>>> assert (f >> f[::-1]).is_monogamous

>>> assert H.spiders(0, 0, x).is_monogamous

>>> cycle = H.caps(x, x) >> x @ (f >> f[::-1]) >> H.cups(x, x)
>>> assert cycle.is_monogamous

>>> assert not f.transpose().is_monogamous
>>> assert not H.cups(x, x).is_monogamous
>>> assert not H.spiders(1, 2, x).is_monogamous
>>> assert not H.spiders(2, 3, x).is_monogamous

property is_left_monogamous: bool

Checks left monogamy, i.e. if each non-scalar spider is connected to exactly one input port.

property is_causal: bool

Checks causality, i.e. if each non-scalar spider is connected to exactly one input port, there is no directed cycle, and wires point forward in the current port order. It is equivalent to: - is_left_monogamous - is_acyclic - is_topological_ordered

If the diagram is causal then it lives in a symmetric monoidal category with a supply of commutative comonoids.

If the diagram is causal and monogamous then it actually lives in a symmetric monoidal category, i.e. it can be drawn using only swaps.

Examples

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x, y, z = map(Ty, "xyz")
>>> f = Box('f', x, y).to_hypergraph()
>>> assert f.is_causal
>>> assert (f >> H.spiders(1, 0, y)).is_causal
>>> assert (H.spiders(1, 2, x) >> f @ f).is_causal

>>> g = Box('g', y, z).to_hypergraph()
>>> assert (f >> g).interchange(0, 1).is_acyclic
>>> assert not (f >> g).interchange(0, 1).is_causal

>>> cycle = H.caps(x, x) >> H.cups(x, x)
>>> assert not cycle.is_acyclic
>>> assert not cycle.is_causal
>>> assert cycle.make_causal().is_causal

>>> assert not H.cups(x, x).is_causal

property is_acyclic: bool

Checks that the causal graph has no directed cycle, with a plain Kahn’s algorithm on the box-level dependency graph, avoiding the construction of a full networkx graph on ports. As an edge case, we also need to check that there are no scalar spiders, otherwise the causal graph has 0 nodes and is thus trivially acyclic.

Examples

>>> from discopy.frobenius import Ty, Box, Cap, Cup, Hypergraph as H
>>> x, y, z = map(Ty, 'xyz')
>>> f = Box('f', x, x)
>>> g = Box('f', x @ z, y @ z)

>>> # Simple case: cup and caps and trace form cycles
>>> assert not (
...     Cap(x, x) >> x @ f >> Cup(x, x)
... ).to_hypergraph().is_acyclic
>>> assert not g.trace().to_hypergraph().is_acyclic

>>> # Breaking causality but not acyclicity:
>>> f_snake = (
...     Cap(x, x) @ x >> x @ f @ x >> x @ Cup(x, x)
... ).to_hypergraph()
>>> assert not f_snake.is_causal and f_snake.is_acyclic

>>> # Edge case: cyclic hypergraph without boxes
>>> assert not (Cap(x, x) >> Cup(x, x)).to_hypergraph().is_acyclic

property is_topologically_ordered: bool

Checks that causal wires point forward in the current port order.

causal_graph()

Directed graph on ports induced by spiders and boxes.

Return type:

DiGraph

topological_order()

Reorder boxes so that causal wires point forward in flat_wires.

Return type:

Hypergraph

make_bijective()

Introduces spider boxes to make self bijective.

Example

>>> from discopy.frobenius import Ty, Spider, Hypergraph as H

>>> spider = H.spiders(3, 2, Ty('x')).make_bijective()
>>> assert spider.boxes == (Spider(3, 2, Ty('x')), )
>>> assert spider.wires == ((0, 1, 2), (((0, 1, 2), (3, 4)),), (3, 4))

>>> copy = H.spiders(1, 2, Ty('x', 'y')).make_bijective()
>>> assert copy.boxes == (Spider(1, 2, Ty('x')), Spider(1, 2, Ty('y')))

>>> unit = H.spiders(0, 1, Ty('x', 'y')).make_bijective()
>>> assert unit.boxes == (Spider(0, 1, Ty('y')), Spider(0, 1, Ty('x')))

Return type:

Hypergraph

make_monogamous()

Introduce Cup and Cap boxes to make self monogamous.

Example

>>> from discopy.frobenius import Ty, Box, Cup, Cap, Spider
>>> x = Ty('x')
>>> h = Box('f', x, x).transpose().to_hypergraph().make_monogamous()
>>> assert list(zip(h.boxes, h.box_wires)) == [
...     (Cap(x, x),      ((),     (1, 2))),
...     (Box('f', x, x), ((1,),   (3,)  )),
...     (Cup(x, x),      ((0, 3), ()    ))]

Return type:

Hypergraph

make_left_monogamous()

Introduce spider boxes to make self left monogamous.

Example

>>> from discopy.frobenius import Ty, Box, Hypergraph as H, Spider
>>> h = H.spiders(2, 3, Ty('x')).make_left_monogamous()
>>> assert h.boxes == (Spider(2, 1, Ty('x')), )
>>> assert h.wires == ((0, 1), (((0, 1), (2,)),), (2, 2, 2))

Return type:

Hypergraph

make_causal()

Introduce trace boxes to make self causal.

Example

>>> from discopy.frobenius import Ty, Box, Cup, Cap
>>> x = Ty('x')
>>> f = Box('f', x @ x, x @ x).to_hypergraph()
>>> assert f.trace().make_causal().boxes\
...     == (Cap(x, x), f.boxes[0], Cup(x, x))

>>> from discopy.frobenius import Hypergraph as H, Spider
>>> assert H.spiders(2, 1, x).make_causal().boxes\
...     == (Spider(2, 1, x),)

Return type:

Hypergraph

property is_generator

Whether the hypergraph is a single generator.

property generator

Return the f from Hypergraph.from_box(f) if is_generator.

classmethod from_box(box)

Turn a box into a hypergraph with binary spiders for each wire.

Parameters:

box (Box) – The box to turn into a hypergraph.

Return type:

Hypergraph

Example

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x, y, z = map(Ty, "xyz")
>>> for p in Box('f', x, y @ z).to_hypergraph().ports: print(p)
Node('input', i=0, obj=x)
Node('dom', depth=0, i=0, obj=x)
Node('cod', depth=0, i=0, obj=y)
Node('cod', depth=0, i=1, obj=z)
Node('output', i=0, obj=y)
Node('output', i=1, obj=z)

classmethod from_glued(dom, cod, images)

Glue a sequence of hypergraphs onto a scan of open wires, in one pass.

Each spider of the result is a connected component of the spiders of the images, computed by union-find as they are glued. This is the colimit of the diagram of gluings, i.e. the same hypergraph as the iterated then() of the images whiskered at their offsets, but built once rather than rebuilt at every step.

Parameters:

• dom (Ty) – The domain of the result.

• cod (Ty) – The codomain of the result.

• images (Iterable[tuple[Hypergraph, int]]) – Each hypergraph to glue, together with the offset at which its domain meets the scan.

Return type:

Hypergraph

Example

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x = Ty('x')
>>> f = Box('f', x, x).to_hypergraph()
>>> g = Box('g', x, x).to_hypergraph()
>>> H.from_glued(x, x, [(f, 0), (g, 0)]) == f >> g
True

A cap glued directly onto a cup leaves a closed loop, kept as a scalar spider rather than dropped:

>>> caps, cups = H.caps(x, x), H.cups(x, x)
>>> H.from_glued(H.category.ob(), H.category.ob(), [
...     (caps, 0), (cups, 0)]).scalar_spiders
[0]

classmethod from_diagram(old)

Turn a Diagram into a Hypergraph.

Parameters:

old (Diagram) – The planar diagram to encode as hypergraph.

Return type:

Hypergraph

Note

The image of each box is computed by the functor into cls, then the images are glued in a single pass with from_glued(), rather than folding them one at a time with then(), which relabels the whole hypergraph built so far at every box.

Example

>>> from discopy.frobenius import Ty, Hypergraph as H
>>> x, y = map(Ty, "xy")
>>> back_n_forth = lambda d: H.from_diagram(d.to_diagram())
>>> for d in [H.spiders(0, 0, x),
...           H.spiders(2, 3, x),
...           H.spiders(1, 2, x @ y)]:
...     assert back_n_forth(d) == d

to_diagram()

Downgrade to Diagram, called by print. When the hypergraph is boundary-connected, the boxes are grouped into wide layers (a foliation) rather than a staircase, by scanning the boundary in one pass; this is what discopy.symmetric.Diagram.foliation() relies on.

Note

Hypergraphs can be translated to planar diagrams in two different ways:

• either we first make_bijective() (introducing spiders) then make_monogamous() (introducing cups and caps) and finally make_causal() (introducing traces)

• or we first make_left_monogamous() (introducing merges) then make_causal() (introducing traces) and finally make_bijective() (introducing copies).

We use the first order whenever category is a subclass of HypergraphCategory, i.e. it has a self-dual supply of spiders, or when it has cups and caps. Otherwise, if it is a subclass of MarkovCategory, i.e. it has a supply of comonoids, we use the second order and introduce copies. When the category has neither, a non-monogamous hypergraph cannot be downgraded and we raise an error.

Examples

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x = Ty('x')
>>> v = Box('v', Ty(), x @ x).to_hypergraph()
>>> print(v >> H.swap(x, x) >> v[::-1])
v >> Swap(x, x) >> v[::-1]
>>> print(x @ H.swap(x, x) >> v[::-1] @ x)
Permutation(x @ x @ x, [0, 2, 1]) >> v[::-1] @ x

Return type:

Diagram

classmethod from_callable(dom, cod)

Turns an arbitrary Python function into a causal hypergraph.

Parameters:

• dom (Ty) – The domain of the hypergraph.

• cod (Ty) – The codomain of the hypergraph.

Return type:

Callable[Callable, Hypergraph]

classmethod from_graph(graph)

The inverse of to_graph().

Parameters:

graph (DiGraph)

Return type:

Hypergraph

to_graph()

Translate a hypergraph into a labeled graph with nodes for inputs, outputs, boxes, domain, codomain and spiders.

Return type:

DiGraph

depth()

The depth of a causal hypergraph.

Return type:

int

spring_layout(seed=None, k=None)

Computes a layout using a force-directed algorithm.

draw(seed=None, k=0.25, path=None, doctest=None)

Draw a hypegraph using a force-based layout algorithm.

Examples

>>> from discopy.frobenius import Ty, Box, Hypergraph as H
>>> x, y, z = map(Ty, "xyz")
>>> f = Box('f', x, y @ z).to_hypergraph()
>>> f.draw(
...     doctest='docs/_static/hypergraph/box.svg', seed=42)

>>> (H.spiders(2, 2, x) >> f @ x).draw(
...     doctest='docs/_static/hypergraph/diagram.svg', seed=42)