petgraph/visit/
traversal.rs

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

petgraph/visit/
traversal.rs
