Struct petgraph::visit::Dfs

pub struct Dfs<N, VM> {
    pub stack: Vec<N>,
    pub discovered: VM,
}

A depth first search (DFS) of a graph.

Using a Dfs 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, 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	The stack of nodes to visit
discovered	The map of discovered nodes

Methods

impl<N, VM> Dfs<N, VM> where N: Clone, VM: VisitMap<N>

fn new<G>(graph: &G, start: N) -> Self where G: Visitable<NodeId=N, Map=VM>

Create a new Dfs, using the graph's visitor map, and put start in the stack of nodes to visit.

fn empty<G>(graph: &G) -> Self where G: Visitable<NodeId=N, Map=VM>

Create a new Dfs using the graph's visitor map, and no stack.

fn move_to(&mut self, start: N)

Keep the discovered map, but clear the visit stack and restart the dfs from a particular node.

fn next<'a, G>(&mut self, graph: &'a G) -> Option<N> where G: Graphlike<NodeId=N>, G: NeighborIter<'a>

Return the next node in the dfs, or None if the traversal is done.

Trait Implementations

Derived Implementations

impl<N: Debug, VM: Debug> Debug for Dfs<N, VM>

fn fmt(&self, __arg_0: &mut Formatter) -> Result

impl<N: Clone, VM: Clone> Clone for Dfs<N, VM>

fn clone(&self) -> Dfs<N, VM>

fn clone_from(&mut self, source: &Self)