Multigraph support

[akissinger]

I've been thinking about the least intrusive way to add support for parallel edges and self-loops to pyzx, and doing some experimental work on the multigraph branch.

I haven't thought of all the details yet, but here are some notes (included breaking changes). Feedback welcome.

• multigraph support is optional, and depends on the graph backend. If a backend has multigraph support, it should override the new multigraph method of BaseGraph to return True
  • if a method hasn't (yet) been updated to cope with multigraphs, it should throw a NotImplementedError if it gets passed one
  • I've made a copy of GraphS and called it Multigraph. This will be the pure python backend modified to have multigraph support
• BaseGraph should be cleaned up so that its utility methods work for graphs OR multigraphs (in progress)
  • If necessary, methods can check self.multigraph() and implement different behaviors if this is true (although this doesn't seem to be necessary for the most part)
  • I think this is a good time to deprecate some overly complicated methods like replace_subgraph
  • add_edge_table is now just iteratively calling add_edge_smart, which should be implemented on the backend to Do The Right Thing, depending on whether the graph is a multigraph or not.
  • ET should be treated as an opaque ID, rather than a source/target pair. This was always the intention, but it got lost at some point.
• Graph.edge(s, t) now returns the ID of the first edge connecting s and t. Its behavior is undefined if s and t are not connected.
• Graph.edges now has optional s and t parameters to get a Sequence of all the edges connecting s and t. If these are omitted, it gives a Sequence of all edges, as before.

[dlyongemallo]

I'm not familiar with the design decisions that went into the current implementation of graphs in pyzx, but what's the reason for using adjacency lists over an adjacency matrix? In the case of multigraph support, with an adjacency matrix one could just use a weight for each edge type. For example if you had 3 (simple) edges, you'd just give the edge a value of 3, instead of having to manipulate 3 edges. This scales better if one can have many edges between two vertices. The tradeoff is that one can then no longer manipulate any individual edge, if that's really important for some reason.

[jvdwetering]

We often have quite sparse, but large diagrams, so an adjacency matrix would be quite expensive. We also have two different types of edges, so we need some logic to deal with that. Additionally we often care about looping over the neighbours of a vertex, and with our current set up this scales in the number of neighbours, while with an adjacency matrix it scales with the total number of vertices.

[jvdwetering]

I think the multigraph approach we used in DiZX works quite well: https://github.com/jvdwetering/dizx

[dlyongemallo]

We often have quite sparse, but large diagrams, so an adjacency matrix would be quite expensive.

An adjacency matrix for a sparse matrix can be stored very efficiently. It's even possible to efficiently iterate over the neighbours of a vertex, with a bit more work. It really depends on what the expected typical cases are.

[jvdwetering]

Isn't the way you store a sparse matrix by recording where the non-zero positions are with a hash-map? Doesn't this give you essentially the data-structure we are using right now?

[dlyongemallo]

Yes, it's very similar. The difference would only be in whether edges are treated as having individual identities, which makes no difference for simple graphs.

In the case of multigraphs, the first comment above suggests that each edge would have its own unique identity (i.e, there is such a thing as the first edge connecting s and t, so for example they could be connected by edges e1, e2, and e3, and the first and last are simple while the middle is a Hadamard edge). In a matrix representation, you'd only store that there are 2 simple edges and 1 Hadamard edge between s and t, and you wouldn't care that the second edge in particular was Hadamard. For example, if you only cared about the parity of a particular type of edge you could just get it without having to iterate through all the edges.

I'm not familiar enough with what the "typical" zx diagram looks like or what the typical operations are so maybe I'm just missing something, and it's actually important to identify individual edges and their order.

(OTOH, now that I've played around with zxlive a bit, I can see that one might want to identify individual edges for visual purposes.)