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)]);