pub struct Topo<N, VM> { /* private fields */ }
Expand description
A topological order traversal for a graph.
Note that Topo
only visits nodes that are not part of cycles,
i.e. nodes in a true DAG. Use other visitors like DfsPostOrder
or
algorithms like kosaraju_scc to handle graphs with possible cycles.
Implementations§
source§impl<N, VM> Topo<N, VM>
impl<N, VM> Topo<N, VM>
sourcepub fn new<G>(graph: G) -> Self
pub fn new<G>(graph: G) -> Self
Create a new Topo
, using the graph’s visitor map, and put all
initial nodes in the to visit list.
sourcepub fn with_initials<G, I>(graph: G, initials: I) -> Self
pub fn with_initials<G, I>(graph: G, initials: I) -> Self
Create a new Topo
with initial nodes.
Nodes with incoming edges are ignored.
sourcepub fn reset<G>(&mut self, graph: G)
pub fn reset<G>(&mut self, graph: G)
Clear visited state, and put all initial nodes in the to visit list.
sourcepub fn next<G>(&mut self, g: G) -> Option<N>where
G: IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>,
pub fn next<G>(&mut self, g: G) -> Option<N>where
G: IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>,
Return the next node in the current topological order traversal, or
None
if the traversal is at the end.
Note: The graph may not have a complete topological order, and the only way to know is to run the whole traversal and make sure it visits every node.
Trait Implementations§
Auto Trait Implementations§
impl<N, VM> Freeze for Topo<N, VM>where
VM: Freeze,
impl<N, VM> RefUnwindSafe for Topo<N, VM>where
VM: RefUnwindSafe,
N: RefUnwindSafe,
impl<N, VM> Send for Topo<N, VM>
impl<N, VM> Sync for Topo<N, VM>
impl<N, VM> Unpin for Topo<N, VM>
impl<N, VM> UnwindSafe for Topo<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
Mutably borrows from an owned value. Read more
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)
🔬This is a nightly-only experimental API. (
clone_to_uninit
)