oxicuda_graphalg/repr/
adjacency_list.rs

1//! Adjacency-list graph representation.
2
3use crate::error::{GraphalgError, GraphalgResult};
4
5/// Unweighted graph stored as an adjacency list. Directed by default.
6#[derive(Debug, Clone)]
7pub struct AdjacencyList {
8    pub n: usize,
9    pub edges: Vec<Vec<usize>>,
10}
11
12impl AdjacencyList {
13    /// Create an empty graph with `n` nodes and no edges.
14    pub fn new(n: usize) -> Self {
15        Self {
16            n,
17            edges: vec![Vec::new(); n],
18        }
19    }
20
21    /// Add a directed edge `u -> v`. Returns error if endpoints are out of range.
22    pub fn add_edge(&mut self, u: usize, v: usize) -> GraphalgResult<()> {
23        if u >= self.n {
24            return Err(GraphalgError::IndexOutOfBounds {
25                index: u,
26                len: self.n,
27            });
28        }
29        if v >= self.n {
30            return Err(GraphalgError::IndexOutOfBounds {
31                index: v,
32                len: self.n,
33            });
34        }
35        self.edges[u].push(v);
36        Ok(())
37    }
38
39    /// Add an undirected edge `(u, v)`.
40    pub fn add_undirected_edge(&mut self, u: usize, v: usize) -> GraphalgResult<()> {
41        self.add_edge(u, v)?;
42        if u != v {
43            self.add_edge(v, u)?;
44        }
45        Ok(())
46    }
47
48    /// Total number of directed edges stored.
49    pub fn num_edges(&self) -> usize {
50        self.edges.iter().map(|adj| adj.len()).sum()
51    }
52
53    /// Out-neighbors of vertex `u`.
54    pub fn neighbors(&self, u: usize) -> GraphalgResult<&[usize]> {
55        if u >= self.n {
56            return Err(GraphalgError::IndexOutOfBounds {
57                index: u,
58                len: self.n,
59            });
60        }
61        Ok(&self.edges[u])
62    }
63
64    /// Compute the in-degree of each vertex.
65    pub fn in_degrees(&self) -> Vec<usize> {
66        let mut deg = vec![0usize; self.n];
67        for adj in &self.edges {
68            for &v in adj {
69                deg[v] += 1;
70            }
71        }
72        deg
73    }
74
75    /// Compute the out-degree of each vertex.
76    pub fn out_degrees(&self) -> Vec<usize> {
77        self.edges.iter().map(|adj| adj.len()).collect()
78    }
79
80    /// Return the reverse graph (reverse all directed edges).
81    pub fn reverse(&self) -> Self {
82        let mut rev = Self::new(self.n);
83        for (u, adj) in self.edges.iter().enumerate() {
84            for &v in adj {
85                rev.edges[v].push(u);
86            }
87        }
88        rev
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    #[test]
97    fn empty_graph() {
98        let g = AdjacencyList::new(5);
99        assert_eq!(g.n, 5);
100        assert_eq!(g.num_edges(), 0);
101    }
102
103    #[test]
104    fn add_directed_edges() {
105        let mut g = AdjacencyList::new(3);
106        g.add_edge(0, 1).expect("ok");
107        g.add_edge(1, 2).expect("ok");
108        assert_eq!(g.num_edges(), 2);
109    }
110
111    #[test]
112    fn add_undirected_edge_creates_two() {
113        let mut g = AdjacencyList::new(2);
114        g.add_undirected_edge(0, 1).expect("ok");
115        assert_eq!(g.num_edges(), 2);
116    }
117
118    #[test]
119    fn add_self_loop_undirected() {
120        let mut g = AdjacencyList::new(2);
121        g.add_undirected_edge(0, 0).expect("ok");
122        assert_eq!(g.num_edges(), 1);
123    }
124
125    #[test]
126    fn add_oob_errors() {
127        let mut g = AdjacencyList::new(3);
128        assert!(g.add_edge(3, 0).is_err());
129        assert!(g.add_edge(0, 5).is_err());
130    }
131
132    #[test]
133    fn degrees_consistent() {
134        let mut g = AdjacencyList::new(3);
135        g.add_edge(0, 1).expect("ok");
136        g.add_edge(0, 2).expect("ok");
137        g.add_edge(1, 2).expect("ok");
138        let out = g.out_degrees();
139        let in_d = g.in_degrees();
140        assert_eq!(out, vec![2, 1, 0]);
141        assert_eq!(in_d, vec![0, 1, 2]);
142    }
143
144    #[test]
145    fn reverse_graph() {
146        let mut g = AdjacencyList::new(3);
147        g.add_edge(0, 1).expect("ok");
148        g.add_edge(1, 2).expect("ok");
149        let r = g.reverse();
150        assert_eq!(r.neighbors(1).expect("ok"), &[0usize]);
151        assert_eq!(r.neighbors(2).expect("ok"), &[1usize]);
152    }
153}
oxicuda_graphalg/repr/adjacency_list.rs

oxicuda_graphalg/repr/
adjacency_list.rs
