1 use super::{DirectedGraph, WithNumNodes, WithStartNode, WithSuccessors};
2 use rustc_index::bit_set::BitSet;
3 use rustc_index::vec::IndexVec;
4 use std::ops::ControlFlow;
5
6 #[cfg(test)]
7 mod tests;
8
post_order_from<G: DirectedGraph + WithSuccessors + WithNumNodes>( graph: &G, start_node: G::Node, ) -> Vec<G::Node>9 pub fn post_order_from<G: DirectedGraph + WithSuccessors + WithNumNodes>(
10 graph: &G,
11 start_node: G::Node,
12 ) -> Vec<G::Node> {
13 post_order_from_to(graph, start_node, None)
14 }
15
post_order_from_to<G: DirectedGraph + WithSuccessors + WithNumNodes>( graph: &G, start_node: G::Node, end_node: Option<G::Node>, ) -> Vec<G::Node>16 pub fn post_order_from_to<G: DirectedGraph + WithSuccessors + WithNumNodes>(
17 graph: &G,
18 start_node: G::Node,
19 end_node: Option<G::Node>,
20 ) -> Vec<G::Node> {
21 let mut visited: IndexVec<G::Node, bool> = IndexVec::from_elem_n(false, graph.num_nodes());
22 let mut result: Vec<G::Node> = Vec::with_capacity(graph.num_nodes());
23 if let Some(end_node) = end_node {
24 visited[end_node] = true;
25 }
26 post_order_walk(graph, start_node, &mut result, &mut visited);
27 result
28 }
29
post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>( graph: &G, node: G::Node, result: &mut Vec<G::Node>, visited: &mut IndexVec<G::Node, bool>, )30 fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>(
31 graph: &G,
32 node: G::Node,
33 result: &mut Vec<G::Node>,
34 visited: &mut IndexVec<G::Node, bool>,
35 ) {
36 struct PostOrderFrame<Node, Iter> {
37 node: Node,
38 iter: Iter,
39 }
40
41 if visited[node] {
42 return;
43 }
44
45 let mut stack = vec![PostOrderFrame { node, iter: graph.successors(node) }];
46
47 'recurse: while let Some(frame) = stack.last_mut() {
48 let node = frame.node;
49 visited[node] = true;
50
51 while let Some(successor) = frame.iter.next() {
52 if !visited[successor] {
53 stack.push(PostOrderFrame { node: successor, iter: graph.successors(successor) });
54 continue 'recurse;
55 }
56 }
57
58 let _ = stack.pop();
59 result.push(node);
60 }
61 }
62
reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>( graph: &G, start_node: G::Node, ) -> Vec<G::Node>63 pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>(
64 graph: &G,
65 start_node: G::Node,
66 ) -> Vec<G::Node> {
67 let mut vec = post_order_from(graph, start_node);
68 vec.reverse();
69 vec
70 }
71
72 /// A "depth-first search" iterator for a directed graph.
73 pub struct DepthFirstSearch<'graph, G>
74 where
75 G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors,
76 {
77 graph: &'graph G,
78 stack: Vec<G::Node>,
79 visited: BitSet<G::Node>,
80 }
81
82 impl<G> DepthFirstSearch<'graph, G>
83 where
84 G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors,
85 {
new(graph: &'graph G, start_node: G::Node) -> Self86 pub fn new(graph: &'graph G, start_node: G::Node) -> Self {
87 Self { graph, stack: vec![start_node], visited: BitSet::new_empty(graph.num_nodes()) }
88 }
89 }
90
91 impl<G> Iterator for DepthFirstSearch<'_, G>
92 where
93 G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors,
94 {
95 type Item = G::Node;
96
next(&mut self) -> Option<G::Node>97 fn next(&mut self) -> Option<G::Node> {
98 let DepthFirstSearch { stack, visited, graph } = self;
99 let n = stack.pop()?;
100 stack.extend(graph.successors(n).filter(|&m| visited.insert(m)));
101 Some(n)
102 }
103 }
104
105 /// The status of a node in the depth-first search.
106 ///
107 /// See the documentation of `TriColorDepthFirstSearch` to see how a node's status is updated
108 /// during DFS.
109 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
110 pub enum NodeStatus {
111 /// This node has been examined by the depth-first search but is not yet `Settled`.
112 ///
113 /// Also referred to as "gray" or "discovered" nodes in [CLR].
114 ///
115 /// [CLR]: https://en.wikipedia.org/wiki/Introduction_to_Algorithms
116 Visited,
117
118 /// This node and all nodes reachable from it have been examined by the depth-first search.
119 ///
120 /// Also referred to as "black" or "finished" nodes in [CLR].
121 ///
122 /// [CLR]: https://en.wikipedia.org/wiki/Introduction_to_Algorithms
123 Settled,
124 }
125
126 struct Event<N> {
127 node: N,
128 becomes: NodeStatus,
129 }
130
131 /// A depth-first search that also tracks when all successors of a node have been examined.
132 ///
133 /// This is based on the DFS described in [Introduction to Algorithms (1st ed.)][CLR], hereby
134 /// referred to as **CLR**. However, we use the terminology in [`NodeStatus`] above instead of
135 /// "discovered"/"finished" or "white"/"grey"/"black". Each node begins the search with no status,
136 /// becomes `Visited` when it is first examined by the DFS and is `Settled` when all nodes
137 /// reachable from it have been examined. This allows us to differentiate between "tree", "back"
138 /// and "forward" edges (see [`TriColorVisitor::node_examined`]).
139 ///
140 /// Unlike the pseudocode in [CLR], this implementation is iterative and does not use timestamps.
141 /// We accomplish this by storing `Event`s on the stack that result in a (possible) state change
142 /// for each node. A `Visited` event signifies that we should examine this node if it has not yet
143 /// been `Visited` or `Settled`. When a node is examined for the first time, we mark it as
144 /// `Visited` and push a `Settled` event for it on stack followed by `Visited` events for all of
145 /// its predecessors, scheduling them for examination. Multiple `Visited` events for a single node
146 /// may exist on the stack simultaneously if a node has multiple predecessors, but only one
147 /// `Settled` event will ever be created for each node. After all `Visited` events for a node's
148 /// successors have been popped off the stack (as well as any new events triggered by visiting
149 /// those successors), we will pop off that node's `Settled` event.
150 ///
151 /// [CLR]: https://en.wikipedia.org/wiki/Introduction_to_Algorithms
152 pub struct TriColorDepthFirstSearch<'graph, G>
153 where
154 G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors,
155 {
156 graph: &'graph G,
157 stack: Vec<Event<G::Node>>,
158 visited: BitSet<G::Node>,
159 settled: BitSet<G::Node>,
160 }
161
162 impl<G> TriColorDepthFirstSearch<'graph, G>
163 where
164 G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors,
165 {
new(graph: &'graph G) -> Self166 pub fn new(graph: &'graph G) -> Self {
167 TriColorDepthFirstSearch {
168 graph,
169 stack: vec![],
170 visited: BitSet::new_empty(graph.num_nodes()),
171 settled: BitSet::new_empty(graph.num_nodes()),
172 }
173 }
174
175 /// Performs a depth-first search, starting from the given `root`.
176 ///
177 /// This won't visit nodes that are not reachable from `root`.
run_from<V>(mut self, root: G::Node, visitor: &mut V) -> Option<V::BreakVal> where V: TriColorVisitor<G>,178 pub fn run_from<V>(mut self, root: G::Node, visitor: &mut V) -> Option<V::BreakVal>
179 where
180 V: TriColorVisitor<G>,
181 {
182 use NodeStatus::{Settled, Visited};
183
184 self.stack.push(Event { node: root, becomes: Visited });
185
186 loop {
187 match self.stack.pop()? {
188 Event { node, becomes: Settled } => {
189 let not_previously_settled = self.settled.insert(node);
190 assert!(not_previously_settled, "A node should be settled exactly once");
191 if let ControlFlow::Break(val) = visitor.node_settled(node) {
192 return Some(val);
193 }
194 }
195
196 Event { node, becomes: Visited } => {
197 let not_previously_visited = self.visited.insert(node);
198 let prior_status = if not_previously_visited {
199 None
200 } else if self.settled.contains(node) {
201 Some(Settled)
202 } else {
203 Some(Visited)
204 };
205
206 if let ControlFlow::Break(val) = visitor.node_examined(node, prior_status) {
207 return Some(val);
208 }
209
210 // If this node has already been examined, we are done.
211 if prior_status.is_some() {
212 continue;
213 }
214
215 // Otherwise, push a `Settled` event for this node onto the stack, then
216 // schedule its successors for examination.
217 self.stack.push(Event { node, becomes: Settled });
218 for succ in self.graph.successors(node) {
219 if !visitor.ignore_edge(node, succ) {
220 self.stack.push(Event { node: succ, becomes: Visited });
221 }
222 }
223 }
224 }
225 }
226 }
227 }
228
229 impl<G> TriColorDepthFirstSearch<'graph, G>
230 where
231 G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors + WithStartNode,
232 {
233 /// Performs a depth-first search, starting from `G::start_node()`.
234 ///
235 /// This won't visit nodes that are not reachable from the start node.
run_from_start<V>(self, visitor: &mut V) -> Option<V::BreakVal> where V: TriColorVisitor<G>,236 pub fn run_from_start<V>(self, visitor: &mut V) -> Option<V::BreakVal>
237 where
238 V: TriColorVisitor<G>,
239 {
240 let root = self.graph.start_node();
241 self.run_from(root, visitor)
242 }
243 }
244
245 /// What to do when a node is examined or becomes `Settled` during DFS.
246 pub trait TriColorVisitor<G>
247 where
248 G: ?Sized + DirectedGraph,
249 {
250 /// The value returned by this search.
251 type BreakVal;
252
253 /// Called when a node is examined by the depth-first search.
254 ///
255 /// By checking the value of `prior_status`, this visitor can determine whether the edge
256 /// leading to this node was a tree edge (`None`), forward edge (`Some(Settled)`) or back edge
257 /// (`Some(Visited)`). For a full explanation of each edge type, see the "Depth-first Search"
258 /// chapter in [CLR] or [wikipedia].
259 ///
260 /// If you want to know *both* nodes linked by each edge, you'll need to modify
261 /// `TriColorDepthFirstSearch` to store a `source` node for each `Visited` event.
262 ///
263 /// [wikipedia]: https://en.wikipedia.org/wiki/Depth-first_search#Output_of_a_depth-first_search
264 /// [CLR]: https://en.wikipedia.org/wiki/Introduction_to_Algorithms
node_examined( &mut self, _node: G::Node, _prior_status: Option<NodeStatus>, ) -> ControlFlow<Self::BreakVal>265 fn node_examined(
266 &mut self,
267 _node: G::Node,
268 _prior_status: Option<NodeStatus>,
269 ) -> ControlFlow<Self::BreakVal> {
270 ControlFlow::CONTINUE
271 }
272
273 /// Called after all nodes reachable from this one have been examined.
node_settled(&mut self, _node: G::Node) -> ControlFlow<Self::BreakVal>274 fn node_settled(&mut self, _node: G::Node) -> ControlFlow<Self::BreakVal> {
275 ControlFlow::CONTINUE
276 }
277
278 /// Behave as if no edges exist from `source` to `target`.
ignore_edge(&mut self, _source: G::Node, _target: G::Node) -> bool279 fn ignore_edge(&mut self, _source: G::Node, _target: G::Node) -> bool {
280 false
281 }
282 }
283
284 /// This `TriColorVisitor` looks for back edges in a graph, which indicate that a cycle exists.
285 pub struct CycleDetector;
286
287 impl<G> TriColorVisitor<G> for CycleDetector
288 where
289 G: ?Sized + DirectedGraph,
290 {
291 type BreakVal = ();
292
node_examined( &mut self, _node: G::Node, prior_status: Option<NodeStatus>, ) -> ControlFlow<Self::BreakVal>293 fn node_examined(
294 &mut self,
295 _node: G::Node,
296 prior_status: Option<NodeStatus>,
297 ) -> ControlFlow<Self::BreakVal> {
298 match prior_status {
299 Some(NodeStatus::Visited) => ControlFlow::BREAK,
300 _ => ControlFlow::CONTINUE,
301 }
302 }
303 }
304