Add `graph` module, port `contract_nodes` and `has_parallel_edges` to core.

kevinhartman commented 5 months ago

[!IMPORTANT] In the original PR description, I'd suggested we use blanket implementations for all graph types, constrained to apply to compatible graph types using traits. However, this proved not to be ideal, since petgraph does not provide a trait to identify stable versus unstable graphs, yet most algorithms would need to rely on this property to be written efficiently.

Instead, the PR now recommends that we provide explicit implementations per petgraph graph type for ported algorithms.

As part of #1121, this PR is meant as a proposal for a few patterns we might follow to bring rustworkx-core up to parity with our Python API.

To demonstrate these patterns, I've ported contract_nodes and has_parallel_edges from PyGraph and PyDiGraph to rustworkx-core, making the functions available for all stable petgraph graphs (chosen as "complex" and "simple" examples, respectively).

[!NOTE] Many of the methods that currently exist on Py(Di|)Graph are there only to make the Python API more ergonomic (i.e. to side-step PyO3 limitations with iterators and data ownership). These methods should probably not be ported to core. In general, rustworkx-core's API should feel like a Rust API.

Extension traits

The primary pattern proposed here is to provide traits for the various graph methods of Py(Di|)Graph worth porting to core, along with implementations for applicable petgraph graph types.

To aid in discoverability, we can also expose modules intended for import via * that bring all supported extension methods into scope for the graph type. For example, we can import all graph extensions as follows (which, at least in the CLion IDE, adds per-graph compatible methods to code completion):

use petgraph::prelude::*;

// Imports all extension methods, including `contract_nodes`.
use rustworkx_core::graph_ext::*;

let mut dag: StableDiGraph<char, usize> = ...;
let res = dag.contract_nodes(...);

Node contraction

To see how this idea works with a complex example, I've ported contract_nodes from Py(Di|)Graph. To do this, we introduce 4 different traits: ContractNodesUndirected, ContractNodesSimpleUndirected, ContractNodesDirected, and ContractNodesSimpleUndirected.

We need this many because each of the methods between ContractNodes(Un|Di)rected and ContractNodesSimple(Un|Di)rected has a different signature and return type (since each has a different set of possible errors).

Error interface

In #1124 we started discussing how the core's error interface ought to look. Originally, I proposed that we should aim to have a single error type returned by all core functions which may fail. However, I see now that this would have been somewhat of a Rust anti-pattern: it's generally encouraged to have error types which can indicate multiple failure cases, but it's not proper for functions to return error types with variants that can never happen in the given function's execution.

Instead, we define unique error enum types for each function to encapsulate exactly the error set it may return. For example, we introduce two error types ContractError and ContractSimpleError for node contraction, since only simple contractions can fail due to an edge merge issue.

For errors, I'd propose putting all error types within src/err.rs. These can then be imported internally by extension trait implementations in the graph module, as well as by top-level functions outside it.

On the Python-side, we can implement From<...> for RxPyErr to automatically map each error type to a Python exception. This is done for both ContractError and ContractSimpleError. See the docstring for RxPyErr for more detail.

Integration testing

I've added a new folder tests/graph_ext which contains a main.rs file. Any modules registered there get automatically picked up and included in the same integration testing executable. For now, there's a file contraction.rs which contains modules for testing against StableGraph and GraphMap (the two stable graph types in petgraph). Additional algorithms ported to graph_ext should be added to this folder.

Other

I've also added a new trait NodeRemovable, which we've been needing for a while. It's similar to the Build trait provided by petgraph, but provides node removal.
In case it isn't clear, the graph module has been added to house our extension methods. Top-level functions can still make sense, and I don't propose we move existing ones. But perhaps for some, we ought to consider exposing them as extensions in parallel for user convenience.

Todo

[x] Port Python tests for contract_nodes and has_parallel_edges to core.

coveralls commented 4 months ago

Pull Request Test Coverage Report for Build 9190954784

Details

243 of 339 (71.68%) changed or added relevant lines in 7 files are covered.
6 unchanged lines in 1 file lost coverage.
Overall coverage decreased (-0.5%) to 96.001%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
src/lib.rs	13	22	59.09%
rustworkx-core/src/graph_ext/mod.rs	3	16	18.75%
rustworkx-core/src/err.rs	0	16	0.0%
rustworkx-core/src/graph_ext/contraction.rs	177	235	75.32%
<!--	Total:	243	339	71.68%	-->

Files with Coverage Reduction	New Missed Lines	%
src/shortest_path/all_pairs_bellman_ford.rs	6	95.53%
<!--	Total:	6		-->

Totals
Change from base Build 9190944049:	-0.5%
Covered Lines:	16973
Relevant Lines:	17680

💛 - Coveralls

kevinhartman commented 3 months ago

This should be ready for another look. Thanks for the review @mtreinish!

EDIT: On the topic of a prelude, I think that's a good idea, but not even petgraph pulls in their visit stuff via their prelude, so I think we ought to think that through separately from this PR.

mtreinish commented 3 months ago

EDIT: On the topic of a prelude, I think that's a good idea, but not even petgraph pulls in their visit stuff via their prelude, so I think we ought to think that through separately from this PR.

Sure, I agree. We can think about a rustworkx core prelude in a follow up for 0.16.0. I'm not sure exactly what we'd want to put it in it.

Qiskit / rustworkx