DAG compose efficient in number of nodes about rustworkx HOT 1 OPEN

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.

from rustworkx.