use_adjacency/
lib.rs

1#![forbid(unsafe_code)]
2//! Primitive adjacency list helpers.
3//!
4//! The crate provides small builders for directed and undirected adjacency
5//! lists plus basic neighbor and degree queries.
6//!
7//! # Examples
8//!
9//! ```rust
10//! use use_adjacency::{build_directed_adjacency, degree, has_edge, neighbors};
11//!
12//! let adjacency = build_directed_adjacency(3, &[(0, 1), (0, 2)]).unwrap();
13//!
14//! assert_eq!(neighbors(&adjacency, 0), Some(&[1, 2][..]));
15//! assert_eq!(degree(&adjacency, 0), Some(2));
16//! assert!(has_edge(&adjacency, 0, 2));
17//! ```
18
19pub type AdjacencyList = Vec<Vec<usize>>;
20
21#[derive(Debug, Clone, Copy, PartialEq, Eq)]
22pub enum AdjacencyError {
23    InvalidNodeIndex,
24}
25
26fn validate_edge(node_count: usize, source: usize, target: usize) -> Result<(), AdjacencyError> {
27    if source >= node_count || target >= node_count {
28        Err(AdjacencyError::InvalidNodeIndex)
29    } else {
30        Ok(())
31    }
32}
33
34pub fn build_directed_adjacency(
35    node_count: usize,
36    edges: &[(usize, usize)],
37) -> Result<AdjacencyList, AdjacencyError> {
38    let mut adjacency = vec![Vec::new(); node_count];
39
40    for &(source, target) in edges {
41        validate_edge(node_count, source, target)?;
42        adjacency[source].push(target);
43    }
44
45    Ok(adjacency)
46}
47
48pub fn build_undirected_adjacency(
49    node_count: usize,
50    edges: &[(usize, usize)],
51) -> Result<AdjacencyList, AdjacencyError> {
52    let mut adjacency = vec![Vec::new(); node_count];
53
54    for &(source, target) in edges {
55        validate_edge(node_count, source, target)?;
56        adjacency[source].push(target);
57
58        if source != target {
59            adjacency[target].push(source);
60        }
61    }
62
63    Ok(adjacency)
64}
65
66#[must_use]
67pub fn neighbors(adjacency: &AdjacencyList, node: usize) -> Option<&[usize]> {
68    adjacency.get(node).map(Vec::as_slice)
69}
70
71#[must_use]
72pub fn degree(adjacency: &AdjacencyList, node: usize) -> Option<usize> {
73    adjacency.get(node).map(Vec::len)
74}
75
76#[must_use]
77pub fn has_edge(adjacency: &AdjacencyList, source: usize, target: usize) -> bool {
78    adjacency
79        .get(source)
80        .is_some_and(|targets| targets.contains(&target))
81}
82
83#[cfg(test)]
84mod tests {
85    use super::{
86        build_directed_adjacency, build_undirected_adjacency, degree, has_edge, neighbors,
87        AdjacencyError,
88    };
89
90    #[test]
91    fn builds_directed_adjacency() {
92        let adjacency = build_directed_adjacency(3, &[(0, 1), (0, 2), (1, 2)]).unwrap();
93
94        assert_eq!(neighbors(&adjacency, 0), Some(&[1, 2][..]));
95        assert_eq!(degree(&adjacency, 0), Some(2));
96        assert!(has_edge(&adjacency, 1, 2));
97        assert!(!has_edge(&adjacency, 2, 1));
98    }
99
100    #[test]
101    fn builds_undirected_adjacency_and_preserves_duplicates() {
102        let adjacency = build_undirected_adjacency(3, &[(0, 1), (1, 2), (0, 1)]).unwrap();
103
104        assert_eq!(neighbors(&adjacency, 0), Some(&[1, 1][..]));
105        assert_eq!(neighbors(&adjacency, 1), Some(&[0, 2, 0][..]));
106        assert!(has_edge(&adjacency, 2, 1));
107    }
108
109    #[test]
110    fn handles_self_loops_and_empty_graphs() {
111        let adjacency = build_undirected_adjacency(1, &[(0, 0)]).unwrap();
112
113        assert_eq!(neighbors(&adjacency, 0), Some(&[0][..]));
114        assert_eq!(
115            build_directed_adjacency(0, &[]).unwrap(),
116            Vec::<Vec<usize>>::new()
117        );
118    }
119
120    #[test]
121    fn rejects_invalid_node_indexes() {
122        assert_eq!(
123            build_directed_adjacency(2, &[(0, 2)]),
124            Err(AdjacencyError::InvalidNodeIndex)
125        );
126        assert_eq!(
127            build_undirected_adjacency(2, &[(3, 1)]),
128            Err(AdjacencyError::InvalidNodeIndex)
129        );
130    }
131}
use_adjacency/lib.rs

use_adjacency/
lib.rs
