rust_igraph/core/
graph.rs

1//! Minimal `Graph` for the Phase 0 walking skeleton.
2//!
3//! Only undirected, unweighted graphs with `u32` vertex ids. Adjacency stored as
4//! `Vec<Vec<u32>>`. This will be replaced by the full `igraph_t`-equivalent
5//! structure in Phase 1 (see `ALGO-CORE-001`); the public surface kept here is
6//! the strict subset that `bfs`, `read_edgelist`, and the oracle tests need.
7
8use super::error::{IgraphError, IgraphResult};
9
10/// Vertex id. Phase 0 fixes this to `u32`; Phase 1 may switch to a generic
11/// integer type behind a feature flag. See plan §3.3.
12pub type VertexId = u32;
13
14/// Undirected, unweighted graph backed by an adjacency list.
15#[derive(Debug, Clone, Default)]
16pub struct Graph {
17    n: u32,
18    out_neighbors: Vec<Vec<VertexId>>,
19    edge_count: usize,
20}
21
22impl Graph {
23    /// Construct an empty graph on `n` vertices and no edges.
24    pub fn with_vertices(n: u32) -> Self {
25        Self {
26            n,
27            out_neighbors: vec![Vec::new(); n as usize],
28            edge_count: 0,
29        }
30    }
31
32    /// Number of vertices. Counterpart of `igraph_vcount()`.
33    pub fn vcount(&self) -> u32 {
34        self.n
35    }
36
37    /// Number of edges. Counterpart of `igraph_ecount()`.
38    pub fn ecount(&self) -> usize {
39        self.edge_count
40    }
41
42    /// Append `count` new isolated vertices, returning the id range
43    /// `(first, last_inclusive)` of the new vertices.
44    pub fn add_vertices(&mut self, count: u32) -> (VertexId, VertexId) {
45        let first = self.n;
46        self.n = self.n.checked_add(count).expect("vertex count overflow");
47        self.out_neighbors.resize(self.n as usize, Vec::new());
48        (first, self.n.saturating_sub(1))
49    }
50
51    /// Add a single undirected edge between `u` and `v`.
52    ///
53    /// Self-loops are allowed (added once); parallel edges are allowed.
54    pub fn add_edge(&mut self, u: VertexId, v: VertexId) -> IgraphResult<()> {
55        self.check_vertex(u)?;
56        self.check_vertex(v)?;
57        self.out_neighbors[u as usize].push(v);
58        if u != v {
59            self.out_neighbors[v as usize].push(u);
60        }
61        self.edge_count += 1;
62        Ok(())
63    }
64
65    /// Add a sequence of undirected edges.
66    pub fn add_edges<I>(&mut self, edges: I) -> IgraphResult<()>
67    where
68        I: IntoIterator<Item = (VertexId, VertexId)>,
69    {
70        for (u, v) in edges {
71            self.add_edge(u, v)?;
72        }
73        Ok(())
74    }
75
76    /// Neighbors of `v`. Order is insertion order.
77    pub fn neighbors(&self, v: VertexId) -> IgraphResult<&[VertexId]> {
78        self.check_vertex(v)?;
79        Ok(&self.out_neighbors[v as usize])
80    }
81
82    /// Degree of `v` (counting self-loops once each, parallel edges separately).
83    pub fn degree(&self, v: VertexId) -> IgraphResult<usize> {
84        self.check_vertex(v)?;
85        Ok(self.out_neighbors[v as usize].len())
86    }
87
88    fn check_vertex(&self, v: VertexId) -> IgraphResult<()> {
89        if v >= self.n {
90            return Err(IgraphError::VertexOutOfRange { id: v, n: self.n });
91        }
92        Ok(())
93    }
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99
100    #[test]
101    fn empty_graph_counts() {
102        let g = Graph::with_vertices(0);
103        assert_eq!(g.vcount(), 0);
104        assert_eq!(g.ecount(), 0);
105    }
106
107    #[test]
108    fn add_vertices_then_edges() {
109        let mut g = Graph::with_vertices(3);
110        g.add_edge(0, 1).unwrap();
111        g.add_edge(1, 2).unwrap();
112        assert_eq!(g.vcount(), 3);
113        assert_eq!(g.ecount(), 2);
114        assert_eq!(g.degree(1).unwrap(), 2);
115        assert_eq!(g.neighbors(1).unwrap(), &[0, 2]);
116    }
117
118    #[test]
119    fn out_of_range_vertex_errors() {
120        let mut g = Graph::with_vertices(2);
121        let err = g.add_edge(0, 5).unwrap_err();
122        assert!(matches!(err, IgraphError::VertexOutOfRange { id: 5, n: 2 }));
123    }
124
125    #[test]
126    fn self_loop_counted_once_per_endpoint() {
127        let mut g = Graph::with_vertices(1);
128        g.add_edge(0, 0).unwrap();
129        assert_eq!(g.ecount(), 1);
130        assert_eq!(g.neighbors(0).unwrap(), &[0]);
131    }
132}
rust_igraph/core/graph.rs

rust_igraph/core/
graph.rs
