Add support for pruning nodes from a DFS.
diff --git a/src/visit/dfsvisit.rs b/src/visit/dfsvisit.rs
index 4e8a57b..cfb40c9 100644
--- a/src/visit/dfsvisit.rs
+++ b/src/visit/dfsvisit.rs
@@ -20,26 +20,35 @@
/// For an edge *(u, v)*, if the discover time of *v* is greater than *u*,
/// then it is a forward edge, else a cross edge.
CrossForwardEdge(N, N),
+ /// All edges from a node have been reported.
Finish(N, Time),
}
-/// Return if the expression is a break value.
+/// Return if the expression is a break value, execute the provided statement
+/// if it is a prune value.
macro_rules! try_control {
- ($e:expr) => {
+ ($e:expr, $p:stmt) => {
match $e {
x => if x.should_break() {
return x;
+ } else if x.should_prune() {
+ $p;
}
}
}
}
-/// Control flow for callbacks.
-///
-/// `Break` can carry a value.
+/// Control flow for `depth_first_search` callbacks.
#[derive(Copy, Clone, Debug)]
pub enum Control<B> {
+ /// Continue the DFS traversal as normal.
Continue,
+ /// Prune the current node from the DFS traversal. No more edges from this
+ /// node will be reported to the callback. A `DfsEvent::Finish` for this
+ /// node will still be reported. This can be returned in response to any
+ /// `DfsEvent`, except `Finish`, which will panic.
+ Prune,
+ /// Stop the DFS traversal and return the provided value.
Break(B),
}
@@ -48,7 +57,7 @@
/// Get the value in `Control::Break(_)`, if present.
pub fn break_value(self) -> Option<B> {
match self {
- Control::Continue => None,
+ Control::Continue | Control::Prune => None,
Control::Break(b) => Some(b),
}
}
@@ -60,12 +69,15 @@
pub trait ControlFlow {
fn continuing() -> Self;
fn should_break(&self) -> bool;
+ fn should_prune(&self) -> bool;
}
impl ControlFlow for () {
fn continuing() { }
#[inline]
fn should_break(&self) -> bool { false }
+ #[inline]
+ fn should_prune(&self) -> bool { false }
}
impl<B> ControlFlow for Control<B> {
@@ -73,6 +85,12 @@
fn should_break(&self) -> bool {
if let Control::Break(_) = *self { true } else { false }
}
+ fn should_prune(&self) -> bool {
+ match *self {
+ Control::Prune => true,
+ Control::Continue | Control::Break(_) => false,
+ }
+ }
}
impl<E> ControlFlow for Result<(), E> {
@@ -80,6 +98,9 @@
fn should_break(&self) -> bool {
self.is_err()
}
+ fn should_prune(&self) -> bool {
+ false
+ }
}
/// The default is `Continue`.
@@ -98,8 +119,11 @@
///
/// 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.
+/// change the control flow of the search. `Control::Break` will stop the
+/// the visit early, returning the contained value from the function.
+/// `Control::Prune` will stop traversing any additional edges from the current
+/// node and proceed immediately to the `Finish` event. Attempting to prune a
+/// node from its `Finish` event will cause a panic.
///
/// [de]: enum.DfsEvent.html
///
@@ -156,7 +180,8 @@
let finished = &mut graph.visit_map();
for start in starts {
- try_control!(dfs_visitor(graph, start, &mut visitor, discovered, finished, time));
+ try_control!(dfs_visitor(graph, start, &mut visitor, discovered, finished, time),
+ unreachable!());
}
C::continuing()
}
@@ -171,20 +196,27 @@
if !discovered.visit(u) {
return C::continuing();
}
- try_control!(visitor(DfsEvent::Discover(u, time_post_inc(time))));
- for v in graph.neighbors(u) {
- if !discovered.is_visited(&v) {
- try_control!(visitor(DfsEvent::TreeEdge(u, v)));
- try_control!(dfs_visitor(graph, v, visitor, discovered, finished, time));
- } else if !finished.is_visited(&v) {
- try_control!(visitor(DfsEvent::BackEdge(u, v)));
- } else {
- try_control!(visitor(DfsEvent::CrossForwardEdge(u, v)));
+
+ 'prune: loop {
+ try_control!(visitor(DfsEvent::Discover(u, time_post_inc(time))), break 'prune);
+ for v in graph.neighbors(u) {
+ if !discovered.is_visited(&v) {
+ try_control!(visitor(DfsEvent::TreeEdge(u, v)), continue);
+ try_control!(dfs_visitor(graph, v, visitor, discovered, finished, time),
+ unreachable!());
+ } else if !finished.is_visited(&v) {
+ try_control!(visitor(DfsEvent::BackEdge(u, v)), continue);
+ } else {
+ try_control!(visitor(DfsEvent::CrossForwardEdge(u, v)), continue);
+ }
}
+
+ break;
}
let first_finish = finished.visit(u);
debug_assert!(first_finish);
- try_control!(visitor(DfsEvent::Finish(u, time_post_inc(time))));
+ try_control!(visitor(DfsEvent::Finish(u, time_post_inc(time))),
+ panic!("Pruning on the `DfsEvent::Finish` is not supported!"));
C::continuing()
}
diff --git a/tests/graph.rs b/tests/graph.rs
index 773a993..fa76940 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -1539,6 +1539,24 @@
}
path.reverse();
assert_eq!(&path, &[n(0), n(2), n(4)]);
+
+ // check that if we prune 2, we never see 4.
+ let start = n(0);
+ let prune = n(2);
+ let nongoal = n(4);
+ let ret = depth_first_search(&gr, Some(start), |event| {
+ if let Discover(n, _) = event {
+ if n == prune {
+ return Control::Prune;
+ }
+ } else if let TreeEdge(u, v) = event {
+ if v == nongoal {
+ return Control::Break(u);
+ }
+ }
+ Control::Continue
+ });
+ assert!(ret.break_value().is_none());
}
