sparse_graph/lib.rs
1#![allow(non_snake_case)]
2
3use std::fmt;
4
5/// A `SparseGraph` represents an unweighted graph with `V` nodes and `E` edges using the
6/// [compressed sparse row](https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format)) format.
7#[derive(Debug)]
8pub struct SparseGraph<'a> {
9 idxptr: &'a [usize], // O(V)
10 indices: &'a [usize], // O(E)
11}
12
13impl SparseGraph<'_> {
14 /// Returns a sparse graph.
15 ///
16 /// # Arguments
17 ///
18 /// * `idxptr` - Starting index in `indices` for each vertex. These must be strictly non-decreasing
19 /// and less than `indices.len`. The length defines the number of nodes in the graph, `V`
20 /// * `indices` - Values in the range `0..V-1` indicating which nodes each vertex is linked to.
21 /// The length defines the number edges in the graph, `E`.
22 ///
23 /// # Panics
24 ///
25 /// # Example
26 ///
27 /// ```
28 /// use sparse_graph::SparseGraph;
29 ///
30 /// let (idxptr, indices) = (vec![0, 1, 3, 4, 5, 6], vec![1, 2, 3, 0, 4, 5, 3]);
31 /// let g = SparseGraph::new(&idxptr, &indices);
32 /// ```
33 pub fn new<'a>(idxptr: &'a [usize], indices: &'a [usize]) -> SparseGraph<'a> {
34 let edge_count = indices.len();
35 if idxptr.is_empty() && idxptr[0] != 0 {
36 panic!("Bad index ptr!");
37 }
38 if edge_count > 0 {
39 for index in idxptr.iter() {
40 if *index >= edge_count {
41 panic!("Bad index!");
42 }
43 }
44 }
45 SparseGraph { idxptr, indices }
46 }
47
48 /// Computes the strongly connected components using a memory optimised version of Tarjan's algorithm.
49 ///
50 /// See <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1707>.
51 ///
52 /// Returns
53 ///
54 /// # Example
55 ///
56 /// ```
57 /// use sparse_graph::{SparseGraph, ConnectedComponents};
58 ///
59 /// // Create a graph with two strongly connect components
60 /// let (idxptr, indices) = (vec![0, 1, 3, 4, 5, 6], vec![1, 2, 3, 0, 4, 5, 3]);
61 /// let g = SparseGraph::new(&idxptr, &indices);
62 /// let ConnectedComponents { n, labels, sparse_graph } = g.scc();
63 /// assert_eq!(n, 2);
64 /// assert_eq!(labels, [1, 1, 1, 0, 0, 0]);
65 /// assert!(std::ptr::eq(sparse_graph, &g))
66 /// ```
67 pub fn scc(&self) -> ConnectedComponents {
68 let N = self.idxptr.len();
69 let END = N + 1;
70 let VOID = N + 2;
71
72 let mut lowlinks = vec![VOID; N];
73 let mut stack_f = vec![VOID; N];
74 let mut stack_b = vec![VOID; N];
75
76 let mut label = N;
77 let mut index = 0;
78 let mut ss_head = END;
79
80 // Iterate over every node in order
81 for v1 in 0..N {
82 // If not node hasn't been processed yet, it won't have a lowlink or a label
83 if lowlinks[v1] == VOID {
84 // DFS-stack push;
85 // At this point, the DFS stack is empty, so pushing sets both the
86 // forward and backwards pointers to end.
87 let mut stack_head = v1;
88 stack_f[v1] = END;
89 stack_b[v1] = END;
90 // We'll now proceed wih the inner loop algorithm until the stack is empty
91 while stack_head != END {
92 let v = stack_head;
93 if lowlinks[v] == VOID {
94 // If the top node in the stack hasn't been visited yet,
95 // assign it the next index value.
96 lowlinks[v] = index;
97 index += 1;
98
99 // Visit all of the nodes accessible from v and push then onto the stack
100 // ahead of v. If they're already in the stack, bring them to the top.
101 let range_end = if v == N - 1 {
102 self.indices.len()
103 } else {
104 self.idxptr[v + 1]
105 };
106
107 for &w in &self.indices[self.idxptr[v]..range_end] {
108 if lowlinks[w] == VOID {
109 if stack_f[w] != VOID {
110 // w is already inside the stack, so excise it.
111 let f = stack_f[w];
112 let b = stack_b[w];
113 if b != END {
114 stack_f[b] = f;
115 }
116 if f != END {
117 stack_b[f] = b;
118 }
119 }
120
121 // Add w to the top of the stack. end <-> w <-> stack_head <-> ...
122 stack_f[w] = stack_head;
123 stack_b[w] = END;
124 stack_b[stack_head] = w;
125 stack_head = w;
126 }
127 }
128 } else {
129 // DFS-stack pop
130 stack_head = stack_f[v];
131 // If the stack_head isn't the end
132 if stack_head < N {
133 stack_b[stack_head] = END;
134 }
135 stack_f[v] = VOID;
136 stack_b[v] = VOID;
137
138 // Find out whether this node is a root node
139 // We look at all its linked nodes (which have now all had this
140 // process applied to them!). If none of them have a lower index than this
141 // node then we have a root value. Otherwise we reset the index to the lowest
142 // index.
143 let mut root = true;
144 let mut low_v = lowlinks[v];
145 let range_end = if v == N - 1 {
146 self.indices.len()
147 } else {
148 self.idxptr[v + 1]
149 };
150 for &w in &self.indices[self.idxptr[v]..range_end] {
151 let low_w = lowlinks[w];
152 if low_w < low_v {
153 low_v = low_w;
154 root = false;
155 }
156 }
157 lowlinks[v] = low_v;
158 let ss = &mut stack_f;
159 if root {
160 // Found a root node. This means we've found the root of
161 // a strongly connected component. All the items on the stack
162 // with an index greater or equal to the current nodes index
163 // are part of the SCC and get the same level.
164 // We can reclaim their index values at this point.
165
166 // while S not empty and rindex[v] <= rindex[top[S]]
167 while ss_head != END && lowlinks[v] <= lowlinks[ss_head] {
168 let w = ss_head; // w = pop(S)
169 ss_head = ss[w];
170 ss[w] = VOID;
171 let labels = &mut lowlinks;
172 labels[w] = label; // rindex[w] = c;
173 index -= 1; // index = index - 1
174 }
175 let labels = &mut lowlinks;
176 if index > 0 {
177 index -= 1;
178 }
179 labels[v] = label; // rindex[v] = c
180
181 // Move to the next available label value
182 label -= 1;
183 } else {
184 // We haven't got to the root of this group, so add v to the sets stack
185 ss[v] = ss_head; // push(S, v)
186 ss_head = v;
187 }
188 }
189 }
190 }
191 }
192 let labels = &mut lowlinks;
193
194 for label in labels.iter_mut() {
195 *label = N - *label
196 }
197 ConnectedComponents {
198 n: N - label,
199 labels: lowlinks,
200 sparse_graph: self,
201 }
202 }
203}
204
205/// A label map of the connected components of a graph.
206pub struct ConnectedComponents<'a> {
207 /// The sparse graph associated with the connected components.
208 pub sparse_graph: &'a SparseGraph<'a>,
209 /// The number of connected components.
210 pub n: usize,
211 /// A vector of labels from `0` to `n-1`. Corresponding nodes with the same label beloing to the same connected component.
212 pub labels: Vec<usize>,
213}
214
215impl fmt::Display for SparseGraph<'_> {
216 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
217 writeln!(f, "SparseGraph: {{").expect("");
218 for i in 0..self.indices.len() {
219 let start = self.indices[i];
220 let end;
221 if i == self.indices.len() - 1 {
222 end = self.idxptr.len()
223 } else {
224 end = self.indices[i + 1];
225 }
226 let node = &self.idxptr[start..end];
227 writeln!(f, " Node {}: {:?}", i, node).expect("");
228 }
229 write!(f, "}}")
230 }
231}
232
233#[derive(Debug)]
234pub struct WeightedSparseGraph<'a, W> {
235 /// Starting index in `indices` for each vertex. These are strictly non-decreasing
236 /// and less than `indices.len`. Length is equal to the number of nodes in the graph, `V`.
237 idxptr: &'a Vec<usize>,
238 /// Values in the range `0..V-1` indicating which nodes each vertex is linked to.
239 /// Length is equal to the number edges in the graph, `E`.
240 indices: &'a Vec<usize>,
241
242 // Edge weights. The weights correspond to the edges defined in `indices`.
243 weights: &'a Vec<W>,
244}
245
246#[derive(Debug)]
247pub struct ValuedSparseGraph<'a, V> {
248 /// Starting index in `indices` for each vertex. These are strictly non-decreasing
249 /// and less than `indices.len`. Length is equal to the number of nodes in the graph.
250 idxptr: &'a Vec<usize>,
251 /// Values `0..N-1` indicating which nodes each vertex is linked to.
252 /// Length is equal to the number edges in the graph.
253 indices: &'a Vec<usize>,
254
255 // Vertex values. The values correspond to the values in `idxptr`.
256 values: Vec<V>,
257}
258
259impl<'a, V> ValuedSparseGraph<'a, V> {
260 pub fn as_sparse_graph(&self) -> SparseGraph {
261 SparseGraph {
262 indices: &self.indices,
263 idxptr: &self.idxptr,
264 }
265 }
266}
267
268#[derive(Debug)]
269pub struct WeightedValuedSparseGraph<'a, W, V> {
270 /// Starting index in `indices` for each vertex. These are strictly non-decreasing
271 /// and less than `indices.len`. Length is equal to the number of nodes in the graph.
272 idxptr: &'a Vec<usize>,
273 /// Values `0..N-1` indicating which nodes each vertex is linked to.
274 /// Length is equal to the number edges in the graph.
275 indices: &'a Vec<usize>,
276
277 // Vertex values. The values correspond to the values in `idxptr`.
278 values: &'a Vec<V>,
279
280 // Edge weights. The weights correspond to the edges defined in `indices`.
281 weights: &'a Vec<W>,
282}
283
284#[cfg(test)]
285mod tests {
286 use super::*;
287
288 #[test]
289 fn sparse_graph_new() {
290 let (a, b) = (vec![0, 1, 2], vec![1, 2, 0]);
291 let g = SparseGraph::new(&a, &b);
292 assert_eq!(*(g.idxptr), [0, 1, 2]);
293 assert_eq!(*g.indices, [1, 2, 0]);
294 }
295
296 #[test]
297 fn scc_1() {
298 let (a, b) = (vec![0, 1, 2], vec![1, 2, 0]);
299 let g = SparseGraph::new(&a, &b);
300 let ConnectedComponents {
301 n,
302 labels,
303 sparse_graph,
304 } = g.scc();
305 assert_eq!(n, 1);
306 assert_eq!(labels, [0, 0, 0]);
307 assert!(std::ptr::eq(sparse_graph, &g))
308 }
309
310 #[test]
311 fn scc_2() {
312 let (a, b) = (vec![0; 3], vec![]);
313 let g = SparseGraph::new(&a, &b);
314 dbg!(&g);
315 let ConnectedComponents { n, labels, .. } = g.scc();
316 assert_eq!(n, 3);
317 assert_eq!(labels, [0, 1, 2]);
318 }
319
320 #[test]
321 fn scc_3() {
322 let (a, b) = (vec![0, 1, 3, 4, 5, 6], vec![1, 2, 3, 0, 4, 5, 3]);
323 let g = SparseGraph::new(&a, &b);
324 let ConnectedComponents { n, labels, .. } = g.scc();
325 assert_eq!(n, 2);
326 assert_eq!(labels, [1, 1, 1, 0, 0, 0]);
327 }
328}