`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,

source#### pub 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

source### impl<T> BorrowMut<T> for T where

T: ?Sized,

### impl<T> BorrowMut<T> for T where

T: ?Sized,

const: unstable · source#### fn borrow_mut(&mut self) -> &mut T

#### fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more

### impl<'a, T> Captures<'a> for T where

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.