Module visitor 

Breadth-first and depth-first traversals, with Rust closures as visitors (igraph_visitor.h).

This module binds the three graph traversal functions of igraph’s Visitors chapter:

Rust method	C function	What you get
Graph::bfs	igraph_bfs	BfsResult: order, rank, parents, pred, succ, dist
Graph::bfs_with	igraph_bfs + igraph_bfshandler_t	same, calling a closure on every visited vertex (BfsVisit)
Graph::bfs_simple	igraph_bfs_simple	BfsSimpleResult: order, distance layers, parents
Graph::dfs	igraph_dfs	DfsResult: discovery and finishing orders, parents, dist
Graph::dfs_with	igraph_dfs + igraph_dfshandler_t (in and out)	same, calling a closure on every DfsEvent

Traversal parameters are grouped in BfsOptions and DfsOptions (edge direction to follow, whether to restart from unreachable vertices, and, for BFS, an optional restricted vertex set).

Visitors are closures

The callback variants accept any FnMut closure returning ControlFlow<()>: return ControlFlow::Continue(()) to go on, or ControlFlow::Break(()) to stop the traversal early. Stopping is not an error (it maps to igraph’s IGRAPH_STOP): the wrapper returns Ok with the partial results computed so far and sets the stopped flag of the result. If the closure panics, the traversal is aborted inside igraph (no unwinding crosses the FFI boundary) and the panic is then resumed in the calling Rust code.

Rusty results

Where igraph stores negative sentinels (-1 for “root”, -2 for “not visited”), the result structs use Options instead, and the visiting orders only contain the vertices that were actually reached (igraph pads them with -1).

Differences from the raw C functions

The bindings smooth over a few rough edges of src/graph/visitors.c, which are present in igraph 1.0.0 and 1.0.1 (the file is unchanged between the two releases):

• igraph_dfs reports a wrong depth to its out-callback (one less than the depth given at discovery) and, after a restart with unreachable, its depth counter is not reset: the roots of later trees still get depth 0, but the other vertices of the second tree get one less than their true depth, those of the third tree two less, and so on (the raw dist output can even become -1, the “not visited” sentinel). DfsEvent and DfsResult::dist carry the true depths, tracked on the Rust side.
• igraph_bfs with unreachable = true reads out of bounds on the null graph: the bindings answer that case without calling igraph.
• igraph_bfs_simple does not validate its root, and igraph_dfs reports an invalid root as IGRAPH_EINVAL: both methods check the root first and report ErrorKind::InvalidVertexId, like Graph::bfs.
• After an early stop, igraph_bfs has already assigned a parent to the vertices waiting in its queue; BfsResult::parents only describes the vertices that were actually visited.

See also

Many questions that can be answered with a hand-written traversal have a dedicated (and usually faster) function elsewhere in the crate:

• distances and shortest paths: Graph::distances, Graph::get_shortest_path, Graph::get_shortest_paths, Graph::eccentricity (all in crate::paths);
• reachability and components: Graph::subcomponent (the vertices a BFS from one root reaches), Graph::connected_components, Graph::neighborhood (vertices within a given number of hops);
• DAGs and cycles: Graph::topological_sorting, Graph::is_dag, Graph::find_cycle (in crate::cycles);
• trees: Graph::unfold_tree (unrolls a graph into a BFS tree), Graph::kary_tree and Graph::famous to build test inputs;
• low-level neighbor access for your own traversals: crate::adjlist.

Example

use igraph::prelude::*;
use igraph::visitor::{BfsOptions, DfsOptions};
use std::ops::ControlFlow;

// A small binary tree:      0
//                         /   \
//                        1     2
//                       / \   /
//                      3   4 5
let tree = Graph::kary_tree(6, 2, TreeMode::Undirected)?;

let bfs = tree.bfs(&[0], &BfsOptions::default())?;
assert_eq!(bfs.order, [0, 1, 2, 3, 4, 5]);
assert_eq!(bfs.dist, [Some(0), Some(1), Some(1), Some(2), Some(2), Some(2)]);
assert_eq!(bfs.path_to(5), Some(vec![0, 2, 5]));

let dfs = tree.dfs(0, &DfsOptions::default())?;
assert_eq!(dfs.order, [0, 1, 3, 4, 2, 5]);     // pre-order
assert_eq!(dfs.order_out, [3, 4, 1, 5, 2, 0]); // post-order

// Stop as soon as a vertex at distance 2 is found.
let mut first_deep = None;
let partial = tree.bfs_with(&[0], &BfsOptions::default(), |visit| {
    if visit.dist == 2 {
        first_deep = Some(visit.vid);
        return ControlFlow::Break(());
    }
    ControlFlow::Continue(())
})?;
assert_eq!(first_deep, Some(3));
assert!(partial.stopped);

// In an unweighted graph, BFS distances are shortest-path lengths.
let d = tree.distances(0, .., None, NeighborMode::All)?;
assert_eq!(d.to_rows()[0], [0.0, 1.0, 1.0, 2.0, 2.0, 2.0]);

Structs

BfsOptions

Parameters of a breadth-first search (Graph::bfs, Graph::bfs_with).

BfsResult

Results of a breadth-first search (Graph::bfs, Graph::bfs_with).

BfsSimpleResult

Results of Graph::bfs_simple.

BfsVisit

What a breadth-first search visitor sees each time a vertex is visited (the arguments of igraph’s igraph_bfshandler_t).

DfsOptions

Parameters of a depth-first search (Graph::dfs, Graph::dfs_with).

DfsResult

Results of a depth-first search (Graph::dfs, Graph::dfs_with).

Enums

DfsEvent

An event reported to a depth-first search visitor (Graph::dfs_with).