Function dfs_edges

pub fn dfs_edges<G>(graph: G, source: Option<G::NodeId>) -> Vec<(usize, usize)>
where
    G: IntoNodeIdentifiers + NodeIndexable + IntoNeighbors + NodeCount + EdgeCount + Visitable,
    G::NodeId: Eq + Hash,

Return an edge list of the tree edges from a depth-first traversal.

The pseudo-code for the DFS algorithm is listed below. The output contains the tree edges found by the procedure.

DFS(G, v)
  let S be a stack
  label v as discovered
  PUSH(S, (v, iterator of G.neighbors(v)))
  while (S != Ø)
      let (v, iterator) := LAST(S)
      if hasNext(iterator) then
          w := next(iterator)
          if w is not labeled as discovered then
              label w as discovered                   # (v, w) is a tree edge
              PUSH(S, (w, iterator of G.neighbors(w)))
      else
          POP(S)
  end while

Arguments:

• graph - the graph to run on
• source - the optional node index to use as the starting node for the depth-first search. If specified the edge list will only return edges in the components reachable from this index. If this is not specified then a source will be chosen arbitrarily and repeated until all components of the graph are searched

Example

use rustworkx_core::petgraph;
use rustworkx_core::traversal::dfs_edges;

let g = petgraph::graph::UnGraph::<i32, ()>::from_edges(&[
    (0, 1), (1, 2), (1, 3), (2, 4), (3, 4)
]);
let dfs_edges = dfs_edges(&g, Some(petgraph::graph::NodeIndex::new(0)));
assert_eq!(vec![(0, 1), (1, 2), (2, 4), (4, 3)], dfs_edges);