Infinite loop on cycle_basis when called on a directed graph #1495
Description
Information
- rustworkx-core version: 0.17.1
- Python version: -
- Rust version: 1.88.0
- Operating system: -
What is the current behavior?
rustworkx_core::connectivity::cycle_basis results in an infinite loop when called on (specific) directed graphs.
After consulting the Python API, I understand that this function is not supposed to be called on directed graphs in the first place. However, the Rust API does not restrict or document this.
What is the expected behavior?
The function should be able to either accept DiGraphs without crashing or be restricted to undirected Graphs. As far as I have checked, there would not be an ideal way to implement this, but some quick ideas (usefulness descending, imho):
- The argument bounds could be altered to not accept directed graphs, e.g.,
G: GraphProp<EdgeType = Undirected>. - cycle_basis could treat directed graphs as undirected graphs.
- cycle_basis could runtime-check for a directed graph and produce an error.
Steps to reproduce the problem
Minimal example:
let edge_list = vec![
(0, 1),
(1, 2),
(2, 0),
];
let graph = DiGraph::<i32, i32>::from_edges(edge_list);
let expected = vec![vec![0, 1, 2]];
let res_0 = cycle_basis(&graph, Some(NodeIndex::new(0)));
assert_eq!(sorted_cycle(res_0), expected);The example does not return and eventually runs out of memory.