oxicuda_graphalg/dynamic/
dynamic_graph.rs

1//! A mutable directed graph supporting incremental edge insertion and deletion.
2//!
3//! [`DynamicGraph`] is the substrate for the streaming-update algorithms in this
4//! module (incremental PageRank, incremental SCC). Unlike the immutable
5//! [`AdjacencyList`], it maintains
6//! **both** the forward and reverse adjacency in lock-step and tracks the
7//! *multiplicity* of every ordered pair so that `remove_edge` has well-defined
8//! semantics on multigraphs: inserting a pair twice and removing it once leaves
9//! the edge present with multiplicity one.
10//!
11//! The structure is deliberately a thin, allocation-light wrapper: out- and
12//! in-neighbour lists are kept de-duplicated (one entry per distinct neighbour)
13//! with the parallel multiplicity stored alongside, so neighbour iteration is
14//! `O(deg)` and degree queries are `O(1)`-amortised.
15
16use std::collections::HashMap;
17
18use crate::error::{GraphalgError, GraphalgResult};
19use crate::repr::adjacency_list::AdjacencyList;
20
21/// Mutable directed graph with incremental add/remove and a reverse index.
22#[derive(Debug, Clone)]
23pub struct DynamicGraph {
24    n: usize,
25    /// Distinct out-neighbours of each vertex (de-duplicated).
26    out_adj: Vec<Vec<usize>>,
27    /// Distinct in-neighbours of each vertex (de-duplicated).
28    in_adj: Vec<Vec<usize>>,
29    /// Multiplicity of each present ordered pair `(u, v)`.
30    mult: HashMap<(usize, usize), u32>,
31}
32
33impl DynamicGraph {
34    /// Create an edgeless dynamic graph on `n` vertices.
35    pub fn new(n: usize) -> Self {
36        Self {
37            n,
38            out_adj: vec![Vec::new(); n],
39            in_adj: vec![Vec::new(); n],
40            mult: HashMap::new(),
41        }
42    }
43
44    /// Build a dynamic graph from a static [`AdjacencyList`] (directed).
45    ///
46    /// Parallel edges in the source list increment the multiplicity.
47    pub fn from_adjacency_list(g: &AdjacencyList) -> GraphalgResult<Self> {
48        let mut dg = Self::new(g.n);
49        for u in 0..g.n {
50            for &v in g.neighbors(u)? {
51                dg.add_edge(u, v)?;
52            }
53        }
54        Ok(dg)
55    }
56
57    /// Number of vertices.
58    pub fn num_nodes(&self) -> usize {
59        self.n
60    }
61
62    /// Number of *distinct* directed edges (ignoring multiplicity).
63    pub fn num_distinct_edges(&self) -> usize {
64        self.mult.len()
65    }
66
67    /// Total number of directed edges counting multiplicity.
68    pub fn num_edges(&self) -> usize {
69        self.mult.values().map(|&m| m as usize).sum()
70    }
71
72    /// Out-neighbours of `u` (distinct, unsorted).
73    pub fn out_neighbors(&self, u: usize) -> GraphalgResult<&[usize]> {
74        self.check(u)?;
75        Ok(&self.out_adj[u])
76    }
77
78    /// In-neighbours of `u` (distinct, unsorted).
79    pub fn in_neighbors(&self, u: usize) -> GraphalgResult<&[usize]> {
80        self.check(u)?;
81        Ok(&self.in_adj[u])
82    }
83
84    /// Out-degree of `u` counting multiplicity.
85    pub fn out_degree(&self, u: usize) -> GraphalgResult<usize> {
86        self.check(u)?;
87        let mut d = 0usize;
88        for &v in &self.out_adj[u] {
89            d += *self.mult.get(&(u, v)).unwrap_or(&0) as usize;
90        }
91        Ok(d)
92    }
93
94    /// Multiplicity of the ordered pair `(u, v)` (zero if absent).
95    pub fn edge_multiplicity(&self, u: usize, v: usize) -> u32 {
96        *self.mult.get(&(u, v)).unwrap_or(&0)
97    }
98
99    /// Whether the directed edge `u -> v` is present.
100    pub fn has_edge(&self, u: usize, v: usize) -> bool {
101        self.mult.contains_key(&(u, v))
102    }
103
104    /// Insert a directed edge `u -> v`, incrementing multiplicity.
105    ///
106    /// Returns `true` if this introduced a *new* distinct edge (the pair was not
107    /// previously present), `false` if it only bumped an existing multiplicity.
108    pub fn add_edge(&mut self, u: usize, v: usize) -> GraphalgResult<bool> {
109        self.check(u)?;
110        self.check(v)?;
111        let entry = self.mult.entry((u, v)).or_insert(0);
112        let was_new = *entry == 0;
113        *entry += 1;
114        if was_new {
115            self.out_adj[u].push(v);
116            self.in_adj[v].push(u);
117        }
118        Ok(was_new)
119    }
120
121    /// Remove one unit of multiplicity from the directed edge `u -> v`.
122    ///
123    /// Returns `true` if the distinct edge was *fully* removed (multiplicity hit
124    /// zero), `false` if it merely decremented. Errors with [`GraphalgError::NoSolution`]
125    /// when the edge is absent.
126    pub fn remove_edge(&mut self, u: usize, v: usize) -> GraphalgResult<bool> {
127        self.check(u)?;
128        self.check(v)?;
129        match self.mult.get_mut(&(u, v)) {
130            None => Err(GraphalgError::NoSolution(format!(
131                "edge ({u},{v}) is not present and cannot be removed"
132            ))),
133            Some(m) => {
134                *m -= 1;
135                if *m == 0 {
136                    self.mult.remove(&(u, v));
137                    remove_first(&mut self.out_adj[u], v);
138                    remove_first(&mut self.in_adj[v], u);
139                    Ok(true)
140                } else {
141                    Ok(false)
142                }
143            }
144        }
145    }
146
147    /// Materialise the current state as a static [`AdjacencyList`], expanding
148    /// each pair to its multiplicity (so parallel edges reappear).
149    pub fn to_adjacency_list(&self) -> AdjacencyList {
150        let mut g = AdjacencyList::new(self.n);
151        for u in 0..self.n {
152            for &v in &self.out_adj[u] {
153                let m = *self.mult.get(&(u, v)).unwrap_or(&0);
154                for _ in 0..m {
155                    g.edges[u].push(v);
156                }
157            }
158        }
159        g
160    }
161
162    fn check(&self, u: usize) -> GraphalgResult<()> {
163        if u >= self.n {
164            return Err(GraphalgError::IndexOutOfBounds {
165                index: u,
166                len: self.n,
167            });
168        }
169        Ok(())
170    }
171}
172
173/// Remove the first occurrence of `target` from `vec` (swap-remove, order-free).
174fn remove_first(vec: &mut Vec<usize>, target: usize) {
175    if let Some(pos) = vec.iter().position(|&x| x == target) {
176        vec.swap_remove(pos);
177    }
178}
179
180#[cfg(test)]
181mod tests {
182    use super::*;
183
184    #[test]
185    fn add_remove_round_trip() {
186        let mut g = DynamicGraph::new(3);
187        assert!(g.add_edge(0, 1).expect("add"));
188        assert!(g.add_edge(1, 2).expect("add"));
189        assert!(!g.add_edge(0, 1).expect("add"), "second add is not new");
190        assert_eq!(g.num_distinct_edges(), 2);
191        assert_eq!(g.num_edges(), 3);
192        assert_eq!(g.edge_multiplicity(0, 1), 2);
193
194        // first remove only decrements
195        assert!(!g.remove_edge(0, 1).expect("rm"));
196        assert!(g.has_edge(0, 1));
197        // second fully removes
198        assert!(g.remove_edge(0, 1).expect("rm"));
199        assert!(!g.has_edge(0, 1));
200        assert_eq!(g.num_distinct_edges(), 1);
201    }
202
203    #[test]
204    fn reverse_index_consistent() {
205        let mut g = DynamicGraph::new(4);
206        g.add_edge(0, 2).expect("add");
207        g.add_edge(1, 2).expect("add");
208        g.add_edge(3, 2).expect("add");
209        let mut ins = g.in_neighbors(2).expect("in").to_vec();
210        ins.sort_unstable();
211        assert_eq!(ins, vec![0, 1, 3]);
212        g.remove_edge(1, 2).expect("rm");
213        let mut ins2 = g.in_neighbors(2).expect("in").to_vec();
214        ins2.sort_unstable();
215        assert_eq!(ins2, vec![0, 3]);
216        assert_eq!(g.out_neighbors(1).expect("out"), &[] as &[usize]);
217    }
218
219    #[test]
220    fn out_degree_counts_multiplicity() {
221        let mut g = DynamicGraph::new(2);
222        g.add_edge(0, 1).expect("add");
223        g.add_edge(0, 1).expect("add");
224        g.add_edge(0, 1).expect("add");
225        assert_eq!(g.out_degree(0).expect("deg"), 3);
226        // distinct out-neighbours is still one entry
227        assert_eq!(g.out_neighbors(0).expect("out").len(), 1);
228    }
229
230    #[test]
231    fn remove_absent_errors() {
232        let mut g = DynamicGraph::new(2);
233        assert!(g.remove_edge(0, 1).is_err());
234    }
235
236    #[test]
237    fn out_of_range_errors() {
238        let mut g = DynamicGraph::new(2);
239        assert!(g.add_edge(0, 5).is_err());
240        assert!(g.out_neighbors(9).is_err());
241    }
242
243    #[test]
244    fn round_trip_through_adjacency_list() {
245        let mut src = AdjacencyList::new(3);
246        src.add_edge(0, 1).expect("e");
247        src.add_edge(0, 1).expect("e"); // parallel
248        src.add_edge(1, 2).expect("e");
249        let dg = DynamicGraph::from_adjacency_list(&src).expect("build");
250        assert_eq!(dg.edge_multiplicity(0, 1), 2);
251        let back = dg.to_adjacency_list();
252        assert_eq!(back.num_edges(), 3);
253        assert_eq!(back.out_degrees(), vec![2, 1, 0]);
254    }
255}
oxicuda_graphalg/dynamic/dynamic_graph.rs

oxicuda_graphalg/dynamic/
dynamic_graph.rs
