Comments (6)
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.
Related Issues (20)
- Return sparse matrix instead of dense matrix from adjacency matrix functions HOT 3
- Return paths as a generator instead of list HOT 1
- Performance issue with `custom_vec_iter_impl!` `NodeIndices` HOT 6
- Make the weight function of `dag_longest_path` aware of the nodes' data HOT 3
- Add reverse topological ordering
- Add an `initial_nodes` argument to topological sorters HOT 1
- Support for light/dark mode toggle in docs HOT 1
- No 0.13.x wheels available on linux arm64 with python 3.12 HOT 4
- Node and edge coloring with distance
- Shortest Path Panic HOT 3
- Pass list of sources and targets to dijkstra_shortest_paths
- Dataframe output of all_pairs_dijkstra_shortest_paths? HOT 1
- Include most library functionality in rustworkx-core HOT 3
- Improve rustworkx-core error interface
- Allow passing numpy array to `PyDiGraph::extend_from_edge_list` HOT 3
- Degree centrality support HOT 5
- `bfs_search`, etc. have incorrect type stubs HOT 5
- Add different greedy strategies for node coloring
- Support for "long" attribute type in GraphML HOT 2
- Implementation of Louvain Algorithm HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from rustworkx.