Add a minimum spanning tree function about rustworkx HOT 6 CLOSED

None are exactly the same as minimum spanning tree but https://github.com/Qiskit/retworkx/blob/master/src/k_shortest_path.rs and https://github.com/Qiskit/retworkx/blob/master/src/astar.rs are examples where we had to fork the petgraph module and make small tweaks to work with Python objects and python callables.

from rustworkx.

Looking to work on this. Can petgraph implementation of Minimum spanning tree be directly used?

from rustworkx.

At first glance it looked like it would work, you could use that to get the list of nodes and then construct a new PyGraph or PyDiGraph object from that. But, after looking at the petgraphcode though, I don't think it can be directly used. Mostly because of: https://github.com/petgraph/petgraph/blob/0.5.1/src/algo/mod.rs#L574 and https://github.com/petgraph/petgraph/blob/0.5.1/src/algo/mod.rs#L581-L587 which looks like it's directly using the edge weight payload for order in the binary heap. But, the PyObject we use for the edge weight type doesn't implement the PartialOrd trait since it's just a reference to a python object.

I think we probably could fork the petgraph code for the basic algorithm and modify it to work with retworkx. I think we'll probably need to add a parameter that takes a Fn that we pass the edge weight to which will return a f64 that can be used in the binary heap. This is something that we've had to do with a bunch of algorithm functions.

from rustworkx.

This is something that we've had to do with a bunch of algorithm functions.

Can you share an example where this was done? I'll try to keep it consistent

from rustworkx.

I think I will pick this one. I believe we need to decide two things before coding it:

• Are we going to implement all algorithms supported by networkx? It supports Kruskal's (default), Prim's and Boruvka's
• Are we going to use petgraph's UnionFind or code our own for Kruskal's?

from rustworkx.

I think I will pick this one. I believe we need to decide two things before coding it:

* Are we going to implement all algorithms supported by networkx? It supports Kruskal's (default), Prim's and Boruvka's

I think start with (and for this issue) whichever algorithm you prefer, we can always add other algorithms in follow ups if the need arises.

* Are we going to use petgraph's UnionFind or code our own for Kruskal's?

I would say to start we can try petgraph's unionfind but if it doesn't work for some reason we can write up our own version of it.

from rustworkx.