Symmetric Monoidal Categories

[toumix]

For now, the Diagram class is based on lists of boxes and offsets, it allows only to encode planar diagrams.

In order to encode diagrams in symmetric monoidal categories, we would need a graph-based data structure instead, i.e. we want a class with the following interface:

SDiagram(dom, cod, boxes, graph)

The vertices of the graph are given by inputs + codomains + domains + outputs. Note that scalar boxes do not appear anywhere in the graph: they are not connected to anything. The edges of the graph should satisfy some condition depending on the kind of structure we want:

• For hypergraph categories, there are no restrictions: everything can connect to arbitrarily many things using spiders.
• For compact-closed categories, the graph should be monogamous: everything is connected to exactly one thing.
• For traced categories, the graph should be monogamous plus it only connects inputs to outputs.
• For symmetric monoidal categories proper, the graph should be a monogamous DAG: boxes should be given in a topological ordering, and edges must be monotone.

There should be a forgetful functor from these SDiagram to the usual planar Diagram, so that we can actually draw them. The functor sends a graph-based diagram to a list-based one, adding the necessary swaps, cups, caps and spiders. The adjoint takes a list-based diagram and computes it graph-based form.

This graph-based format would make the encoding of some diagrams smaller: swaps, cups, caps and spiders need not be encoded as boxes anymore. It would also make more equalities hold on the nose: e.g. the Yang-Baxter equation, snake equation and spider fusion. The interchanger reorders the vertices in the graph, it would now encode the naturality equation for symmetry, i.e. we can slide a box through a swap. Another killer app that this format allows is pattern-matching and double-pushout rewriting, see e.g. arXiv:1602.06771 and cartographer.id.

[toumix]

Now that we have hypergraph implemented properly, the description of this task should be updated: we want a special data structure for bijective hypergraphs which can be much more compact than the general case.