pub fn johnson_simple_cycles<G>(
graph: G,
self_cycles: Option<Vec<<G as GraphBase>::NodeId>>,
) -> SimpleCycleIterwhere
G: IntoEdgeReferences + IntoNodeReferences + GraphBase + EdgeCount + NodeCount + NodeIndexable + Clone + IntoNeighbors + IntoNeighborsDirected + Visitable + EdgeFindable + GraphProp<EdgeType = Directed>,
<G as GraphBase>::NodeId: Hash + Eq,Expand description
/// Find all simple cycles of a graph
A “simple cycle” (called an elementary circuit in 1) is a cycle (or closed path) where no node appears more than once.
This function is a an implementation of Johnson’s algorithm 1 also based on the non-recursive implementation found in NetworkX2 with code available on Github3.
To handle self cycles in a manner consistent with the NetworkX implementation you should
use the self_cycles argument to collect manually collected self cycle and then remove
the edges leading to a self cycle from the graph. If you don’t do this
the self cycle may or may not be returned by the iterator. The underlying algorithm is not
able to consistently detect self cycles so it is best to handle them before calling this
function. The example below shows a pattern for doing this. You will need to clone the graph
to do this detection without modifying the graph.
§Returns
This function returns a SimpleCycleIter iterator which returns a Vec of NodeIndex.
Note the NodeIndex type is not neccesarily the same as the input graph, as it’s built
using an internal StableGraph used by the algorithm. If your input graph uses a
different node index type that differs from the default NodeIndex<u32>/NodeIndex<DefaultIx>
you will want to convert these objects to your native NodeIndex type.
The return from this function is not guaranteed to have a particular order for either the cycles or the indices in each cycle.
§Example:
use rustworkx_core::petgraph::prelude::*;
use rustworkx_core::connectivity::johnson_simple_cycles;
let mut graph = DiGraph::<(), ()>::new();
graph.extend_with_edges([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]);
// Handle self cycles
let self_cycles_vec: Vec<NodeIndex> = graph
.node_indices()
.filter(|n| graph.neighbors(*n).any(|x| x == *n))
.collect();
for node in &self_cycles_vec {
while let Some(edge_index) = graph.find_edge(*node, *node) {
graph.remove_edge(edge_index);
}
}
let self_cycles = if self_cycles_vec.is_empty() {
None
} else {
Some(self_cycles_vec)
};
let mut cycles_iter = johnson_simple_cycles(&graph, self_cycles);
let mut cycles = Vec::new();
while let Some(mut cycle) = cycles_iter.next(&graph) {
cycle.sort();
cycles.push(cycle);
}
let expected = vec![
vec![NodeIndex::new(0)],
vec![NodeIndex::new(2)],
vec![NodeIndex::new(0), NodeIndex::new(1), NodeIndex::new(2)],
vec![NodeIndex::new(0), NodeIndex::new(2)],
vec![NodeIndex::new(1), NodeIndex::new(2)],
];
assert_eq!(expected.len(), cycles.len());
for cycle in cycles {
assert!(expected.contains(&cycle));
}