/rust/registry/src/index.crates.io-1949cf8c6b5b557f/petgraph-0.8.3/src/visit/dfsvisit.rs

Source
use crate::visit::IntoNeighbors;
use crate::visit::{VisitMap, Visitable};

/// Strictly monotonically increasing event time for a depth first search.
#[derive(Copy, Clone, Debug, PartialEq, PartialOrd, Eq, Ord, Default, Hash)]
pub struct Time(pub usize);

/// A depth first search (DFS) visitor event.
#[derive(Copy, Clone, Debug)]
pub enum DfsEvent<N> {
    Discover(N, Time),
    /// An edge of the tree formed by the traversal.
    TreeEdge(N, N),
    /// An edge to an already visited node.
    BackEdge(N, N),
    /// A cross or forward edge.
    ///
    /// 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, execute the provided statement
/// if it is a prune value.
macro_rules! try_control {
    ($e:expr, $p:stmt) => {
        try_control!($e, $p, ());
    };
    ($e:expr, $p:stmt, $q:stmt) => {
        match $e {
            x => {
                if x.should_break() {
                    return x;
                } else if x.should_prune() {
                    $p
                } else {
                    $q
                }
            }
        }
    };
}

/// 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),
}

impl<B> Control<B> {
    pub fn breaking() -> Control<()> {
        Control::Break(())
    }
    /// Get the value in `Control::Break(_)`, if present.
    pub fn break_value(self) -> Option<B> {
        match self {
            Control::Continue | Control::Prune => None,
            Control::Break(b) => Some(b),
        }
    }
}

/// Control flow for callbacks.
///
/// The empty return value `()` is equivalent to continue.
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> {
    fn continuing() -> Self {
        Control::Continue
    }
    fn should_break(&self) -> bool {
        matches!(*self, Control::Break(_))
    }
    fn should_prune(&self) -> bool {
        matches!(*self, Control::Prune)
    }
}

impl<C: ControlFlow, E> ControlFlow for Result<C, E> {
    fn continuing() -> Self {
        Ok(C::continuing())
    }
    fn should_break(&self) -> bool {
        if let Ok(ref c) = *self {
            c.should_break()
        } else {
            true
        }
    }
    fn should_prune(&self) -> bool {
        if let Ok(ref c) = *self {
            c.should_prune()
        } else {
            false
        }
    }
}

/// The default is `Continue`.
impl<B> Default for Control<B> {
    fn default() -> Self {
        Control::Continue
    }
}

