oxicuda_graphalg/repr/
adjacency_matrix.rs

1//! Adjacency-matrix graph representation (row-major boolean).
2
3use crate::error::{GraphalgError, GraphalgResult};
4
5/// Unweighted graph stored as a dense row-major boolean matrix.
6#[derive(Debug, Clone)]
7pub struct AdjacencyMatrix {
8    pub n: usize,
9    pub mat: Vec<bool>,
10}
11
12impl AdjacencyMatrix {
13    /// Create an empty (all-false) matrix with `n` nodes.
14    pub fn new(n: usize) -> Self {
15        Self {
16            n,
17            mat: vec![false; n * n],
18        }
19    }
20
21    fn check_index(&self, u: usize, v: usize) -> GraphalgResult<()> {
22        if u >= self.n {
23            return Err(GraphalgError::IndexOutOfBounds {
24                index: u,
25                len: self.n,
26            });
27        }
28        if v >= self.n {
29            return Err(GraphalgError::IndexOutOfBounds {
30                index: v,
31                len: self.n,
32            });
33        }
34        Ok(())
35    }
36
37    /// Set the directed edge `u -> v` to `value`.
38    pub fn set(&mut self, u: usize, v: usize, value: bool) -> GraphalgResult<()> {
39        self.check_index(u, v)?;
40        self.mat[u * self.n + v] = value;
41        Ok(())
42    }
43
44    /// Add directed edge `u -> v`.
45    pub fn add_edge(&mut self, u: usize, v: usize) -> GraphalgResult<()> {
46        self.set(u, v, true)
47    }
48
49    /// Add an undirected edge `(u, v)`.
50    pub fn add_undirected_edge(&mut self, u: usize, v: usize) -> GraphalgResult<()> {
51        self.set(u, v, true)?;
52        self.set(v, u, true)?;
53        Ok(())
54    }
55
56    /// Get the value of the directed edge `u -> v`.
57    pub fn has_edge(&self, u: usize, v: usize) -> GraphalgResult<bool> {
58        self.check_index(u, v)?;
59        Ok(self.mat[u * self.n + v])
60    }
61
62    /// Number of directed edges (true entries).
63    pub fn num_edges(&self) -> usize {
64        self.mat.iter().filter(|x| **x).count()
65    }
66}
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    #[test]
73    fn empty_matrix() {
74        let m = AdjacencyMatrix::new(4);
75        assert_eq!(m.num_edges(), 0);
76    }
77
78    #[test]
79    fn set_and_get() {
80        let mut m = AdjacencyMatrix::new(3);
81        m.add_edge(0, 1).expect("ok");
82        assert!(m.has_edge(0, 1).expect("ok"));
83        assert!(!m.has_edge(1, 0).expect("ok"));
84    }
85
86    #[test]
87    fn undirected_symmetric() {
88        let mut m = AdjacencyMatrix::new(3);
89        m.add_undirected_edge(0, 2).expect("ok");
90        assert!(m.has_edge(0, 2).expect("ok"));
91        assert!(m.has_edge(2, 0).expect("ok"));
92    }
93}
oxicuda_graphalg/repr/adjacency_matrix.rs

oxicuda_graphalg/repr/
adjacency_matrix.rs
