oxicuda_graphalg/repr/
csr_graph.rs

1//! Compressed Sparse Row graph representation.
2
3use crate::error::{GraphalgError, GraphalgResult};
4use crate::repr::adjacency_list::AdjacencyList;
5
6/// CSR-formatted directed graph: `row_ptr` of length `n+1` and `col_idx` of length `m`.
7#[derive(Debug, Clone)]
8pub struct CsrGraph {
9    pub n: usize,
10    pub row_ptr: Vec<usize>,
11    pub col_idx: Vec<usize>,
12}
13
14impl CsrGraph {
15    /// Create an empty CSR graph with `n` nodes and no edges.
16    pub fn new(n: usize) -> Self {
17        Self {
18            n,
19            row_ptr: vec![0; n + 1],
20            col_idx: Vec::new(),
21        }
22    }
23
24    /// Build a CSR graph from an [`AdjacencyList`].
25    pub fn from_adjacency_list(adj: &AdjacencyList) -> Self {
26        let n = adj.n;
27        let mut row_ptr = vec![0usize; n + 1];
28        for (u, neigh) in adj.edges.iter().enumerate() {
29            row_ptr[u + 1] = row_ptr[u] + neigh.len();
30        }
31        let m = row_ptr[n];
32        let mut col_idx = Vec::with_capacity(m);
33        for neigh in &adj.edges {
34            for &v in neigh {
35                col_idx.push(v);
36            }
37        }
38        Self {
39            n,
40            row_ptr,
41            col_idx,
42        }
43    }
44
45    /// Number of directed edges.
46    pub fn num_edges(&self) -> usize {
47        self.col_idx.len()
48    }
49
50    /// Neighbors of vertex `u` in this CSR graph.
51    pub fn neighbors(&self, u: usize) -> GraphalgResult<&[usize]> {
52        if u >= self.n {
53            return Err(GraphalgError::IndexOutOfBounds {
54                index: u,
55                len: self.n,
56            });
57        }
58        let start = self.row_ptr[u];
59        let end = self.row_ptr[u + 1];
60        Ok(&self.col_idx[start..end])
61    }
62}
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn csr_from_adj() {
70        let mut adj = AdjacencyList::new(3);
71        adj.add_edge(0, 1).expect("ok");
72        adj.add_edge(0, 2).expect("ok");
73        adj.add_edge(2, 1).expect("ok");
74        let csr = CsrGraph::from_adjacency_list(&adj);
75        assert_eq!(csr.num_edges(), 3);
76        assert_eq!(csr.row_ptr, vec![0, 2, 2, 3]);
77        let n0 = csr.neighbors(0).expect("ok");
78        assert_eq!(n0, &[1, 2]);
79    }
80}
oxicuda_graphalg/repr/csr_graph.rs

oxicuda_graphalg/repr/
csr_graph.rs
