Qiskit / rustworkx / 9103534121

94%

push

github

Move dag longest path functions to rustworkx-core.  (#1192)

* Added `longest_path` to rustworkx (needs verification)

Started to port `longest_path` to rustworkx by first adding `longest_path.rs` to `rustworkx-core/src/lib/rs`.

Differences from the original in `rustworkx/src/dag_algo/longest_path.rs`:

- Removed Python-specific code: The function no longer uses pyo3 and PyObject. Instead, it uses generic Rust types.
- Type flexibility: The function parameters now accept any type N for nodes, E for edges, and a weight function F that maps edges (represented by their node indices and edge reference) to a weight of type T. This allows the function to work with different graph and edge types.
- Error handling: Instead of returning a Result, it returns an Option to signify failure only in the case of a cycle, which is preemptively checked at the beginning.
- Using Ord and Add: These trait bounds on T allow for ordering and arithmetic, necessary for determining the longest path.

* Added tests to `rustworkx-core/src/longest_path.rs`

Explanation of Test Cases:

- test_empty_graph: Checks that an empty graph returns a path of length zero with no nodes.
- test_single_node: Checks that a graph with a single node returns the node itself with zero path length (since there's no edge).
 - test_simple_path: A simple two-node graph with one edge. Tests if the function correctly identifies the longest path.
 - test_dag_with_multiple_paths: A Directed Acyclic Graph (DAG) with three nodes and a choice of paths, to test if the function picks the longest one.
- test_graph_with_cycle: Ensures that the function returns None for a graph with a cycle, as longest path calculations should only be done on DAGs.

These test can be run with `cargo test` or with `cargo test test_longest_path`

* Added more detailed function description

Added function descriptions and comments to `longest_path.rs`.

The function description is based off of the format i... (continued)

65 of 65 new or added lines in 2 files covered. (100.0%)

16731 of 17340 relevant lines covered (96.49%)

1220917.64 hits per line