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}