sim_lib_discrete_graph/
traversal.rs

1//! Deterministic breadth-first and depth-first traversal.
2
3use crate::error::GraphError;
4use crate::graph::Graph;
5use std::collections::VecDeque;
6
7/// The result of a traversal from a single start node.
8#[derive(Debug, Clone, PartialEq, Eq)]
9pub struct Traversal {
10    /// Nodes in the order they were first visited.
11    pub order: Vec<usize>,
12    /// `predecessor[v]` is the node `v` was discovered from (`None` for the
13    /// start node and for unreached nodes).
14    pub predecessor: Vec<Option<usize>>,
15}
16
17fn check_start<N, W>(graph: &Graph<N, W>, start: usize) -> Result<(), GraphError> {
18    if start >= graph.node_count() {
19        return Err(GraphError::NodeOutOfRange {
20            node: start,
21            count: graph.node_count(),
22        });
23    }
24    Ok(())
25}
26
27/// Breadth-first traversal from `start`. Neighbors are visited in ascending
28/// node order, so the result is deterministic.
29///
30/// # Examples
31///
32/// On the chain `0 -> 1 -> 2`, BFS from `0` visits the nodes in order and
33/// records each node's discovery predecessor:
34///
35/// ```
36/// use sim_lib_discrete_graph::{bfs, Directedness, Graph};
37///
38/// let mut g: Graph<(), ()> = Graph::with_nodes(vec![(), (), ()], Directedness::Directed);
39/// g.add_edge(0, 1, ()).unwrap();
40/// g.add_edge(1, 2, ()).unwrap();
41///
42/// let t = bfs(&g, 0).unwrap();
43/// assert_eq!(t.order, vec![0, 1, 2]);
44/// assert_eq!(t.predecessor, vec![None, Some(0), Some(1)]);
45/// ```
46pub fn bfs<N, W>(graph: &Graph<N, W>, start: usize) -> Result<Traversal, GraphError> {
47    check_start(graph, start)?;
48    let n = graph.node_count();
49    let mut visited = vec![false; n];
50    let mut predecessor = vec![None; n];
51    let mut order = Vec::new();
52    let mut queue = VecDeque::new();
53    visited[start] = true;
54    queue.push_back(start);
55    while let Some(u) = queue.pop_front() {
56        order.push(u);
57        for adj in graph.neighbors(u)? {
58            if !visited[adj.node] {
59                visited[adj.node] = true;
60                predecessor[adj.node] = Some(u);
61                queue.push_back(adj.node);
62            }
63        }
64    }
65    Ok(Traversal { order, predecessor })
66}
67
68/// Depth-first traversal from `start`. Neighbors are explored in ascending node
69/// order, so the result is deterministic.
70pub fn dfs<N, W>(graph: &Graph<N, W>, start: usize) -> Result<Traversal, GraphError> {
71    check_start(graph, start)?;
72    let n = graph.node_count();
73    let mut visited = vec![false; n];
74    let mut predecessor = vec![None; n];
75    let mut order = Vec::new();
76    // Explicit stack of (node, predecessor). Push neighbors in reverse so the
77    // smallest index is popped (and thus visited) first.
78    let mut stack = vec![(start, None)];
79    while let Some((u, pred)) = stack.pop() {
80        if visited[u] {
81            continue;
82        }
83        visited[u] = true;
84        predecessor[u] = pred;
85        order.push(u);
86        let neighbors = graph.neighbors(u)?;
87        for adj in neighbors.into_iter().rev() {
88            if !visited[adj.node] {
89                stack.push((adj.node, Some(u)));
90            }
91        }
92    }
93    Ok(Traversal { order, predecessor })
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99    use crate::edge::Directedness;
100
101    fn diamond() -> Graph<u8, u64> {
102        // 0 - 1, 0 - 2, 1 - 3, 2 - 3 (undirected diamond).
103        let mut g = Graph::with_nodes(vec![0, 1, 2, 3], Directedness::Undirected);
104        g.add_edge(0, 1, 1).unwrap();
105        g.add_edge(0, 2, 1).unwrap();
106        g.add_edge(1, 3, 1).unwrap();
107        g.add_edge(2, 3, 1).unwrap();
108        g
109    }
110
111    #[test]
112    fn bfs_is_deterministic() {
113        let t = bfs(&diamond(), 0).unwrap();
114        assert_eq!(t.order, vec![0, 1, 2, 3]);
115        assert_eq!(t.predecessor[3], Some(1)); // reached from the smaller branch
116    }
117
118    #[test]
119    fn dfs_is_deterministic() {
120        let t = dfs(&diamond(), 0).unwrap();
121        assert_eq!(t.order, vec![0, 1, 3, 2]);
122    }
123
124    #[test]
125    fn bad_start_fails() {
126        assert!(matches!(
127            bfs(&diamond(), 9),
128            Err(GraphError::NodeOutOfRange { node: 9, .. })
129        ));
130    }
131}
sim_lib_discrete_graph/traversal.rs

sim_lib_discrete_graph/
traversal.rs
