Function graphalgs::elementary_circuits::elementary_circuits

pub fn elementary_circuits<N, E, Ix>(
    graph: &Graph<N, E, Directed, Ix>
) -> Vec<Vec<NodeIndex<Ix>>>where
    Ix: IndexType,

Finds and returns all elementary circuits in the directed graph. Circuit is another word for cycle. A circuit is called elementary, if it does not contain any node twice.

This function returns the same circuits as Johnson’s algorithm, although in a different order.

Example

use petgraph::Graph;
use petgraph::Directed;
use graphalgs::elementary_circuits::elementary_circuits;
use petgraph::graph::NodeIndex;

fn n(i: usize) -> NodeIndex<usize> {
    NodeIndex::new(i)
}
let graph = Graph::<(), (), Directed, usize>::from_edges([(1,2), (2,3), (3,1), (2,1)]);
let circuits = elementary_circuits(&graph);
assert_eq!(circuits, vec![vec![n(1),n(2)], vec![n(1),n(2),n(3)]]);