Struct petgraph::visit::Dfs [−][src]
pub struct Dfs<N, VM> { pub stack: Vec<N>, pub discovered: VM, }
Expand description
Visit nodes of a graph in a depth-first-search (DFS) emitting nodes in preorder (when they are first discovered).
The traversal starts at a given node and only traverses nodes reachable from it.
Dfs
is not recursive.
Dfs
does not itself borrow the graph, and because of this you can run
a traversal over a graph while still retaining mutable access to it, if you
use it like the following example:
use petgraph::Graph; use petgraph::visit::Dfs; let mut graph = Graph::<_,()>::new(); let a = graph.add_node(0); let mut dfs = Dfs::new(&graph, a); while let Some(nx) = dfs.next(&graph) { // we can access `graph` mutably here still graph[nx] += 1; } assert_eq!(graph[a], 1);
Note: The algorithm may not behave correctly if nodes are removed during iteration. It may not necessarily visit added nodes or edges.
Fields
stack: Vec<N>
The stack of nodes to visit
discovered: VM
The map of discovered nodes
Implementations
Create a new Dfs, using the graph’s visitor map, and put start in the stack of nodes to visit.
Create a Dfs
from a vector and a visit map
Clear the visit state
Create a new Dfs using the graph’s visitor map, and no stack.
Keep the discovered map, but clear the visit stack and restart the dfs from a particular node.
Return the next node in the dfs, or None if the traversal is done.
Trait Implementations
fn iter(self, context: Context) -> WalkerIter<Self, Context>ⓘNotable traits for WalkerIter<W, C>
impl<W, C> Iterator for WalkerIter<W, C> where
W: Walker<C>,
C: Clone, type Item = W::Item;
where
Self: Sized,
Context: Clone,
fn iter(self, context: Context) -> WalkerIter<Self, Context>ⓘNotable traits for WalkerIter<W, C>
impl<W, C> Iterator for WalkerIter<W, C> where
W: Walker<C>,
C: Clone, type Item = W::Item;
where
Self: Sized,
Context: Clone,
Create an iterator out of the walker and given context
.
Auto Trait Implementations
impl<N, VM> RefUnwindSafe for Dfs<N, VM> where
N: RefUnwindSafe,
VM: RefUnwindSafe,
impl<N, VM> UnwindSafe for Dfs<N, VM> where
N: UnwindSafe,
VM: UnwindSafe,
Blanket Implementations
Mutably borrows from an owned value. Read more