Struct Dfs

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

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

impl<N, VM> Dfs<N, VM>

where N: Copy + PartialEq, VM: VisitMap<N>,

pub fn new<G>(graph: G, start: N) -> Self

where G: GraphRef + 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.

pub fn from_parts(stack: Vec<N>, discovered: VM) -> Self

Create a Dfs from a vector and a visit map

pub fn reset<G>(&mut self, graph: G)

where G: GraphRef + Visitable<NodeId = N, Map = VM>,

Clear the visit state

pub fn empty<G>(graph: G) -> Self

where G: GraphRef + Visitable<NodeId = N, Map = VM>,

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

pub fn move_to(&mut self, start: N)

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

pub fn next<G>(&mut self, graph: G) -> Option<N>

where G: IntoNeighbors<NodeId = N>,

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

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<N, VM> Default for Dfs<N, VM>

where VM: Default,

fn default() -> Self

Returns the “default value” for a type.

impl<G> Walker<G> for Dfs<G::NodeId, G::Map>

where G: IntoNeighbors + Visitable,

type Item = <G as GraphBase>::NodeId

fn walk_next(&mut self, context: G) -> Option<Self::Item>

Advance to the next item

fn iter(self, context: Context) -> WalkerIter<Self, Context>

where Self: Sized, Context: Clone,

Create an iterator out of the walker and given context.