Function petgraph::visit::depth_first_search
source · pub fn depth_first_search<G, I, F, C>(graph: G, starts: I, visitor: F) -> Cwhere
G: IntoNeighbors + Visitable,
I: IntoIterator<Item = G::NodeId>,
F: FnMut(DfsEvent<G::NodeId>) -> C,
C: ControlFlow,
Expand description
A recursive depth first search.
Starting points are the nodes in the iterator starts
(specify just one
start vertex x by using Some(x)
).
The traversal emits discovery and finish events for each reachable vertex,
and edge classification of each reachable edge. visitor
is called for each
event, see DfsEvent
for possible values.
If the return value of the visitor is simply ()
, the visit runs until it
is finished. If the return value is a Control<B>
, it can be used to
break the visit early, and the last control value is returned by the
function.
§Example
Find a path from vertex 0 to 5, and exit the visit as soon as we reach the goal vertex.
use petgraph::prelude::*;
use petgraph::graph::node_index as n;
use petgraph::visit::depth_first_search;
use petgraph::visit::{DfsEvent, Control};
let gr: Graph<(), ()> = Graph::from_edges(&[
(0, 1), (0, 2), (0, 3),
(1, 3),
(2, 3), (2, 4),
(4, 0), (4, 5),
]);
// record each predecessor, mapping node → node
let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
let start = n(0);
let goal = n(5);
depth_first_search(&gr, Some(start), |event| {
if let DfsEvent::TreeEdge(u, v) = event {
predecessor[v.index()] = u;
if v == goal {
return Control::Break(v);
}
}
Control::Continue
});
let mut next = goal;
let mut path = vec![next];
while next != start {
let pred = predecessor[next.index()];
path.push(pred);
next = pred;
}
path.reverse();
assert_eq!(&path, &[n(0), n(2), n(4), n(5)]);