Function depth_first_search

pub fn depth_first_search<G, I, F, C>(graph: G, starts: I, visitor: F) -> C
where
    G: IntoEdges + Visitable,
    I: IntoIterator<Item = G::NodeId>,
    F: FnMut(DfsEvent<G::NodeId, &G::EdgeWeight>) -> C,
    C: ControlFlow,

An iterative depth first search.

It is an iterative implementation of the upstream petgraph depth_first_search function.

Starting points are the nodes in the iterator starts (specify just one start vertex x by using Some(x)).

The traversal emits discovery and finish events for each reachable vertex, and edge classification of each reachable edge. visitor is called for each event, see petgraph::DfsEvent for possible values.

The return value should implement the trait ControlFlow, and can be used to change the control flow of the search.

Control Implements ControlFlow such that Control::Continue resumes the search. Control::Break will stop the visit early, returning the contained value. Control::Prune will stop traversing any additional edges from the current node and proceed immediately to the Finish event.

There are implementations of ControlFlow for (), and Result<C, E> where C: ControlFlow. The implementation for () will continue until finished. For Result, upon encountering an E it will break, otherwise acting the same as C.

*Panics if you attempt to prune a node from its Finish event.

Pseudo-code for the DFS algorithm is listed below, with the annotated event points, for which the given visitor object will be called with the appropriate method.

// G - graph, s - single source node
DFS(G, s)
  let color be a mapping                        // color[u] - vertex u color WHITE/GRAY/BLACK
  for each u in G                               // u - vertex in G
    color[u] := WHITE                           // color all as undiscovered
  end for
  time := 0
  let S be a stack
  PUSH(S, (s, iterator of OutEdges(G, s)))      // S - stack of vertices and edge iterators
  color[s] := GRAY                              // event: Discover(s, time)
  while (S is not empty)
    let (u, iterator) := LAST(S)
    flag := False                               // whether edge to undiscovered vertex found
    for each v, w in iterator                   // v - target vertex, w - edge weight
      if (WHITE = color[v])                     // event: TreeEdge(u, v, w)
        time := time + 1
        color[v] := GRAY                        // event: Discover(v, time)
        flag := True
        break
      elif (GRAY = color[v])                    // event: BackEdge(u, v, w)
        ...
      elif (BLACK = color[v])                   // event: CrossForwardEdge(u, v, w)
        ...
    end for
    if (flag is True)
      PUSH(S, (v, iterator of OutEdges(G, v)))
    elif (flag is False)
      time := time + 1
      color[u] := BLACK                         // event: Finish(u, time)
      POP(S)
  end while

Example returning Control.

Find a path from vertex 0 to 5, and exit the visit as soon as we reach the goal vertex.

use rustworkx_core::petgraph::prelude::*;
use rustworkx_core::petgraph::graph::node_index as n;
use rustworkx_core::petgraph::visit::Control;

use rustworkx_core::traversal::{DfsEvent, depth_first_search};

let gr: Graph<(), ()> = Graph::from_edges(&[
    (0, 1), (0, 2), (0, 3),
    (1, 3),
    (2, 3), (2, 4),
    (4, 0), (4, 5),
]);

// record each predecessor, mapping node → node
let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
let start = n(0);
let goal = n(5);
depth_first_search(&gr, Some(start), |event| {
    if let DfsEvent::TreeEdge(u, v, _) = event {
        predecessor[v.index()] = u;
        if v == goal {
            return Control::Break(v);
        }
    }
    Control::Continue
});

let mut next = goal;
let mut path = vec![next];
while next != start {
    let pred = predecessor[next.index()];
    path.push(pred);
    next = pred;
}
path.reverse();
assert_eq!(&path, &[n(0), n(2), n(4), n(5)]);

Example returning a Result.

use rustworkx_core::petgraph::graph::node_index as n;
use rustworkx_core::petgraph::prelude::*;
use rustworkx_core::petgraph::visit::Time;

use rustworkx_core::traversal::{DfsEvent, depth_first_search};

let gr: Graph<(), ()> = Graph::from_edges(&[(0, 1), (1, 2), (1, 1), (2, 1)]);
let start = n(0);
let mut back_edges = 0;
let mut discover_time = 0;

#[derive(Debug)]
struct BackEdgeFound {
    source: NodeIndex,
    target: NodeIndex,
}

// Stop the search, the first time a BackEdge is encountered.
let result = depth_first_search(&gr, Some(start), |event| {
    match event {
        // In the cases where Ok(()) is returned,
        // Result falls back to the implementation of Control on the value ().
        // In the case of (), this is to always return Control::Continue.
        // continuing the search.
        DfsEvent::Discover(_, Time(t)) => {
            discover_time = t;
            Ok(())
        }
        DfsEvent::BackEdge(u, v, _) => {
            back_edges += 1;
            // the implementation of ControlFlow for Result,
            // treats this Err value as Continue::Break
            Err(BackEdgeFound {source: u, target: v})
        }
        _ => Ok(()),
    }
});

// Even though the graph has more than one cycle,
// The number of back_edges visited by the search should always be 1.
assert_eq!(back_edges, 1);
println!("discover time:{:?}", discover_time);
println!("number of backedges encountered: {}", back_edges);
println!("back edge: ({:?})", result.unwrap_err());