Struct petgraph::visit::Bfs
[−]
[src]
pub struct Bfs<N, VM> { pub stack: VecDeque<N>, pub discovered: VM, }
A breadth first search (BFS) of a graph.
The traversal starts at a given node and only traverses nodes reachable from it.
Bfs
is not recursive.
Bfs
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::Bfs; let mut graph = Graph::<_,()>::new(); let a = graph.add_node(0); let mut bfs = Bfs::new(&graph, a); while let Some(nx) = bfs.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: VecDeque<N>
The queue of nodes to visit
discovered: VM
The map of discovered nodes
Methods
impl<N, VM> Bfs<N, VM> where
N: Copy + PartialEq,
VM: VisitMap<N>,
[src]
N: Copy + PartialEq,
VM: VisitMap<N>,
pub fn new<G>(graph: G, start: N) -> Self where
G: GraphRef + Visitable<NodeId = N, Map = VM>,
[src]
G: GraphRef + Visitable<NodeId = N, Map = VM>,
Create a new Bfs, using the graph's visitor map, and put start in the stack of nodes to visit.
pub fn next<G>(&mut self, graph: G) -> Option<N> where
G: IntoNeighbors<NodeId = N>,
[src]
G: IntoNeighbors<NodeId = N>,
Return the next node in the bfs, or None if the traversal is done.
Trait Implementations
impl<N: Clone, VM: Clone> Clone for Bfs<N, VM>
[src]
fn clone(&self) -> Bfs<N, VM>
[src]
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<G> Walker<G> for Bfs<G::NodeId, G::Map> where
G: IntoNeighbors + Visitable,
[src]
G: IntoNeighbors + Visitable,
type Item = G::NodeId
fn walk_next(&mut self, context: G) -> Option<Self::Item>
[src]
Advance to the next item
ⓘImportant traits for WalkerIter<W, C>fn iter(self, context: Context) -> WalkerIter<Self, Context> where
Self: Sized,
Context: Clone,
[src]
Self: Sized,
Context: Clone,
Create an iterator out of the walker and given context
.