Struct petgraph::visit::Dfs
[−]
[src]
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 | |
discovered |
Methods
impl<G: Visitable> Dfs<G, G>
fn new(graph: &G, start: G) -> Self
Create a new Dfs, using the graph's visitor map, and put start in the stack of nodes to visit.
fn empty(graph: &G) -> Self
Create a new Dfs using the graph's visitor map, and no stack.
impl<N, VM> Dfs<N, VM> where N: Clone, VM: VisitMap<N>
fn move_to(&mut self, start: N)
Keep the discovered map, but clear the visit stack and restart the dfs from a particular node.
impl<N, VM> Dfs<N, VM> where N: Clone, VM: VisitMap<N>
fn next<'a, G>(&mut self, graph: &'a G) -> Option<N> where G: Graphlike<NodeId=N>, G: for<'b> NeighborIter<'b>
Return the next node in the dfs, or None if the traversal is done.