Include most library functionality in rustworkx-core

[mtreinish]

What is the expected enhancement?

Right now we have a divide between what's available in rustworkx and rustworkx-core. The rustworkx python API has far more functionality than rustworkx-core. This makes sense because the library started with just rustworkx and there was no rust api. But I've been finding an increasing number of times where I would like to access things we have implemented in rustworkx from other rust code to find it missing from rustworkx-core. I think we really should move towards trying to close this divide between the crates and ensure rustworkx-core and rustworkx are at feature parity.

I'm proposing that we migrate as much of the functionality as possible to rustworkx-core so that everything we expose to Python users are also available to rust users. We have some one off issues for higher priority items like #769, #741, and #602.
To start I think maybe we should at least have a policy of all new algorithms are written for rustworkx-core and the python interface is built off of that.

Tasks

Beta Give feedback

1. Move lexicographical_topological_sort() functionality to rustworkx-core #1165
   rustworkx-core +1
   
2. Move collect_bicolor_runs() functionality to rustworkx-core #1166
   rustworkx-core +1
   
3. Move layers functionality to rustworkx-core #1167
   rustworkx-core +1
   
4. Move dag longest path functions to rustworkx-core #1168
   rustworkx-core +1
   

[IvanIsCoding]

I think porting our core functionality from rustworkx-core is a good effort now that Qiskit's Rust code also depends on us. I also think that it benefits the Rust community and we do get a couple thousand downloads on crates.io.

One opportunity I would like to explore for us to have yet-another layer of tests on top of the library. Like a fuzzing test suite at the Rust level would be way less expensive than on the Python counterpart but find equally as many logical bugs.

However, I don't think we should require contributions to always include rustworkx-core code. Especially for contributors that want to make a first contribution (e.g. #1089, #796).

Another point is that some contributions like #788 would have been harder to implement in pure Rust first, not in the sense of being hard but getting the interface right first. And I think we'd need to veto our dependencies more carefully if we add everything to rustworkx-core

[kevinhartman]

I think as we build out rustworkx-core to be closer to feature parity with the Python API, it's also a good opportunity to make sure that we're standardizing on API patterns so that the Rust-only UX feels consistent and ergonomic.

I've created #1124 to capture discussion on the error handling interface we may want to expose from core. Separately, I think there may be value in introducing the "extension trait" pattern to rustworkx-core so that petgraph graph types can automatically gain instances methods that mirror the Python API methods we expose on Py(Di|)Graphs. Currently, most rustworkx-core algorithms are implemented as free-standing functions which accept a generic graph G as a first parameter, but with an extension trait pattern, these would appear as instance methods instead.

With the extension trait pattern, we'd define traits for each of the graph methods ported from the Python API, along with "blanket" implementations of each for a generic graph G, where G satisfies the appropriate traits for the algorithm (e.g. whether the graph is directed (GraphProps<EdgeType=Directed>), if nodes are indexable (NodeIndexable), if the graph's edges can be enumerated (IntoEdgeReferences), etc. With this in place, core users just need to import the extension trait, and then the method becomes available on their petgraph iff it is compatible.

I was thinking that if we do go with an approach like this one, it'd make sense to put such extension traits into a graph module within core to represent that these extension traits are all designed to extend existing petgraph types. Users would add use rustworkx_core::graph::{Extension1, Extension2, ...} to the top of their source files, and then graph.extension1(...), graph.extension2(...), etc. would be available for their petgraph graph.

I've got a prototype for this in the same branch containing the error handling interface. I may work this into a PR to make it more visible, but I'm very happy to change any or all of this—the prototype exists to communicate how this idea would manifest.

[IvanIsCoding]

I think as we build out rustworkx-core to be closer to feature parity with the Python API, it's also a good opportunity to make sure that we're standardizing on API patterns so that the Rust-only UX feels consistent and ergonomic.

I've created #1124 to capture discussion on the error handling interface we may want to expose from core. Separately, I think there may be value in introducing the "extension trait" pattern to rustworkx-core so that petgraph graph types can automatically gain instances methods that mirror the Python API methods we expose on Py(Di|)Graphs. Currently, most rustworkx-core algorithms are implemented as free-standing functions which accept a generic graph G as a first parameter, but with an extension trait pattern, these would appear as instance methods instead.

With the extension trait pattern, we'd define traits for each of the graph methods ported from the Python API, along with "blanket" implementations of each for a generic graph G, where G satisfies the appropriate traits for the algorithm (e.g. whether the graph is directed (GraphProps<EdgeType=Directed>), if nodes are indexable (NodeIndexable), if the graph's edges can be enumerated (IntoEdgeReferences), etc. With this in place, core users just need to import the extension trait, and then the method becomes available on their petgraph iff it is compatible.

I was thinking that if we do go with an approach like this one, it'd make sense to put such extension traits into a graph module within core to represent that these extension traits are all designed to extend existing petgraph types. Users would add use rustworkx_core::graph::{Extension1, Extension2, ...} to the top of their source files, and then graph.extension1(...), graph.extension2(...), etc. would be available for their petgraph graph.

I've got a prototype for this in the same branch containing the error handling interface. I may work this into a PR to make it more visible, but I'm very happy to change any or all of this—the prototype exists to communicate how this idea would manifest.

I agree, we'll need to rethink traits, error types, maybe even introduce crate features to stop pulling all the dependencies we currently add.

I do think you should open the PR with the improvements and we can start the discussion from there. Overall it will be a positive addition, it is just that we will need to think more about code we merge.