toolbox_rs/
dynamic_graph.rs

1/// Text book implementation of a dynamic graph data structure based on
2/// adjacency arrays. Nodes record their degree and edge slices are moved to
3/// the end of the edge array if there is insufficient space  when adding an
4/// edge.
5use crate::{
6    edge::{Edge, EdgeData},
7    graph::{EdgeArrayEntry, EdgeID, Graph, NodeID, INVALID_NODE_ID},
8};
9use core::ops::Range;
10
11pub struct NodeArrayEntry {
12    pub first_edge: EdgeID,
13    pub edge_count: usize,
14}
15
16impl NodeArrayEntry {
17    pub fn new(first_edge: EdgeID) -> NodeArrayEntry {
18        NodeArrayEntry {
19            first_edge,
20            edge_count: 0,
21        }
22    }
23
24    /// Get index past the end of the edge slice
25    pub fn slice_end(&self) -> EdgeID {
26        self.edge_count + self.first_edge
27    }
28}
29
30const GROWTH_FACTOR: f64 = 1.1;
31
32pub struct DynamicGraph<T: Clone> {
33    node_array: Vec<NodeArrayEntry>,
34    edge_array: Vec<EdgeArrayEntry<T>>,
35
36    number_of_nodes: usize,
37    number_of_edges: usize,
38}
39
40impl<T: Clone + Copy> Default for DynamicGraph<T> {
41    fn default() -> Self {
42        Self {
43            node_array: Vec::new(),
44            edge_array: Vec::new(),
45
46            number_of_nodes: 0,
47            number_of_edges: 0,
48        }
49    }
50}
51
52impl<T: Clone + Copy> DynamicGraph<T> {
53    /// In time O(V+E) check that the following invariants hold:
54    /// a) the target node of each non-spare edge is smaller than the number of nodes, and
55    /// b) the number of non-spare edges add up to the number of edges, and
56    /// c) the first_edge id at each node is valid
57    /// d) the number of nodes is consistent with the node array size
58    pub fn check_integrity(&self) -> bool {
59        self.edge_array
60            .iter()
61            .filter(|edge_entry| edge_entry.target != usize::MAX)
62            .all(|edge_entry| (edge_entry.target) < self.number_of_nodes())
63            && self
64                .edge_array
65                .iter()
66                .filter(|edge_entry| edge_entry.target != usize::MAX)
67                .count()
68                == self.number_of_edges
69            && self.node_array[..self.number_of_nodes]
70                .iter()
71                .filter(|entry| entry.edge_count > 0)
72                .all(|entry| entry.first_edge < self.number_of_edges)
73            && 2 + self.number_of_nodes == self.node_array.len()
74    }
75
76    pub fn new(
77        node_count: usize,
78        mut input: Vec<impl Edge<ID = NodeID> + EdgeData<DATA = T> + Ord>,
79    ) -> Self {
80        // sort input edges by source/target/data
81        // TODO(dl): sorting by source suffices to construct adjacency array
82        input.sort();
83        Self::new_from_sorted_list(node_count, &input)
84    }
85
86    pub fn new_from_sorted_list(
87        number_of_nodes: usize,
88        input: &[impl Edge<ID = NodeID> + EdgeData<DATA = T> + Ord],
89    ) -> Self {
90        // TODO: renumber IDs if necessary
91        let number_of_edges = input.len();
92
93        let mut graph = DynamicGraph::<T> {
94            number_of_nodes,
95            number_of_edges,
96            ..Default::default()
97        };
98        // +1 as we are going to add one sentinel node at the end
99        graph.node_array.reserve(number_of_nodes + 1);
100        graph
101            .edge_array
102            .reserve((number_of_edges as f64 * GROWTH_FACTOR) as usize);
103
104        // add first entry manually, rest will be computed
105        graph.node_array.push(NodeArrayEntry::new(0));
106        let mut offset = 0;
107        let mut prev_offset = 0;
108        for i in 0..number_of_nodes {
109            while offset != input.len() && input[offset].source() == i {
110                offset += 1;
111            }
112            // record the edge count on the source node
113            graph.node_array.last_mut().unwrap().edge_count = offset - prev_offset;
114            prev_offset = offset;
115            graph.node_array.push(NodeArrayEntry::new(offset as EdgeID));
116        }
117
118        // add sentinel at the end of the node array
119        graph
120            .node_array
121            .push(NodeArrayEntry::new((input.len()) as EdgeID));
122
123        graph.edge_array = input
124            .iter()
125            .map(move |edge| EdgeArrayEntry {
126                target: edge.target(),
127                data: *edge.data(),
128            })
129            .collect();
130        debug_assert!(graph.check_integrity());
131        graph
132    }
133
134    /// Inserts a node with an empty edge slice into the node array.
135    pub fn insert_node(&mut self) {
136        self.node_array.push(NodeArrayEntry::new(
137            self.node_array.last().unwrap().first_edge,
138        ));
139        self.number_of_nodes += 1;
140    }
141
142    /// Inserts an edge into the graph by making sure that there's room one
143    /// index past the current edge slice. It does so by doing the following:
144    /// If one past the slice is a spare edge, use it
145    /// Else, if one before the slice is a spare, move the last element over
146    /// Else, resize the edge array sufficiently and relocate the slice at
147    /// the beginning of the newly added extension of the edge array.
148    pub fn insert_edge(&mut self, source: NodeID, target: NodeID, data: T) {
149        // if the source of target nodes don't exist yet, then add them.
150        while self.number_of_nodes <= source {
151            self.insert_node();
152        }
153        while self.number_of_nodes <= target {
154            self.insert_node();
155        }
156
157        // check if array of outgoing edges needs to be moved to the end
158        let NodeArrayEntry {
159            first_edge,
160            edge_count,
161        } = self.node_array[source];
162
163        let right_potential_edge_id = first_edge + edge_count;
164        if right_potential_edge_id == self.edge_array.len()
165            || !self.is_spare_edge(right_potential_edge_id)
166        {
167            // is there free space left of edge slice?
168            if first_edge != 0 && self.is_spare_edge(first_edge - 1) {
169                // move the right-most element of the slice one past the left end
170                self.node_array[source].first_edge -= 1;
171                self.edge_array
172                    .swap(first_edge - 1, right_potential_edge_id - 1);
173            } else {
174                let new_first_edge = self.edge_array.len();
175                let new_slice_len = (edge_count as f64 * GROWTH_FACTOR) as usize + 1;
176                // do we need to resize the array?
177                if self.edge_array.capacity() < (new_first_edge + new_slice_len) {
178                    // reserve additional capacity to move data to the end
179                    self.edge_array.reserve_exact(new_slice_len);
180                }
181                self.edge_array.resize(
182                    new_first_edge + new_slice_len,
183                    EdgeArrayEntry {
184                        target: INVALID_NODE_ID,
185                        data, // TODO: this is dummy data, should it be T::Default()?
186                    },
187                );
188                // move the edges over and invalidate the old ones
189                (0..edge_count).for_each(|i| {
190                    self.edge_array.swap(new_first_edge + i, first_edge + i);
191                });
192                self.node_array[source].first_edge = new_first_edge;
193            }
194        }
195
196        // At this stage, the entry past the edge slice is guaranteed to be a
197        // spare edge. The following lines write the edge array entry there and
198        // do the necessary book keeping to keep the graph integrity.
199        let edge_id = self.node_array[source].slice_end();
200        self.edge_array[edge_id] = EdgeArrayEntry { target, data };
201        self.node_array[source].edge_count += 1;
202        self.number_of_edges += 1;
203    }
204
205    /// Check whether the edge is unused.
206    fn is_spare_edge(&self, edge: EdgeID) -> bool {
207        self.edge_array[edge].target == usize::MAX
208    }
209
210    /// Make the edge unused.
211    fn make_spare_edge(&mut self, edge: EdgeID) {
212        self.edge_array[edge].target = usize::MAX
213    }
214
215    /// Removes an edge by adjusting counters, moving the edge-to-delete to the
216    /// end of the edge slice and making it a spare edge
217    pub fn remove_edge(&mut self, source: NodeID, edge_to_delete: EdgeID) {
218        self.number_of_edges -= 1;
219        self.node_array[source].edge_count -= 1;
220
221        let NodeArrayEntry {
222            first_edge,
223            edge_count,
224        } = self.node_array[source];
225        let last_edge_at_node = first_edge + edge_count;
226        self.edge_array.swap(last_edge_at_node, edge_to_delete);
227        self.make_spare_edge(last_edge_at_node);
228    }
229}
230
231impl<T: Copy> Graph<T> for DynamicGraph<T> {
232    fn node_range(&self) -> Range<NodeID> {
233        Range {
234            start: 0,
235            end: self.number_of_nodes() as NodeID,
236        }
237    }
238
239    fn edge_range(&self, n: NodeID) -> Range<EdgeID> {
240        Range {
241            start: self.begin_edges(n),
242            end: self.end_edges(n),
243        }
244    }
245
246    fn number_of_nodes(&self) -> usize {
247        self.number_of_nodes
248    }
249
250    fn number_of_edges(&self) -> usize {
251        self.number_of_edges
252    }
253
254    fn begin_edges(&self, n: NodeID) -> EdgeID {
255        self.node_array[n].first_edge
256    }
257
258    fn end_edges(&self, n: NodeID) -> EdgeID {
259        self.node_array[n].first_edge + self.out_degree(n)
260    }
261
262    fn out_degree(&self, n: NodeID) -> usize {
263        self.node_array[n].edge_count
264    }
265
266    fn target(&self, e: EdgeID) -> NodeID {
267        self.edge_array[e].target
268    }
269
270    fn data(&self, e: EdgeID) -> &T {
271        &self.edge_array[e].data
272    }
273
274    fn data_mut(&mut self, e: EdgeID) -> &mut T {
275        &mut self.edge_array[e].data
276    }
277
278    fn find_edge(&self, s: NodeID, t: NodeID) -> Option<EdgeID> {
279        if s > self.number_of_nodes() {
280            return None;
281        }
282        self.edge_range(s).find(|&edge| self.target(edge) == t)
283    }
284
285    fn find_edge_unchecked(&self, s: NodeID, t: NodeID) -> EdgeID {
286        if s > self.number_of_nodes() {
287            return EdgeID::MAX;
288        }
289        for edge in self.edge_range(s) {
290            if self.target(edge) == t {
291                return edge;
292            }
293        }
294        EdgeID::MAX
295    }
296}
297
298#[cfg(test)]
299mod tests {
300    use crate::edge::InputEdge;
301
302    use crate::graph::EdgeID;
303    use crate::{dynamic_graph::DynamicGraph, graph::Graph};
304
305    const EDGES: [InputEdge<i32>; 8] = [
306        InputEdge {
307            source: 0,
308            target: 1,
309            data: 3,
310        },
311        InputEdge {
312            source: 0,
313            target: 4,
314            data: 2,
315        },
316        InputEdge {
317            source: 1,
318            target: 2,
319            data: 3,
320        },
321        InputEdge {
322            source: 1,
323            target: 5,
324            data: 2,
325        },
326        InputEdge {
327            source: 2,
328            target: 3,
329            data: 6,
330        },
331        InputEdge {
332            source: 4,
333            target: 2,
334            data: 1,
335        },
336        InputEdge {
337            source: 4,
338            target: 5,
339            data: 2,
340        },
341        InputEdge {
342            source: 5,
343            target: 3,
344            data: 7,
345        },
346    ];
347
348    #[test]
349    fn size() {
350        type Graph = DynamicGraph<i32>;
351        let graph = Graph::new_from_sorted_list(6, &EDGES);
352        assert_eq!(6, graph.number_of_nodes());
353        assert_eq!(8, graph.number_of_edges());
354    }
355
356    #[test]
357    fn new() {
358        type Graph = DynamicGraph<i32>;
359        let graph = Graph::new(6, EDGES.to_vec());
360        assert_eq!(6, graph.number_of_nodes());
361        assert_eq!(8, graph.number_of_edges());
362    }
363
364    #[test]
365    fn insert_node_edge() {
366        type Graph = DynamicGraph<i32>;
367        let mut graph = Graph::new(6, EDGES.to_vec());
368        assert_eq!(6, graph.number_of_nodes());
369        assert_eq!(8, graph.number_of_edges());
370
371        graph.insert_node();
372        assert_eq!(7, graph.number_of_nodes());
373
374        graph.insert_edge(5, 6, 20);
375        assert_eq!(9, graph.number_of_edges());
376
377        graph.insert_edge(10, 11, -1);
378        assert_eq!(12, graph.number_of_nodes());
379        assert_eq!(10, graph.number_of_edges());
380    }
381
382    #[test]
383    fn degree() {
384        type Graph = DynamicGraph<i32>;
385        let graph = Graph::new_from_sorted_list(6, &EDGES);
386        let mut sum = 0;
387        for i in graph.node_range() {
388            sum += graph.out_degree(i);
389        }
390        assert_eq!(sum, graph.number_of_edges());
391    }
392
393    #[test]
394    fn remove_edge() {
395        type Graph = DynamicGraph<i32>;
396        let mut graph = Graph::new(6, EDGES.to_vec());
397        assert_eq!(6, graph.number_of_nodes());
398        assert_eq!(8, graph.number_of_edges());
399
400        let edge = graph.find_edge(1, 5);
401        assert!(edge.is_some());
402        graph.remove_edge(1, edge.unwrap());
403        assert_eq!(7, graph.number_of_edges());
404
405        let edge = graph.find_edge(1, 5);
406        assert!(edge.is_none());
407    }
408
409    #[test]
410    fn data_mut() {
411        type Graph = DynamicGraph<i32>;
412        let mut graph = Graph::new(6, EDGES.to_vec());
413        assert_eq!(6, graph.number_of_nodes());
414        assert_eq!(8, graph.number_of_edges());
415
416        let edge = graph.find_edge(1, 5);
417        assert!(edge.is_some());
418        assert_ne!(123, *graph.data(edge.unwrap()));
419
420        *graph.data_mut(edge.unwrap()) = 123;
421        assert_eq!(123, *graph.data(edge.unwrap()));
422    }
423
424    #[test]
425    fn find_edge() {
426        type Graph = DynamicGraph<i32>;
427        let graph = Graph::new_from_sorted_list(6, &EDGES);
428
429        // existing edges
430        assert!(graph.find_edge_unchecked(0, 1) != EdgeID::MAX);
431        assert!(graph.find_edge_unchecked(1, 2) != EdgeID::MAX);
432        assert!(graph.find_edge_unchecked(4, 2) != EdgeID::MAX);
433        assert!(graph.find_edge_unchecked(2, 3) != EdgeID::MAX);
434        assert!(graph.find_edge_unchecked(0, 4) != EdgeID::MAX);
435        assert!(graph.find_edge_unchecked(4, 5) != EdgeID::MAX);
436        assert!(graph.find_edge_unchecked(5, 3) != EdgeID::MAX);
437        assert!(graph.find_edge_unchecked(1, 5) != EdgeID::MAX);
438        assert!(graph.find_edge(0, 1).is_some());
439        assert!(graph.find_edge(1, 2).is_some());
440        assert!(graph.find_edge(4, 2).is_some());
441        assert!(graph.find_edge(2, 3).is_some());
442        assert!(graph.find_edge(0, 4).is_some());
443        assert!(graph.find_edge(4, 5).is_some());
444        assert!(graph.find_edge(5, 3).is_some());
445        assert!(graph.find_edge(1, 5).is_some());
446
447        // non-existing edge within ranges
448        assert_eq!(graph.find_edge_unchecked(0, 0), EdgeID::MAX);
449        assert!(graph.find_edge(0, 0).is_none());
450
451        // non-existing edge out of range
452        assert_eq!(graph.find_edge_unchecked(16, 17), EdgeID::MAX);
453        assert!(graph.find_edge(16, 17).is_none());
454    }
455
456    #[test]
457    fn insert_edge() {
458        type Graph = DynamicGraph<i32>;
459
460        let mut graph = Graph::new_from_sorted_list(6, &EDGES);
461        assert_eq!(6, graph.number_of_nodes());
462        assert_eq!(8, graph.number_of_edges());
463
464        // the node exists, but it's degree is 0, it will be created at the end
465        assert_eq!(0, graph.out_degree(3));
466        graph.insert_edge(3, 5, 123);
467
468        // check that graph was expanded and edge exists
469        assert_eq!(1, graph.out_degree(3));
470        assert_eq!(6, graph.number_of_nodes());
471        assert_eq!(9, graph.number_of_edges());
472        assert!(graph.find_edge(3, 5).is_some());
473
474        // check that all other edges exist as well
475        for edge in &EDGES {
476            let result = graph.find_edge(edge.source, edge.target);
477            assert!(result.is_some());
478            let edge_id = result.unwrap();
479            let data = *graph.data(edge_id);
480            assert_eq!(edge.data, data);
481        }
482
483        // insert edge that forces moving edge slice to end of array
484        graph.insert_edge(4, 1, 7);
485        // check that edge exists
486        assert_eq!(6, graph.number_of_nodes());
487        assert_eq!(10, graph.number_of_edges());
488        assert!(graph.find_edge(4, 1).is_some());
489        assert!(graph.check_integrity());
490
491        // insert edge that finds a free slot left of its slice
492        graph.insert_edge(5, 1, 1234);
493        // check that edge exists
494        assert_eq!(6, graph.number_of_nodes());
495        assert_eq!(11, graph.number_of_edges());
496        assert!(graph.find_edge(5, 1).is_some());
497        assert!(graph.check_integrity());
498
499        // insert edge that finds a free slot left of right slice
500        assert!(graph.find_edge(2, 5).is_none());
501        graph.insert_edge(2, 5, 1234);
502        // check that edge exists
503        assert_eq!(6, graph.number_of_nodes());
504        assert_eq!(12, graph.number_of_edges());
505        assert!(graph.find_edge(2, 5).is_some());
506        assert!(graph.check_integrity());
507
508        // check that all other edges exist as well
509        for edge in &EDGES {
510            let result = graph.find_edge(edge.source, edge.target);
511            assert!(result.is_some());
512            let edge_id = result.unwrap();
513            let data = *graph.data(edge_id);
514            assert_eq!(edge.data, data);
515        }
516
517        assert!(graph.find_edge(3, 5).is_some());
518        assert!(graph.find_edge(4, 1).is_some());
519        assert!(graph.find_edge(5, 1).is_some());
520        assert!(graph.find_edge(2, 5).is_some());
521    }
522}
toolbox_rs/dynamic_graph.rs

toolbox_rs/
dynamic_graph.rs
