1 use crate::visit::IntoNeighbors;
2 use crate::visit::{VisitMap, Visitable};
3
4 /// Strictly monotonically increasing event time for a depth first search.
5 #[derive(Copy, Clone, Debug, PartialEq, PartialOrd, Eq, Ord, Default, Hash)]
6 pub struct Time(pub usize);
7
8 /// A depth first search (DFS) visitor event.
9 #[derive(Copy, Clone, Debug)]
10 pub enum DfsEvent<N> {
11 Discover(N, Time),
12 /// An edge of the tree formed by the traversal.
13 TreeEdge(N, N),
14 /// An edge to an already visited node.
15 BackEdge(N, N),
16 /// A cross or forward edge.
17 ///
18 /// For an edge *(u, v)*, if the discover time of *v* is greater than *u*,
19 /// then it is a forward edge, else a cross edge.
20 CrossForwardEdge(N, N),
21 /// All edges from a node have been reported.
22 Finish(N, Time),
23 }
24
25 /// Return if the expression is a break value, execute the provided statement
26 /// if it is a prune value.
27 macro_rules! try_control {
28 ($e:expr, $p:stmt) => {
29 try_control!($e, $p, ());
30 };
31 ($e:expr, $p:stmt, $q:stmt) => {
32 match $e {
33 x => {
34 if x.should_break() {
35 return x;
36 } else if x.should_prune() {
37 $p
38 } else {
39 $q
40 }
41 }
42 }
43 };
44 }
45
46 /// Control flow for `depth_first_search` callbacks.
47 #[derive(Copy, Clone, Debug)]
48 pub enum Control<B> {
49 /// Continue the DFS traversal as normal.
50 Continue,
51 /// Prune the current node from the DFS traversal. No more edges from this
52 /// node will be reported to the callback. A `DfsEvent::Finish` for this
53 /// node will still be reported. This can be returned in response to any
54 /// `DfsEvent`, except `Finish`, which will panic.
55 Prune,
56 /// Stop the DFS traversal and return the provided value.
57 Break(B),
58 }
59
60 impl<B> Control<B> {
breaking() -> Control<()>61 pub fn breaking() -> Control<()> {
62 Control::Break(())
63 }
64 /// Get the value in `Control::Break(_)`, if present.
break_value(self) -> Option<B>65 pub fn break_value(self) -> Option<B> {
66 match self {
67 Control::Continue | Control::Prune => None,
68 Control::Break(b) => Some(b),
69 }
70 }
71 }
72
73 /// Control flow for callbacks.
74 ///
75 /// The empty return value `()` is equivalent to continue.
76 pub trait ControlFlow {
continuing() -> Self77 fn continuing() -> Self;
should_break(&self) -> bool78 fn should_break(&self) -> bool;
should_prune(&self) -> bool79 fn should_prune(&self) -> bool;
80 }
81
82 impl ControlFlow for () {
continuing()83 fn continuing() {}
84 #[inline]
should_break(&self) -> bool85 fn should_break(&self) -> bool {
86 false
87 }
88 #[inline]
should_prune(&self) -> bool89 fn should_prune(&self) -> bool {
90 false
91 }
92 }
93
94 impl<B> ControlFlow for Control<B> {
continuing() -> Self95 fn continuing() -> Self {
96 Control::Continue
97 }
should_break(&self) -> bool98 fn should_break(&self) -> bool {
99 if let Control::Break(_) = *self {
100 true
101 } else {
102 false
103 }
104 }
should_prune(&self) -> bool105 fn should_prune(&self) -> bool {
106 match *self {
107 Control::Prune => true,
108 Control::Continue | Control::Break(_) => false,
109 }
110 }
111 }
112
113 impl<C: ControlFlow, E> ControlFlow for Result<C, E> {
continuing() -> Self114 fn continuing() -> Self {
115 Ok(C::continuing())
116 }
should_break(&self) -> bool117 fn should_break(&self) -> bool {
118 if let Ok(ref c) = *self {
119 c.should_break()
120 } else {
121 true
122 }
123 }
should_prune(&self) -> bool124 fn should_prune(&self) -> bool {
125 if let Ok(ref c) = *self {
126 c.should_prune()
127 } else {
128 false
129 }
130 }
131 }
132
133 /// The default is `Continue`.
134 impl<B> Default for Control<B> {
default() -> Self135 fn default() -> Self {
136 Control::Continue
137 }
138 }
139
140 /// A recursive depth first search.
141 ///
142 /// Starting points are the nodes in the iterator `starts` (specify just one
143 /// start vertex *x* by using `Some(x)`).
144 ///
145 /// The traversal emits discovery and finish events for each reachable vertex,
146 /// and edge classification of each reachable edge. `visitor` is called for each
147 /// event, see [`DfsEvent`][de] for possible values.
148 ///
149 /// The return value should implement the trait `ControlFlow`, and can be used to change
150 /// the control flow of the search.
151 ///
152 /// `Control` Implements `ControlFlow` such that `Control::Continue` resumes the search.
153 /// `Control::Break` will stop the visit early, returning the contained value.
154 /// `Control::Prune` will stop traversing any additional edges from the current
155 /// node and proceed immediately to the `Finish` event.
156 ///
157 /// There are implementations of `ControlFlow` for `()`, and `Result<C, E>` where
158 /// `C: ControlFlow`. The implementation for `()` will continue until finished.
159 /// For `Result`, upon encountering an `E` it will break, otherwise acting the same as `C`.
160 ///
161 /// ***Panics** if you attempt to prune a node from its `Finish` event.
162 ///
163 /// [de]: enum.DfsEvent.html
164 ///
165 /// # Example returning `Control`.
166 ///
167 /// Find a path from vertex 0 to 5, and exit the visit as soon as we reach
168 /// the goal vertex.
169 ///
170 /// ```
171 /// use petgraph::prelude::*;
172 /// use petgraph::graph::node_index as n;
173 /// use petgraph::visit::depth_first_search;
174 /// use petgraph::visit::{DfsEvent, Control};
175 ///
176 /// let gr: Graph<(), ()> = Graph::from_edges(&[
177 /// (0, 1), (0, 2), (0, 3),
178 /// (1, 3),
179 /// (2, 3), (2, 4),
180 /// (4, 0), (4, 5),
181 /// ]);
182 ///
183 /// // record each predecessor, mapping node → node
184 /// let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
185 /// let start = n(0);
186 /// let goal = n(5);
187 /// depth_first_search(&gr, Some(start), |event| {
188 /// if let DfsEvent::TreeEdge(u, v) = event {
189 /// predecessor[v.index()] = u;
190 /// if v == goal {
191 /// return Control::Break(v);
192 /// }
193 /// }
194 /// Control::Continue
195 /// });
196 ///
197 /// let mut next = goal;
198 /// let mut path = vec![next];
199 /// while next != start {
200 /// let pred = predecessor[next.index()];
201 /// path.push(pred);
202 /// next = pred;
203 /// }
204 /// path.reverse();
205 /// assert_eq!(&path, &[n(0), n(2), n(4), n(5)]);
206 /// ```
207 ///
208 /// # Example returning a `Result`.
209 /// ```
210 /// use petgraph::graph::node_index as n;
211 /// use petgraph::prelude::*;
212 /// use petgraph::visit::depth_first_search;
213 /// use petgraph::visit::{DfsEvent, Time};
214 ///
215 /// let gr: Graph<(), ()> = Graph::from_edges(&[(0, 1), (1, 2), (1, 1), (2, 1)]);
216 /// let start = n(0);
217 /// let mut back_edges = 0;
218 /// let mut discover_time = 0;
219 /// // Stop the search, the first time a BackEdge is encountered.
220 /// let result = depth_first_search(&gr, Some(start), |event| {
221 /// match event {
222 /// // In the cases where Ok(()) is returned,
223 /// // Result falls back to the implementation of Control on the value ().
224 /// // In the case of (), this is to always return Control::Continue.
225 /// // continuing the search.
226 /// DfsEvent::Discover(_, Time(t)) => {
227 /// discover_time = t;
228 /// Ok(())
229 /// }
230 /// DfsEvent::BackEdge(_, _) => {
231 /// back_edges += 1;
232 /// // the implementation of ControlFlow for Result,
233 /// // treats this Err value as Continue::Break
234 /// Err(event)
235 /// }
236 /// _ => Ok(()),
237 /// }
238 /// });
239 ///
240 /// // Even though the graph has more than one cycle,
241 /// // The number of back_edges visited by the search should always be 1.
242 /// assert_eq!(back_edges, 1);
243 /// println!("discover time:{:?}", discover_time);
244 /// println!("number of backedges encountered: {}", back_edges);
245 /// println!("back edge: {:?}", result);
246 /// ```
depth_first_search<G, I, F, C>(graph: G, starts: I, mut visitor: F) -> C where G: IntoNeighbors + Visitable, I: IntoIterator<Item = G::NodeId>, F: FnMut(DfsEvent<G::NodeId>) -> C, C: ControlFlow,247 pub fn depth_first_search<G, I, F, C>(graph: G, starts: I, mut visitor: F) -> C
248 where
249 G: IntoNeighbors + Visitable,
250 I: IntoIterator<Item = G::NodeId>,
251 F: FnMut(DfsEvent<G::NodeId>) -> C,
252 C: ControlFlow,
253 {
254 let time = &mut Time(0);
255 let discovered = &mut graph.visit_map();
256 let finished = &mut graph.visit_map();
257
258 for start in starts {
259 try_control!(
260 dfs_visitor(graph, start, &mut visitor, discovered, finished, time),
261 unreachable!()
262 );
263 }
264 C::continuing()
265 }
266
dfs_visitor<G, F, C>( graph: G, u: G::NodeId, visitor: &mut F, discovered: &mut G::Map, finished: &mut G::Map, time: &mut Time, ) -> C where G: IntoNeighbors + Visitable, F: FnMut(DfsEvent<G::NodeId>) -> C, C: ControlFlow,267 fn dfs_visitor<G, F, C>(
268 graph: G,
269 u: G::NodeId,
270 visitor: &mut F,
271 discovered: &mut G::Map,
272 finished: &mut G::Map,
273 time: &mut Time,
274 ) -> C
275 where
276 G: IntoNeighbors + Visitable,
277 F: FnMut(DfsEvent<G::NodeId>) -> C,
278 C: ControlFlow,
279 {
280 if !discovered.visit(u) {
281 return C::continuing();
282 }
283
284 try_control!(
285 visitor(DfsEvent::Discover(u, time_post_inc(time))),
286 {},
287 for v in graph.neighbors(u) {
288 if !discovered.is_visited(&v) {
289 try_control!(visitor(DfsEvent::TreeEdge(u, v)), continue);
290 try_control!(
291 dfs_visitor(graph, v, visitor, discovered, finished, time),
292 unreachable!()
293 );
294 } else if !finished.is_visited(&v) {
295 try_control!(visitor(DfsEvent::BackEdge(u, v)), continue);
296 } else {
297 try_control!(visitor(DfsEvent::CrossForwardEdge(u, v)), continue);
298 }
299 }
300 );
301 let first_finish = finished.visit(u);
302 debug_assert!(first_finish);
303 try_control!(
304 visitor(DfsEvent::Finish(u, time_post_inc(time))),
305 panic!("Pruning on the `DfsEvent::Finish` is not supported!")
306 );
307 C::continuing()
308 }
309
time_post_inc(x: &mut Time) -> Time310 fn time_post_inc(x: &mut Time) -> Time {
311 let v = *x;
312 x.0 += 1;
313 v
314 }
315