Rewrite rule for removing redundant swaps

[kinianlo]

I am wondering if discopy has any rewriting tools for removing redundant swaps? Specifically, I am trying to automatically remove this kind of redundant swaps:

which is, I believe, equivalent to the followings up to symmetries:

[toumix]

You can translate your diagram back and forth the hypergraph.Diagram class:

from discopy import Ty, Id, Swap, hypergraph
x = Ty("x")
back_n_forth = lambda f: hypergraph.Diagram.upgrade(f).downgrade()
assert back_n_forth(Swap(x, x) >> Swap(x, x)) == Id(x @ x)

The only price to pay is that hypergraph categories are self-adjoint so this will remove all the adjoints from your diagram (i.e. x.r and x.l are both mapped to x).

[y-richie-y]

What if we wrapped all the types? @toumix

[JosephNathaniel]

Hi there, I tried using the back_n_forth function above to simplify redundant swaps, but in some cases it doesn't appear to have the desired behaviour. For instance, consider the diagram

Diagram(dom=Ty(), cod=Ty('n', 'n'), boxes=[Box('Alice', Ty(), Ty('n')), Box('Bob', Ty(), Ty('n')), Box('hates', Ty('n', 'n'), Ty('n', 'n'))], offsets=[0, 1, 0])

Applying back_n_forth yields

[toumix]

The problem comes from the greedy algorithm used for the "forth" part of back_n_forth: it takes the boxes one at a time and when they have no wires coming in, it plugs them on the left of the diagram. This is the reason the unnecessary swap is introduced in your example.

I don't think there is an obvious way to solve this problem. Planarity testing for graphs is a non-trivial problem, it can be solved in linear time but this requires some clever data structures. Adapting those data structures to diagrams, represented as graphs with extra structure, sounds like a very cool project but maybe it's a bit too much effort for the expected payoff.

[toumix]

Maybe the diagrams you are trying to simplify have some special shape for which a simple heuristic can do the trick? In your example it would make sense to add the new boxes to the right hand side instead, this would be very easy to implement.

[RazinShaikh]

Can you share a code snippet for adding new boxes to the right instead?

[toumix]

I'm busy with other things right now but you can try replacing this one line: https://github.com/oxford-quantum-group/discopy/blob/87dcd350480532b616eb7acf9043ab94b8300c70/discopy/drawing.py#L223

with

box, offset = box_node.box, getattr(box_node, "offset", len(scan))

[toumix]

Even better, you could submit a PR for a new optional argument to hypergraph.Diagram.downgrade for switching from left to right.

[RazinShaikh]

Thanks, I will look into it