Function find_cycle

Source
pub fn find_cycle<G>(
    graph: G,
    source: Option<G::NodeId>,
) -> Vec<(G::NodeId, G::NodeId)>
Expand description

Return the first cycle encountered during DFS of a given directed graph. Empty list is returned if no cycle is found.

Arguments:

  • graph - The directed graph in which to find the first cycle.
  • source - Optional node index for starting the search. If not specified, an arbitrary node is chosen to start the search.

ยงExample

use petgraph::prelude::*;
use rustworkx_core::connectivity::find_cycle;

let edge_list = vec![
    (0, 1),
    (3, 0),
    (0, 5),
    (8, 0),
    (1, 2),
    (1, 6),
    (2, 3),
    (3, 4),
    (4, 5),
    (6, 7),
    (7, 8),
    (8, 9),
];
let graph = DiGraph::<i32, i32>::from_edges(&edge_list);
let mut res: Vec<(usize, usize)> = find_cycle(&graph, Some(NodeIndex::new(0)))
    .iter()
    .map(|(s, t)| (s.index(), t.index()))
    .collect();
assert_eq!(res, [(0, 1), (1, 2), (2, 3), (3, 0)]);