/// A recursive depth first search.
///
/// Starting points are the nodes in the iterator `starts` (specify just one
/// start node *x* by using `Some(x)`).
///
/// The traversal emits discovery and finish events for each reachable node,
/// and edge classification of each reachable edge. `visitor` is called for each
/// event, see [`DfsEvent`][de] for possible values.
///
/// The return value should implement the trait `ControlFlow`, and can be used to change
/// the control flow of the search.
///
/// `Control` Implements `ControlFlow` such that `Control::Continue` resumes the search.
/// `Control::Break` will stop the visit early, returning the contained value.
/// `Control::Prune` will stop traversing any additional edges from the current
/// node and proceed immediately to the `Finish` event.
///
/// There are implementations of `ControlFlow` for `()`, and `Result<C, E>` where
/// `C: ControlFlow`. The implementation for `()` will continue until finished.
/// For `Result`, upon encountering an `E` it will break, otherwise acting the same as `C`.
///
/// **Panics** if you attempt to prune a node from its `Finish` event.
///
/// [de]: enum.DfsEvent.html
///
/// # Example returning `Control`.
///
/// Find a path from node 0 to 5, and exit the visit as soon as we reach
/// the goal node.
///
/// ```
/// 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)]);
/// ```
///
/// # Example returning a `Result`.
/// ```
/// use petgraph::graph::node_index as n;
/// use petgraph::prelude::*;
/// use petgraph::visit::depth_first_search;
/// use petgraph::visit::{DfsEvent, Time};
///
/// let gr: Graph<(), ()> = Graph::from_edges(&[(0, 1), (1, 2), (1, 1), (2, 1)]);
/// let start = n(0);
/// let mut back_edges = 0;
/// let mut discover_time = 0;
/// // Stop the search, the first time a BackEdge is encountered.
/// let result = depth_first_search(&gr, Some(start), |event| {
///     match event {
///         // In the cases where Ok(()) is returned,
///         // Result falls back to the implementation of Control on the value ().
///         // In the case of (), this is to always return Control::Continue.
///         // continuing the search.
///         DfsEvent::Discover(_, Time(t)) => {
///             discover_time = t;
///             Ok(())
///         }
///         DfsEvent::BackEdge(_, _) => {
///             back_edges += 1;
///             // the implementation of ControlFlow for Result,
///             // treats this Err value as Continue::Break
///             Err(event)
///         }
///         _ => Ok(()),
///     }
/// });
///
/// // Even though the graph has more than one cycle,
/// // The number of back_edges visited by the search should always be 1.
/// assert_eq!(back_edges, 1);
/// println!("discover time:{:?}", discover_time);
/// println!("number of backedges encountered: {}", back_edges);
/// println!("back edge: {:?}", result);
/// ```
#[track_caller]
pub fn 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,
{
    let time = &mut Time(0);
    let discovered = &mut graph.visit_map();
    let finished = &mut graph.visit_map();

    for start in starts {
        try_control!(
            dfs_visitor(graph, start, &mut visitor, discovered, finished, time),
            unreachable!()
        );
    }
    C::continuing()
}

pub(crate) fn dfs_visitor<G, F, C>(
    graph: G,
    u: G::NodeId,
    visitor: &mut F,
    discovered: &mut impl VisitMap<G::NodeId>,
    finished: &mut impl VisitMap<G::NodeId>,
    time: &mut Time,
) -> C
where
    G: IntoNeighbors + Visitable,
    F: FnMut(DfsEvent<G::NodeId>) -> C,
    C: ControlFlow,
{
    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)), 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);
            }
        }
    );
    let first_finish = finished.visit(u);
    debug_assert!(first_finish);
    try_control!(
        visitor(DfsEvent::Finish(u, time_post_inc(time))),
        panic!("Pruning on the `DfsEvent::Finish` is not supported!")
    );
    C::continuing()
}

fn time_post_inc(x: &mut Time) -> Time {
    let v = *x;
    x.0 += 1;
    v
}

Coverage Report

Created: 2026-10-28 06:31

