DAG compose efficient in number of nodes

[kdk]

What is the expected enhancement?

Several methods on terra's DAGCircuit implement some variant of graph composition by topologically sorting one of the input graphs and appending its nodes to the other, one by one. (See e.g. DAGCircuit.compose). The downside of this approach is that the number of operations grows as the number of nodes in the sorted graph. If the sorted DAGCircuit is shorter than it is wide, this is probably actually preferable. Another option for implementing DAG composition is removing output nodes from one circuit, input nodes from the other, and directly adding edges between them. This will scale as the number of qubits, not the number of nodes, which would be preferable if both graphs are longer than they are wide.

In networkx, implementing this style of composition is difficult because each graph is implemented on top of its own dictionary, so there is no way easy way to add edges between the graphs. (There are a handful of ways this might actually be possible, e.g. a globally unique node_id and hacking a dictionary merge on _multi_graph._adj, or if all of our DAGCircuits live as disjoint subgroups inside a single networkx graph, ... but each of these approaches sound likely to cause more problems than they solve.) Is implementing a more efficient composition any simpler in retworkx?

[mtreinish]

I've been looking at this a bit, the internal data structure for the graphs from petgraph should make this possible, but we'll likely want to contribute an implementation there for both Graph and StableGraph because I haven't been able to find the functionality and I expect it will require manipulation of private attributes.

But, basically the graphs are vectors of the nodes and edges inside petgraph https://github.com/petgraph/petgraph/blob/master/src/graph_impl/mod.rs#L332-L336. So it should be possible to just extend those vectors with the list of nodes and edges from another graph. The tricky bits I can see as a potential problem with will likely come up around indexes. Each node and edge struct in a graph keeps track of indexes for it's edges and nodes respectively. So we can easily extend the vectors but then the rhs nodes and edge objects will need to be updated to refer to the new indexes otherwise the structure of the graph will be broken.

In the meantime we might have some performance improvements by trying to implement as much of the existing compose algorithm inside of retworkx as we can, just for the faster iteration time. So even if the algoirthm is inefficient it will at least perform better.