search

Qiskit / rustworkx

A high performance Python graph library implemented in Rust.
https://www.rustworkx.org
Apache License 2.0
981 stars 142 forks source link

A BFS layers algorithm #804

Open LaurentBergeron opened 1 year ago

LaurentBergeron commented 1 year ago

What is the expected enhancement?

Should be similar to the networkx API: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.traversal.breadth_first_search.bfs_layers.html

It would be great to allow using the visit.BFSVisitor feature, like the current rustworkx bfs_search implementation

abhamra commented 9 months ago

I would like to be assigned to this task, if possible

abhamra commented 9 months ago

@mtreinish Not sure if this task is still up for grabs, but glad to take it on at some point!

mtreinish commented 9 months ago

@abhamra sure thing, I've assigned the issue to you.

1ucian0 commented 1 month ago

Should it be a pub fn in https://github.com/Qiskit/rustworkx/blob/main/rustworkx-core/src/traversal/bfs_visit.rs ?

abhamra commented 1 month ago

Should it be a pub fn in https://github.com/Qiskit/rustworkx/blob/main/rustworkx-core/src/traversal/bfs_visit.rs ?

I had a similar question; essentially, do we want it in rustworkx-core so it's supported for all petgraphs, or just for the Python graph / digraphs through src/traversal/mod.rs, which is where bfs_search is?

mtreinish commented 1 month ago

I think ideally we'd add the interface to rustworkx-core too. The underlying implementation of bfs_search relies on the rustworkx-core function @1ucian0 linked to above. For this I'd expect we'd follow the same pattern so that we expose a rust API from rustworkx-core and use that in the python side of the library.