pub struct TriColorDepthFirstSearch<'graph, G>where
G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors,{
graph: &'graph G,
stack: Vec<Event<G::Node>>,
visited: BitSet<G::Node>,
settled: BitSet<G::Node>,
}
Expand description
A depth-first search that also tracks when all successors of a node have been examined.
This is based on the DFS described in Introduction to Algorithms (1st ed.), hereby
referred to as CLR. However, we use the terminology in NodeStatus
above instead of
“discovered”/“finished” or “white”/“grey”/“black”. Each node begins the search with no status,
becomes Visited
when it is first examined by the DFS and is Settled
when all nodes
reachable from it have been examined. This allows us to differentiate between “tree”, “back”
and “forward” edges (see TriColorVisitor::node_examined
).
Unlike the pseudocode in CLR, this implementation is iterative and does not use timestamps.
We accomplish this by storing Event
s on the stack that result in a (possible) state change
for each node. A Visited
event signifies that we should examine this node if it has not yet
been Visited
or Settled
. When a node is examined for the first time, we mark it as
Visited
and push a Settled
event for it on stack followed by Visited
events for all of
its predecessors, scheduling them for examination. Multiple Visited
events for a single node
may exist on the stack simultaneously if a node has multiple predecessors, but only one
Settled
event will ever be created for each node. After all Visited
events for a node’s
successors have been popped off the stack (as well as any new events triggered by visiting
those successors), we will pop off that node’s Settled
event.
Fields§
§graph: &'graph G
§stack: Vec<Event<G::Node>>
§visited: BitSet<G::Node>
§settled: BitSet<G::Node>
Implementations§
source§impl<'graph, G> TriColorDepthFirstSearch<'graph, G>where
G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors,
impl<'graph, G> TriColorDepthFirstSearch<'graph, G>where
G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors,
source§impl<G> TriColorDepthFirstSearch<'_, G>where
G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors + WithStartNode,
impl<G> TriColorDepthFirstSearch<'_, G>where
G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors + WithStartNode,
sourcepub fn run_from_start<V>(self, visitor: &mut V) -> Option<V::BreakVal>where
V: TriColorVisitor<G>,
pub fn run_from_start<V>(self, visitor: &mut V) -> Option<V::BreakVal>where
V: TriColorVisitor<G>,
Performs a depth-first search, starting from G::start_node()
.
This won’t visit nodes that are not reachable from the start node.
Auto Trait Implementations§
impl<'graph, G: ?Sized> RefUnwindSafe for TriColorDepthFirstSearch<'graph, G>where
G: RefUnwindSafe,
<G as DirectedGraph>::Node: RefUnwindSafe,
impl<'graph, G: ?Sized> Send for TriColorDepthFirstSearch<'graph, G>where
G: Sync,
<G as DirectedGraph>::Node: Send,
impl<'graph, G: ?Sized> Sync for TriColorDepthFirstSearch<'graph, G>where
G: Sync,
<G as DirectedGraph>::Node: Sync,
impl<'graph, G: ?Sized> Unpin for TriColorDepthFirstSearch<'graph, G>where
<G as DirectedGraph>::Node: Unpin,
impl<'graph, G: ?Sized> UnwindSafe for TriColorDepthFirstSearch<'graph, G>where
G: RefUnwindSafe,
<G as DirectedGraph>::Node: UnwindSafe,
Blanket Implementations§
impl<'a, T> Captures<'a> for Twhere
T: ?Sized,
impl<T> Erased for T
Layout§
Note: Unable to compute type layout, possibly due to this type having generic parameters. Layout can only be computed for concrete, fully-instantiated types.