petgraph/visit/
dfsvisit.rs

1
2
3use visit::IntoNeighbors;
4use visit::{VisitMap, Visitable};
5
6/// Strictly monotonically increasing event time for a depth first search.
7#[derive(Copy, Clone, Debug, PartialEq, PartialOrd, Eq, Ord, Default, Hash)]
8pub struct Time(pub usize);
9
10/// A depth first search (DFS) visitor event.
11#[derive(Copy, Clone, Debug)]
12pub enum DfsEvent<N> {
13    Discover(N, Time),
14    /// An edge of the tree formed by the traversal.
15    TreeEdge(N, N),
16    /// An edge to an already visited node.
17    BackEdge(N, N),
18    /// A cross or forward edge.
19    ///
20    /// For an edge *(u, v)*, if the discover time of *v* is greater than *u*,
21    /// then it is a forward edge, else a cross edge.
22    CrossForwardEdge(N, N),
23    Finish(N, Time),
24}
25
26/// Return if the expression is a break value.
27macro_rules! try_control {
28    ($e:expr) => {
29        match $e {
30            x => if x.should_break() {
31                return x;
32            }
33        }
34    }
35}
36
37/// Control flow for callbacks.
38///
39/// `Break` can carry a value.
40#[derive(Copy, Clone, Debug)]
41pub enum Control<B> {
42    Continue,
43    Break(B),
44}
45
46impl<B> Control<B> {
47    pub fn breaking() -> Control<()> { Control::Break(()) }
48    /// Get the value in `Control::Break(_)`, if present.
49    pub fn break_value(self) -> Option<B> {
50        match self {
51            Control::Continue => None,
52            Control::Break(b) => Some(b),
53        }
54    }
55}
56
57/// Control flow for callbacks.
58///
59/// The empty return value `()` is equivalent to continue.
60pub trait ControlFlow {
61    fn continuing() -> Self;
62    fn should_break(&self) -> bool;
63}
64
65impl ControlFlow for () {
66    fn continuing() { }
67    #[inline]
68    fn should_break(&self) -> bool { false }
69}
70
71impl<B> ControlFlow for Control<B> {
72    fn continuing() -> Self { Control::Continue }
73    fn should_break(&self) -> bool {
74        if let Control::Break(_) = *self { true } else { false }
75    }
76}
77
78impl<E> ControlFlow for Result<(), E> {
79    fn continuing() -> Self { Ok(()) }
80    fn should_break(&self) -> bool {
81        self.is_err()
82    }
83}
84
85/// The default is `Continue`.
86impl<B> Default for Control<B> {
87    fn default() -> Self { Control::Continue }
88}
89
90/// A recursive depth first search.
91///
92/// Starting points are the nodes in the iterator `starts` (specify just one
93/// start vertex *x* by using `Some(x)`).
94///
95/// The traversal emits discovery and finish events for each reachable vertex,
96/// and edge classification of each reachable edge. `visitor` is called for each
97/// event, see [`DfsEvent`][de] for possible values.
98///
99/// If the return value of the visitor is simply `()`, the visit runs until it
100/// is finished. If the return value is a `Control<B>`, it can be used to
101/// break the visit early, and the last control value is returned by the
102/// function.
103///
104/// [de]: enum.DfsEvent.html
105///
106/// # Example
107///
108/// Find a path from vertex 0 to 5, and exit the visit as soon as we reach
109/// the goal vertex.
110///
111/// ```
112/// use petgraph::prelude::*;
113/// use petgraph::graph::node_index as n;
114/// use petgraph::visit::depth_first_search;
115/// use petgraph::visit::{DfsEvent, Control};
116///
117/// let gr: Graph<(), ()> = Graph::from_edges(&[
118///     (0, 1), (0, 2), (0, 3),
119///     (1, 3),
120///     (2, 3), (2, 4),
121///     (4, 0), (4, 5),
122/// ]);
123///
124/// // record each predecessor, mapping node → node
125/// let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
126/// let start = n(0);
127/// let goal = n(5);
128/// depth_first_search(&gr, Some(start), |event| {
129///     if let DfsEvent::TreeEdge(u, v) = event {
130///         predecessor[v.index()] = u;
131///         if v == goal {
132///             return Control::Break(v);
133///         }
134///     }
135///     Control::Continue
136/// });
137///
138/// let mut next = goal;
139/// let mut path = vec![next];
140/// while next != start {
141///     let pred = predecessor[next.index()];
142///     path.push(pred);
143///     next = pred;
144/// }
145/// path.reverse();
146/// assert_eq!(&path, &[n(0), n(2), n(4), n(5)]);
147/// ```
148pub fn depth_first_search<G, I, F, C>(graph: G, starts: I, mut visitor: F) -> C
149    where G: IntoNeighbors + Visitable,
150          I: IntoIterator<Item=G::NodeId>,
151          F: FnMut(DfsEvent<G::NodeId>) -> C,
152          C: ControlFlow,
153{
154    let time = &mut Time(0);
155    let discovered = &mut graph.visit_map();
156    let finished = &mut graph.visit_map();
157
158    for start in starts {
159        try_control!(dfs_visitor(graph, start, &mut visitor, discovered, finished, time));
160    }
161    C::continuing()
162}
163
164fn dfs_visitor<G, F, C>(graph: G, u: G::NodeId, visitor: &mut F,
165                     discovered: &mut G::Map, finished: &mut G::Map,
166                     time: &mut Time) -> C
167    where G: IntoNeighbors + Visitable,
168          F: FnMut(DfsEvent<G::NodeId>) -> C,
169          C: ControlFlow,
170{
171    if !discovered.visit(u) {
172        return C::continuing();
173    }
174    try_control!(visitor(DfsEvent::Discover(u, time_post_inc(time))));
175    for v in graph.neighbors(u) {
176        if !discovered.is_visited(&v) {
177            try_control!(visitor(DfsEvent::TreeEdge(u, v)));
178            try_control!(dfs_visitor(graph, v, visitor, discovered, finished, time));
179        } else if !finished.is_visited(&v) {
180            try_control!(visitor(DfsEvent::BackEdge(u, v)));
181        } else {
182            try_control!(visitor(DfsEvent::CrossForwardEdge(u, v)));
183        }
184    }
185    let first_finish = finished.visit(u);
186    debug_assert!(first_finish);
187    try_control!(visitor(DfsEvent::Finish(u, time_post_inc(time))));
188    C::continuing()
189}
190
191fn time_post_inc(x: &mut Time) -> Time {
192    let v = *x;
193    x.0 += 1;
194    v
195}
petgraph/visit/dfsvisit.rs

petgraph/visit/
dfsvisit.rs
