]>
Commit | Line | Data |
---|---|---|
f20569fa XL |
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 | ||
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 | ||
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 | ||
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 | ||
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 | { | |
86 | 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 | ||
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 | { | |
166 | 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`. | |
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. | |
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 | |
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. | |
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`. | |
279 | 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 | ||
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 | } |