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§
source§impl<N, VM> Dfs<N, VM>
impl<N, VM> Dfs<N, VM>
sourcepub fn new<G>(graph: G, start: N) -> Self
pub fn new<G>(graph: G, start: N) -> Self
Create a new Dfs, using the graph’s visitor map, and put start in the stack of nodes to visit.
sourcepub fn from_parts(stack: Vec<N>, discovered: VM) -> Self
pub fn from_parts(stack: Vec<N>, discovered: VM) -> Self
Create a Dfs
from a vector and a visit map
sourcepub fn empty<G>(graph: G) -> Self
pub fn empty<G>(graph: G) -> Self
Create a new Dfs using the graph’s visitor map, and no stack.
sourcepub fn move_to(&mut self, start: N)
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.
sourcepub fn next<G>(&mut self, graph: G) -> Option<N>where
G: IntoNeighbors<NodeId = N>,
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§
Auto Trait Implementations§
impl<N, VM> Freeze for Dfs<N, VM>where
VM: Freeze,
impl<N, VM> RefUnwindSafe for Dfs<N, VM>where
VM: RefUnwindSafe,
N: RefUnwindSafe,
impl<N, VM> Send for Dfs<N, VM>
impl<N, VM> Sync for Dfs<N, VM>
impl<N, VM> Unpin for Dfs<N, VM>
impl<N, VM> UnwindSafe for Dfs<N, VM>where
VM: UnwindSafe,
N: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)