Line	Count	Source
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> {
61	0	pub fn breaking() -> Control<()> {
62	0	Control::Break(())
63	0	}
64		/// Get the value in `Control::Break(_)`, if present.
65	0	pub fn break_value(self) -> Option<B> {
66	0	match self {
67	0	Control::Continue \| Control::Prune => None,
68	0	Control::Break(b) => Some(b),
69		}
70	0	}
71		}
72
73		/// Control flow for callbacks.
74		///
75		/// The empty return value `()` is equivalent to continue.
76		pub trait ControlFlow {
77		fn continuing() -> Self;
78		fn should_break(&self) -> bool;
79		fn should_prune(&self) -> bool;
80		}
81
82		impl ControlFlow for () {
83	0	fn continuing() {}
84		#[inline]
85	0	fn should_break(&self) -> bool {
86	0	false
87	0	}
88		#[inline]
89	0	fn should_prune(&self) -> bool {
90	0	false
91	0	}
92		}
93
94		impl<B> ControlFlow for Control<B> {
95	0	fn continuing() -> Self {
96	0	Control::Continue
97	0	}
98	0	fn should_break(&self) -> bool {
99	0	matches!(*self, Control::Break(_))
100	0	}
101	0	fn should_prune(&self) -> bool {
102	0	matches!(*self, Control::Prune)
103	0	}
104		}
105
106		impl<C: ControlFlow, E> ControlFlow for Result<C, E> {
107	0	fn continuing() -> Self {
108	0	Ok(C::continuing())
109	0	}
110	0	fn should_break(&self) -> bool {
111	0	if let Ok(ref c) = *self {
112	0	c.should_break()
113		} else {
114	0	true
115		}
116	0	}
117	0	fn should_prune(&self) -> bool {
118	0	if let Ok(ref c) = *self {
119	0	c.should_prune()
120		} else {
121	0	false
122		}
123	0	}
124		}
125
126		/// The default is `Continue`.
127		impl<B> Default for Control<B> {
128	0	fn default() -> Self {
129	0	Control::Continue
130	0	}
131		}
132
133		/// A recursive depth first search.
134		///
135		/// Starting points are the nodes in the iterator `starts` (specify just one
136		/// start node x by using `Some(x)`).
137		///
138		/// The traversal emits discovery and finish events for each reachable node,
139		/// and edge classification of each reachable edge. `visitor` is called for each
140		/// event, see [`DfsEvent`][de] for possible values.
141		///
142		/// The return value should implement the trait `ControlFlow`, and can be used to change
143		/// the control flow of the search.
144		///
145		/// `Control` Implements `ControlFlow` such that `Control::Continue` resumes the search.
146		/// `Control::Break` will stop the visit early, returning the contained value.
147		/// `Control::Prune` will stop traversing any additional edges from the current
148		/// node and proceed immediately to the `Finish` event.
149		///
150		/// There are implementations of `ControlFlow` for `()`, and `Result<C, E>` where
151		/// `C: ControlFlow`. The implementation for `()` will continue until finished.
152		/// For `Result`, upon encountering an `E` it will break, otherwise acting the same as `C`.
153		///
154		/// Panics if you attempt to prune a node from its `Finish` event.
155		///
156		/// [de]: enum.DfsEvent.html
157		///
158		/// # Example returning `Control`.
159		///
160		/// Find a path from node 0 to 5, and exit the visit as soon as we reach
161		/// the goal node.
162		///
163		/// ```
164		/// use petgraph::prelude::*;
165		/// use petgraph::graph::node_index as n;
166		/// use petgraph::visit::depth_first_search;
167		/// use petgraph::visit::{DfsEvent, Control};
168		///
169		/// let gr: Graph<(), ()> = Graph::from_edges(&[
170		/// (0, 1), (0, 2), (0, 3),
171		/// (1, 3),
172		/// (2, 3), (2, 4),
173		/// (4, 0), (4, 5),
174		/// ]);
175		///
176		/// // record each predecessor, mapping node → node
177		/// let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
178		/// let start = n(0);
179		/// let goal = n(5);
180		/// depth_first_search(&gr, Some(start), \|event\| {
181		/// if let DfsEvent::TreeEdge(u, v) = event {
182		/// predecessor[v.index()] = u;
183		/// if v == goal {
184		/// return Control::Break(v);
185		/// }
186		/// }
187		/// Control::Continue
188		/// });
189		///
190		/// let mut next = goal;
191		/// let mut path = vec![next];
192		/// while next != start {
193		/// let pred = predecessor[next.index()];
194		/// path.push(pred);
195		/// next = pred;
196		/// }
197		/// path.reverse();
198		/// assert_eq!(&path, &[n(0), n(2), n(4), n(5)]);
199		/// ```
200		///
201		/// # Example returning a `Result`.
202		/// ```
203		/// use petgraph::graph::node_index as n;
204		/// use petgraph::prelude::*;
205		/// use petgraph::visit::depth_first_search;
206		/// use petgraph::visit::{DfsEvent, Time};
207		///
208		/// let gr: Graph<(), ()> = Graph::from_edges(&[(0, 1), (1, 2), (1, 1), (2, 1)]);
209		/// let start = n(0);
210		/// let mut back_edges = 0;
211		/// let mut discover_time = 0;
212		/// // Stop the search, the first time a BackEdge is encountered.
213		/// let result = depth_first_search(&gr, Some(start), \|event\| {
214		/// match event {
215		/// // In the cases where Ok(()) is returned,
216		/// // Result falls back to the implementation of Control on the value ().
217		/// // In the case of (), this is to always return Control::Continue.
218		/// // continuing the search.
219		/// DfsEvent::Discover(_, Time(t)) => {
220		/// discover_time = t;
221		/// Ok(())
222		/// }
223		/// DfsEvent::BackEdge(_, _) => {
224		/// back_edges += 1;
225		/// // the implementation of ControlFlow for Result,
226		/// // treats this Err value as Continue::Break
227		/// Err(event)
228		/// }
229		/// _ => Ok(()),
230		/// }
231		/// });
232		///
233		/// // Even though the graph has more than one cycle,
234		/// // The number of back_edges visited by the search should always be 1.
235		/// assert_eq!(back_edges, 1);
236		/// println!("discover time:{:?}", discover_time);
237		/// println!("number of backedges encountered: {}", back_edges);
238		/// println!("back edge: {:?}", result);
239		/// ```
240		#[track_caller]
241	0	pub fn depth_first_search<G, I, F, C>(graph: G, starts: I, mut visitor: F) -> C
242	0	where
243	0	G: IntoNeighbors + Visitable,
244	0	I: IntoIterator<Item = G::NodeId>,
245	0	F: FnMut(DfsEvent<G::NodeId>) -> C,
246	0	C: ControlFlow,
247		{
248	0	let time = &mut Time(0);
249	0	let discovered = &mut graph.visit_map();
250	0	let finished = &mut graph.visit_map();
251
252	0	for start in starts {
253	0	try_control!(
254	0	dfs_visitor(graph, start, &mut visitor, discovered, finished, time),
255	0	unreachable!()
256		);
257		}
258	0	C::continuing()
259	0	}
260
261	0	pub(crate) fn dfs_visitor<G, F, C>(
262	0	graph: G,
263	0	u: G::NodeId,
264	0	visitor: &mut F,
265	0	discovered: &mut impl VisitMap<G::NodeId>,
266	0	finished: &mut impl VisitMap<G::NodeId>,
267	0	time: &mut Time,
268	0	) -> C
269	0	where
270	0	G: IntoNeighbors + Visitable,
271	0	F: FnMut(DfsEvent<G::NodeId>) -> C,
272	0	C: ControlFlow,
273		{
274	0	if !discovered.visit(u) {
275	0	return C::continuing();
276	0	}
277
278	0	try_control!(
279	0	visitor(DfsEvent::Discover(u, time_post_inc(time))),
280	0	{},
281	0	for v in graph.neighbors(u) {
282	0	if !discovered.is_visited(&v) {
283	0	try_control!(visitor(DfsEvent::TreeEdge(u, v)), continue);
284	0	try_control!(
285	0	dfs_visitor(graph, v, visitor, discovered, finished, time),
286	0	unreachable!()
287		);
288	0	} else if !finished.is_visited(&v) {
289	0	try_control!(visitor(DfsEvent::BackEdge(u, v)), continue);
290		} else {
291	0	try_control!(visitor(DfsEvent::CrossForwardEdge(u, v)), continue);
292		}
293		}
294		);
295	0	let first_finish = finished.visit(u);
296	0	debug_assert!(first_finish);
297	0	try_control!(
298	0	visitor(DfsEvent::Finish(u, time_post_inc(time))),
299	0	panic!("Pruning on the `DfsEvent::Finish` is not supported!")
300		);
301	0	C::continuing()
302	0	}
303
304	0	fn time_post_inc(x: &mut Time) -> Time {
305	0	let v = *x;
306	0	x.0 += 1;
307	0	v
308	0	}