use_graph_traversal/
lib.rs

1#![forbid(unsafe_code)]
2//! Primitive graph traversal helpers.
3//!
4//! The crate provides deterministic breadth-first and depth-first traversals
5//! that follow the existing adjacency list order.
6//!
7//! # Examples
8//!
9//! ```rust
10//! use use_graph_traversal::{breadth_first_order, connected_component, reachable};
11//!
12//! let adjacency = vec![vec![1, 2], vec![3], vec![], vec![]];
13//!
14//! assert_eq!(breadth_first_order(&adjacency, 0).unwrap(), vec![0, 1, 2, 3]);
15//! assert!(reachable(&adjacency, 0, 3).unwrap());
16//! assert_eq!(connected_component(&adjacency, 0).unwrap(), vec![0, 1, 2, 3]);
17//! ```
18
19use std::collections::VecDeque;
20
21#[derive(Debug, Clone, Copy, PartialEq, Eq)]
22pub enum TraversalError {
23    InvalidStartNode,
24    InvalidTargetNode,
25    InvalidNeighborIndex,
26}
27
28fn validate_start(adjacency: &[Vec<usize>], start: usize) -> Result<(), TraversalError> {
29    if start >= adjacency.len() {
30        Err(TraversalError::InvalidStartNode)
31    } else {
32        Ok(())
33    }
34}
35
36fn validate_target(adjacency: &[Vec<usize>], target: usize) -> Result<(), TraversalError> {
37    if target >= adjacency.len() {
38        Err(TraversalError::InvalidTargetNode)
39    } else {
40        Ok(())
41    }
42}
43
44fn validate_neighbor(adjacency: &[Vec<usize>], neighbor: usize) -> Result<(), TraversalError> {
45    if neighbor >= adjacency.len() {
46        Err(TraversalError::InvalidNeighborIndex)
47    } else {
48        Ok(())
49    }
50}
51
52pub fn breadth_first_order(
53    adjacency: &[Vec<usize>],
54    start: usize,
55) -> Result<Vec<usize>, TraversalError> {
56    validate_start(adjacency, start)?;
57
58    let mut visited = vec![false; adjacency.len()];
59    let mut queue = VecDeque::new();
60    let mut order = Vec::with_capacity(adjacency.len());
61
62    visited[start] = true;
63    queue.push_back(start);
64
65    while let Some(node) = queue.pop_front() {
66        order.push(node);
67
68        for &neighbor in &adjacency[node] {
69            validate_neighbor(adjacency, neighbor)?;
70
71            if !visited[neighbor] {
72                visited[neighbor] = true;
73                queue.push_back(neighbor);
74            }
75        }
76    }
77
78    Ok(order)
79}
80
81pub fn depth_first_order(
82    adjacency: &[Vec<usize>],
83    start: usize,
84) -> Result<Vec<usize>, TraversalError> {
85    validate_start(adjacency, start)?;
86
87    let mut visited = vec![false; adjacency.len()];
88    let mut stack = vec![start];
89    let mut order = Vec::with_capacity(adjacency.len());
90
91    while let Some(node) = stack.pop() {
92        if visited[node] {
93            continue;
94        }
95
96        visited[node] = true;
97        order.push(node);
98
99        for &neighbor in adjacency[node].iter().rev() {
100            validate_neighbor(adjacency, neighbor)?;
101
102            if !visited[neighbor] {
103                stack.push(neighbor);
104            }
105        }
106    }
107
108    Ok(order)
109}
110
111pub fn reachable(
112    adjacency: &[Vec<usize>],
113    start: usize,
114    target: usize,
115) -> Result<bool, TraversalError> {
116    validate_start(adjacency, start)?;
117    validate_target(adjacency, target)?;
118
119    if start == target {
120        return Ok(true);
121    }
122
123    let mut visited = vec![false; adjacency.len()];
124    let mut queue = VecDeque::new();
125
126    visited[start] = true;
127    queue.push_back(start);
128
129    while let Some(node) = queue.pop_front() {
130        for &neighbor in &adjacency[node] {
131            validate_neighbor(adjacency, neighbor)?;
132
133            if neighbor == target {
134                return Ok(true);
135            }
136
137            if !visited[neighbor] {
138                visited[neighbor] = true;
139                queue.push_back(neighbor);
140            }
141        }
142    }
143
144    Ok(false)
145}
146
147pub fn connected_component(
148    adjacency: &[Vec<usize>],
149    start: usize,
150) -> Result<Vec<usize>, TraversalError> {
151    breadth_first_order(adjacency, start)
152}
153
154#[cfg(test)]
155mod tests {
156    use super::{
157        breadth_first_order, connected_component, depth_first_order, reachable, TraversalError,
158    };
159
160    #[test]
161    fn performs_breadth_first_traversal() {
162        let adjacency = vec![vec![1, 2], vec![3], vec![3], vec![]];
163
164        assert_eq!(
165            breadth_first_order(&adjacency, 0).unwrap(),
166            vec![0, 1, 2, 3]
167        );
168    }
169
170    #[test]
171    fn performs_depth_first_traversal_in_adjacency_order() {
172        let adjacency = vec![vec![1, 2], vec![3], vec![], vec![]];
173
174        assert_eq!(depth_first_order(&adjacency, 0).unwrap(), vec![0, 1, 3, 2]);
175    }
176
177    #[test]
178    fn checks_reachability_and_connected_components() {
179        let adjacency = vec![vec![1], vec![2], vec![], vec![4], vec![]];
180
181        assert!(reachable(&adjacency, 0, 2).unwrap());
182        assert!(!reachable(&adjacency, 0, 4).unwrap());
183        assert_eq!(connected_component(&adjacency, 3).unwrap(), vec![3, 4]);
184    }
185
186    #[test]
187    fn rejects_invalid_indexes() {
188        let adjacency = vec![vec![1], vec![]];
189
190        assert_eq!(
191            breadth_first_order(&adjacency, 2),
192            Err(TraversalError::InvalidStartNode)
193        );
194        assert_eq!(
195            reachable(&adjacency, 0, 2),
196            Err(TraversalError::InvalidTargetNode)
197        );
198    }
199
200    #[test]
201    fn rejects_invalid_neighbor_indexes_in_input_adjacency() {
202        let adjacency = vec![vec![3], vec![]];
203
204        assert_eq!(
205            depth_first_order(&adjacency, 0),
206            Err(TraversalError::InvalidNeighborIndex)
207        );
208    }
209}
use_graph_traversal/lib.rs

use_graph_traversal/
lib.rs
