petgraph/visit/traversal.rs
1
2use {Incoming};
3use super::{IntoNeighbors, IntoNeighborsDirected, Visitable, VisitMap};
4use super::{GraphRef, Reversed, IntoNodeIdentifiers};
5use std::collections::VecDeque;
6
7/// Visit nodes of a graph in a depth-first-search (DFS) emitting nodes in
8/// preorder (when they are first discovered).
9///
10/// The traversal starts at a given node and only traverses nodes reachable
11/// from it.
12///
13/// `Dfs` is not recursive.
14///
15/// `Dfs` does not itself borrow the graph, and because of this you can run
16/// a traversal over a graph while still retaining mutable access to it, if you
17/// use it like the following example:
18///
19/// ```
20/// use petgraph::Graph;
21/// use petgraph::visit::Dfs;
22///
23/// let mut graph = Graph::<_,()>::new();
24/// let a = graph.add_node(0);
25///
26/// let mut dfs = Dfs::new(&graph, a);
27/// while let Some(nx) = dfs.next(&graph) {
28/// // we can access `graph` mutably here still
29/// graph[nx] += 1;
30/// }
31///
32/// assert_eq!(graph[a], 1);
33/// ```
34///
35/// **Note:** The algorithm may not behave correctly if nodes are removed
36/// during iteration. It may not necessarily visit added nodes or edges.
37#[derive(Clone, Debug)]
38pub struct Dfs<N, VM> {
39 /// The stack of nodes to visit
40 pub stack: Vec<N>,
41 /// The map of discovered nodes
42 pub discovered: VM,
43}
44
45impl<N, VM> Dfs<N, VM>
46 where N: Copy + PartialEq,
47 VM: VisitMap<N>,
48{
49 /// Create a new **Dfs**, using the graph's visitor map, and put **start**
50 /// in the stack of nodes to visit.
51 pub fn new<G>(graph: G, start: N) -> Self
52 where G: GraphRef + Visitable<NodeId=N, Map=VM>
53 {
54 let mut dfs = Dfs::empty(graph);
55 dfs.move_to(start);
56 dfs
57 }
58
59 /// Create a `Dfs` from a vector and a visit map
60 pub fn from_parts(stack: Vec<N>, discovered: VM) -> Self {
61 Dfs {
62 stack: stack,
63 discovered: discovered,
64 }
65 }
66
67 /// Clear the visit state
68 pub fn reset<G>(&mut self, graph: G)
69 where G: GraphRef + Visitable<NodeId=N, Map=VM>
70 {
71 graph.reset_map(&mut self.discovered);
72 self.stack.clear();
73 }
74
75 /// Create a new **Dfs** using the graph's visitor map, and no stack.
76 pub fn empty<G>(graph: G) -> Self
77 where G: GraphRef + Visitable<NodeId=N, Map=VM>
78 {
79 Dfs {
80 stack: Vec::new(),
81 discovered: graph.visit_map(),
82 }
83 }
84
85 /// Keep the discovered map, but clear the visit stack and restart
86 /// the dfs from a particular node.
87 pub fn move_to(&mut self, start: N)
88 {
89 self.discovered.visit(start);
90 self.stack.clear();
91 self.stack.push(start);
92 }
93
94 /// Return the next node in the dfs, or **None** if the traversal is done.
95 pub fn next<G>(&mut self, graph: G) -> Option<N>
96 where G: IntoNeighbors<NodeId=N>,
97 {
98 if let Some(node) = self.stack.pop() {
99 for succ in graph.neighbors(node) {
100 if self.discovered.visit(succ) {
101 self.stack.push(succ);
102 }
103 }
104
105 return Some(node);
106 }
107 None
108 }
109}
110
111/// Visit nodes in a depth-first-search (DFS) emitting nodes in postorder
112/// (each node after all its descendants have been emitted).
113///
114/// `DfsPostOrder` is not recursive.
115///
116/// The traversal starts at a given node and only traverses nodes reachable
117/// from it.
118#[derive(Clone, Debug)]
119pub struct DfsPostOrder<N, VM> {
120 /// The stack of nodes to visit
121 pub stack: Vec<N>,
122 /// The map of discovered nodes
123 pub discovered: VM,
124 /// The map of finished nodes
125 pub finished: VM,
126}
127
128impl<N, VM> DfsPostOrder<N, VM>
129 where N: Copy + PartialEq,
130 VM: VisitMap<N>,
131{
132 /// Create a new `DfsPostOrder` using the graph's visitor map, and put
133 /// `start` in the stack of nodes to visit.
134 pub fn new<G>(graph: G, start: N) -> Self
135 where G: GraphRef + Visitable<NodeId=N, Map=VM>
136 {
137 let mut dfs = Self::empty(graph);
138 dfs.move_to(start);
139 dfs
140 }
141
142 /// Create a new `DfsPostOrder` using the graph's visitor map, and no stack.
143 pub fn empty<G>(graph: G) -> Self
144 where G: GraphRef + Visitable<NodeId=N, Map=VM>
145 {
146 DfsPostOrder {
147 stack: Vec::new(),
148 discovered: graph.visit_map(),
149 finished: graph.visit_map(),
150 }
151 }
152
153 /// Clear the visit state
154 pub fn reset<G>(&mut self, graph: G)
155 where G: GraphRef + Visitable<NodeId=N, Map=VM>
156 {
157 graph.reset_map(&mut self.discovered);
158 graph.reset_map(&mut self.finished);
159 self.stack.clear();
160 }
161
162 /// Keep the discovered and finished map, but clear the visit stack and restart
163 /// the dfs from a particular node.
164 pub fn move_to(&mut self, start: N)
165 {
166 self.stack.clear();
167 self.stack.push(start);
168 }
169
170 /// Return the next node in the traversal, or `None` if the traversal is done.
171 pub fn next<G>(&mut self, graph: G) -> Option<N>
172 where G: IntoNeighbors<NodeId=N>,
173 {
174 while let Some(&nx) = self.stack.last() {
175 if self.discovered.visit(nx) {
176 // First time visiting `nx`: Push neighbors, don't pop `nx`
177 for succ in graph.neighbors(nx) {
178 if !self.discovered.is_visited(&succ) {
179 self.stack.push(succ);
180 }
181 }
182 } else {
183 self.stack.pop();
184 if self.finished.visit(nx) {
185 // Second time: All reachable nodes must have been finished
186 return Some(nx);
187 }
188 }
189 }
190 None
191 }
192}
193
194/// A breadth first search (BFS) of a graph.
195///
196/// The traversal starts at a given node and only traverses nodes reachable
197/// from it.
198///
199/// `Bfs` is not recursive.
200///
201/// `Bfs` does not itself borrow the graph, and because of this you can run
202/// a traversal over a graph while still retaining mutable access to it, if you
203/// use it like the following example:
204///
205/// ```
206/// use petgraph::Graph;
207/// use petgraph::visit::Bfs;
208///
209/// let mut graph = Graph::<_,()>::new();
210/// let a = graph.add_node(0);
211///
212/// let mut bfs = Bfs::new(&graph, a);
213/// while let Some(nx) = bfs.next(&graph) {
214/// // we can access `graph` mutably here still
215/// graph[nx] += 1;
216/// }
217///
218/// assert_eq!(graph[a], 1);
219/// ```
220///
221/// **Note:** The algorithm may not behave correctly if nodes are removed
222/// during iteration. It may not necessarily visit added nodes or edges.
223#[derive(Clone)]
224pub struct Bfs<N, VM> {
225 /// The queue of nodes to visit
226 pub stack: VecDeque<N>,
227 /// The map of discovered nodes
228 pub discovered: VM,
229}
230
231impl<N, VM> Bfs<N, VM>
232 where N: Copy + PartialEq,
233 VM: VisitMap<N>,
234{
235 /// Create a new **Bfs**, using the graph's visitor map, and put **start**
236 /// in the stack of nodes to visit.
237 pub fn new<G>(graph: G, start: N) -> Self
238 where G: GraphRef + Visitable<NodeId=N, Map=VM>
239 {
240 let mut discovered = graph.visit_map();
241 discovered.visit(start);
242 let mut stack = VecDeque::new();
243 stack.push_front(start);
244 Bfs {
245 stack: stack,
246 discovered: discovered,
247 }
248 }
249
250 /// Return the next node in the bfs, or **None** if the traversal is done.
251 pub fn next<G>(&mut self, graph: G) -> Option<N>
252 where G: IntoNeighbors<NodeId=N>
253 {
254 if let Some(node) = self.stack.pop_front() {
255 for succ in graph.neighbors(node) {
256 if self.discovered.visit(succ) {
257 self.stack.push_back(succ);
258 }
259 }
260
261 return Some(node);
262 }
263 None
264 }
265
266}
267
268/// A topological order traversal for a graph.
269///
270/// **Note** that `Topo` only visits nodes that are not part of cycles,
271/// i.e. nodes in a true DAG. Use other visitors like `DfsPostOrder` or
272/// algorithms like kosaraju_scc to handle graphs with possible cycles.
273#[derive(Clone)]
274pub struct Topo<N, VM> {
275 tovisit: Vec<N>,
276 ordered: VM,
277}
278
279impl<N, VM> Topo<N, VM>
280 where N: Copy + PartialEq,
281 VM: VisitMap<N>,
282{
283 /// Create a new `Topo`, using the graph's visitor map, and put all
284 /// initial nodes in the to visit list.
285 pub fn new<G>(graph: G) -> Self
286 where G: IntoNodeIdentifiers + IntoNeighborsDirected + Visitable<NodeId=N, Map=VM>,
287 {
288 let mut topo = Self::empty(graph);
289 topo.extend_with_initials(graph);
290 topo
291 }
292
293 fn extend_with_initials<G>(&mut self, g: G)
294 where G: IntoNodeIdentifiers + IntoNeighborsDirected<NodeId=N>,
295 {
296 // find all initial nodes (nodes without incoming edges)
297 self.tovisit.extend(g.node_identifiers()
298 .filter(move |&a| g.neighbors_directed(a, Incoming).next().is_none()));
299 }
300
301 /* Private until it has a use */
302 /// Create a new `Topo`, using the graph's visitor map with *no* starting
303 /// index specified.
304 fn empty<G>(graph: G) -> Self
305 where G: GraphRef + Visitable<NodeId=N, Map=VM>
306 {
307 Topo {
308 ordered: graph.visit_map(),
309 tovisit: Vec::new(),
310 }
311 }
312
313 /// Clear visited state, and put all initial nodes in the to visit list.
314 pub fn reset<G>(&mut self, graph: G)
315 where G: IntoNodeIdentifiers + IntoNeighborsDirected + Visitable<NodeId=N, Map=VM>,
316 {
317 graph.reset_map(&mut self.ordered);
318 self.tovisit.clear();
319 self.extend_with_initials(graph);
320 }
321
322 /// Return the next node in the current topological order traversal, or
323 /// `None` if the traversal is at the end.
324 ///
325 /// *Note:* The graph may not have a complete topological order, and the only
326 /// way to know is to run the whole traversal and make sure it visits every node.
327 pub fn next<G>(&mut self, g: G) -> Option<N>
328 where G: IntoNeighborsDirected + Visitable<NodeId=N, Map=VM>,
329 {
330 // Take an unvisited element and find which of its neighbors are next
331 while let Some(nix) = self.tovisit.pop() {
332 if self.ordered.is_visited(&nix) {
333 continue;
334 }
335 self.ordered.visit(nix);
336 for neigh in g.neighbors(nix) {
337 // Look at each neighbor, and those that only have incoming edges
338 // from the already ordered list, they are the next to visit.
339 if Reversed(g).neighbors(neigh).all(|b| self.ordered.is_visited(&b)) {
340 self.tovisit.push(neigh);
341 }
342 }
343 return Some(nix);
344 }
345 None
346 }
347}
348
349
350/// A walker is a traversal state, but where part of the traversal
351/// information is supplied manually to each next call.
352///
353/// This for example allows graph traversals that don't hold a borrow of the
354/// graph they are traversing.
355pub trait Walker<Context> {
356 type Item;
357 /// Advance to the next item
358 fn walk_next(&mut self, context: Context) -> Option<Self::Item>;
359
360 /// Create an iterator out of the walker and given `context`.
361 fn iter(self, context: Context) -> WalkerIter<Self, Context>
362 where Self: Sized,
363 Context: Clone,
364 {
365 WalkerIter {
366 walker: self,
367 context: context,
368 }
369 }
370}
371
372/// A walker and its context wrapped into an iterator.
373#[derive(Clone, Debug)]
374pub struct WalkerIter<W, C> {
375 walker: W,
376 context: C,
377}
378
379impl<W, C> WalkerIter<W, C>
380 where W: Walker<C>,
381 C: Clone,
382{
383 pub fn context(&self) -> C {
384 self.context.clone()
385 }
386
387 pub fn inner_ref(&self) -> &W {
388 &self.walker
389 }
390
391 pub fn inner_mut(&mut self) -> &mut W {
392 &mut self.walker
393 }
394}
395
396impl<W, C> Iterator for WalkerIter<W, C>
397 where W: Walker<C>,
398 C: Clone,
399{
400 type Item = W::Item;
401 fn next(&mut self) -> Option<Self::Item> {
402 self.walker.walk_next(self.context.clone())
403 }
404}
405
406impl<G> Walker<G> for Dfs<G::NodeId, G::Map>
407 where G: IntoNeighbors + Visitable
408{
409 type Item = G::NodeId;
410 fn walk_next(&mut self, context: G) -> Option<Self::Item> {
411 self.next(context)
412 }
413}
414
415impl<G> Walker<G> for DfsPostOrder<G::NodeId, G::Map>
416 where G: IntoNeighbors + Visitable
417{
418 type Item = G::NodeId;
419 fn walk_next(&mut self, context: G) -> Option<Self::Item> {
420 self.next(context)
421 }
422}
423
424impl<G> Walker<G> for Bfs<G::NodeId, G::Map>
425 where G: IntoNeighbors + Visitable
426{
427 type Item = G::NodeId;
428 fn walk_next(&mut self, context: G) -> Option<Self::Item> {
429 self.next(context)
430 }
431}
432
433impl<G> Walker<G> for Topo<G::NodeId, G::Map>
434 where G: IntoNeighborsDirected + Visitable,
435{
436 type Item = G::NodeId;
437 fn walk_next(&mut self, context: G) -> Option<Self::Item> {
438 self.next(context)
439 }
440}