toolbox_rs/
cell.rs

1use fxhash::FxHashMap;
2use itertools::Itertools;
3use log::debug;
4
5use crate::{
6    edge::InputEdge, graph::NodeID, one_to_many_dijkstra::OneToManyDijkstra,
7    static_graph::StaticGraph,
8};
9
10#[derive(Clone, Debug)]
11pub struct BaseCell {
12    // TODO: experiment on thin_vec
13    pub incoming_nodes: Vec<NodeID>,
14    pub outgoing_nodes: Vec<NodeID>,
15    pub edges: Vec<InputEdge<usize>>,
16    // TODO: add renumbering table to support unpacking edges
17}
18
19impl Default for BaseCell {
20    fn default() -> Self {
21        Self::new()
22    }
23}
24
25impl BaseCell {
26    pub fn new() -> Self {
27        BaseCell {
28            incoming_nodes: Vec::new(),
29            outgoing_nodes: Vec::new(),
30            edges: Vec::new(),
31        }
32    }
33
34    pub fn process(&self) -> MatrixCell {
35        // renumber nodes to be in contiguous range"
36        // [sources..targets..other nodes]
37        // [0,1,2         ...         n-1]
38
39        // println!("processing cell {:?}", self);
40        let mut seen_nodes = FxHashMap::default();
41        self.incoming_nodes.iter().for_each(|node| {
42            let next_id = seen_nodes.len();
43            seen_nodes.entry(*node).or_insert(next_id);
44            // println!("source {}, idx: {}", *node, seen_nodes.len());
45        });
46        // println!("1");
47        self.outgoing_nodes.iter().for_each(|node| {
48            let next_id = seen_nodes.len();
49            seen_nodes.entry(*node).or_insert(next_id);
50            // println!("target {}, idx: {}", *node, seen_nodes.len());
51        });
52        // println!("2");
53
54        let new_edges = self
55            .edges
56            .iter()
57            .map(|edge| {
58                // renumber source/target nodes of edges to be in range [0..k-1]
59                let mut new_edge = *edge;
60
61                let seen_nodes_len = seen_nodes.len();
62                seen_nodes.entry(edge.source).or_insert(seen_nodes_len);
63                new_edge.source = *seen_nodes.get(&edge.source).expect("renumbering broken");
64
65                let seen_nodes_len = seen_nodes.len();
66                seen_nodes.entry(edge.target).or_insert(seen_nodes_len);
67                new_edge.target = *seen_nodes.get(&edge.target).expect("renumbering broken");
68
69                new_edge
70            })
71            .collect_vec();
72
73        // instantiate subgraph
74        let graph = StaticGraph::new(new_edges);
75        let mut dijkstra = OneToManyDijkstra::new();
76        let mut matrix = vec![usize::MAX; self.incoming_nodes.len() * self.outgoing_nodes.len()];
77
78        let source_range = 0..self.incoming_nodes.len();
79        let target_range = (self.incoming_nodes.len()
80            ..self.incoming_nodes.len() + self.outgoing_nodes.len())
81            .collect_vec();
82        // println!("3, graph: ({},{})", graph.number_of_nodes(), graph.number_of_edges());
83        if !self.edges.is_empty() {
84            for source in source_range {
85                // compute clique information repeated one-to-many calls for each source
86                let _success = dijkstra.run(&graph, source, &target_range);
87                for target in &target_range {
88                    let distance = dijkstra.distance(*target);
89                    let target_index = target - self.incoming_nodes.len();
90                    debug!(
91                        "matrix[{}] distance({source},{target})={distance}",
92                        (source * self.outgoing_nodes.len() + target_index)
93                    );
94
95                    matrix[source * self.outgoing_nodes.len() + target_index] = distance;
96                }
97            }
98        }
99        // println!("4");
100
101        // return MatrixCell
102        MatrixCell {
103            matrix,
104            incoming_nodes: self.incoming_nodes.clone(),
105            outgoing_nodes: self.outgoing_nodes.clone(),
106        }
107    }
108}
109
110#[derive(Clone)]
111pub struct MatrixCell {
112    // TODO: experiment on thin_vec
113    pub incoming_nodes: Vec<NodeID>,
114    pub outgoing_nodes: Vec<NodeID>,
115    // matrix of pairwise distances between boundary nodes
116    pub matrix: Vec<usize>,
117}
118
119impl MatrixCell {
120    // TODO: iterator for row and column access
121    pub fn get_distance_row(&self, u: NodeID) -> &[usize] {
122        // get row in matrix for node u
123        let index = self
124            .incoming_nodes
125            .binary_search(&u)
126            .unwrap_or_else(|_| panic!("node {u} not found in node boundary"));
127        // return the row of the matrix
128        &self.matrix[index * self.incoming_nodes.len()..(index + 1) * self.outgoing_nodes.len()]
129    }
130
131    pub fn overlay_edges(&self) -> Vec<InputEdge<usize>> {
132        let mut result = Vec::with_capacity(self.incoming_nodes.len() * self.outgoing_nodes.len());
133
134        // walk matrix to derive list of edges for the next level of processing
135        for i in 0..self.incoming_nodes.len() {
136            let source = self.incoming_nodes[i];
137            for j in 0..self.outgoing_nodes.len() {
138                let distance = self.matrix[i * j + i];
139                if distance != usize::MAX {
140                    let target = self.outgoing_nodes[j];
141                    let edge = InputEdge {
142                        source,
143                        target,
144                        data: distance,
145                    };
146                    // edge_count += 1;
147                    result.push(edge);
148                }
149            }
150        }
151
152        result
153    }
154}
155
156#[cfg(test)]
157mod tests {
158    use super::BaseCell;
159    use crate::{edge::InputEdge, graph::UNREACHABLE};
160
161    #[test]
162    fn process_base_cell1() {
163        let edges: Vec<InputEdge<usize>> = vec![
164            InputEdge::new(0, 1, 3),
165            InputEdge::new(1, 2, 3),
166            InputEdge::new(4, 2, 1),
167            InputEdge::new(2, 3, 6),
168            InputEdge::new(0, 4, 2),
169            InputEdge::new(4, 5, 2),
170            InputEdge::new(5, 3, 7),
171            InputEdge::new(1, 5, 2),
172        ];
173
174        // check first set of source, target nodes
175        let incoming_nodes = vec![0, 4];
176        let outgoing_nodes = vec![3, 5];
177
178        let base_cell = BaseCell {
179            incoming_nodes: incoming_nodes.clone(),
180            outgoing_nodes: outgoing_nodes.clone(),
181            edges: edges.clone(),
182        };
183        let matrix_cell = base_cell.process();
184
185        assert_eq!(incoming_nodes, matrix_cell.incoming_nodes);
186        assert_eq!(outgoing_nodes, matrix_cell.outgoing_nodes);
187        assert_eq!(matrix_cell.matrix, vec![9, 4, 7, 2]);
188
189        assert_eq!(matrix_cell.get_distance_row(0), vec![9, 4]);
190        assert_eq!(matrix_cell.get_distance_row(4), vec![7, 2]);
191
192        // check second set of source, target nodes
193        let incoming_nodes = vec![0, 1];
194        let outgoing_nodes = vec![4, 5];
195
196        let base_cell = BaseCell {
197            incoming_nodes: incoming_nodes.clone(),
198            outgoing_nodes: outgoing_nodes.clone(),
199            edges,
200        };
201        let matrix_cell = base_cell.process();
202
203        assert_eq!(incoming_nodes, matrix_cell.incoming_nodes);
204        assert_eq!(outgoing_nodes, matrix_cell.outgoing_nodes);
205        assert_eq!(matrix_cell.matrix, vec![2, 4, UNREACHABLE, 2]);
206
207        assert_eq!(matrix_cell.get_distance_row(0), vec![2, 4]);
208        assert_eq!(matrix_cell.get_distance_row(1), vec![UNREACHABLE, 2]);
209    }
210
211    #[test]
212    fn process_base_cell2() {
213        let edges = vec![
214            InputEdge::new(0, 1, 7),
215            InputEdge::new(0, 2, 3),
216            InputEdge::new(1, 2, 1),
217            InputEdge::new(1, 3, 6),
218            InputEdge::new(2, 4, 8),
219            InputEdge::new(3, 5, 2),
220            InputEdge::new(3, 2, 3),
221            InputEdge::new(4, 3, 2),
222            InputEdge::new(4, 5, 8),
223        ];
224
225        // check first set of source, target nodes
226        let incoming_nodes = vec![0, 1];
227        let outgoing_nodes = vec![4, 5];
228
229        let base_cell = BaseCell {
230            incoming_nodes: incoming_nodes.clone(),
231            outgoing_nodes: outgoing_nodes.clone(),
232            edges: edges.clone(),
233        };
234        let matrix_cell = base_cell.process();
235
236        assert_eq!(incoming_nodes, matrix_cell.incoming_nodes);
237        assert_eq!(outgoing_nodes, matrix_cell.outgoing_nodes);
238        assert_eq!(matrix_cell.matrix, vec![11, 15, 9, 8]);
239
240        assert_eq!(matrix_cell.get_distance_row(0), vec![11, 15]);
241        assert_eq!(matrix_cell.get_distance_row(1), vec![9, 8]);
242
243        // check second set of source, target nodes
244        let incoming_nodes = vec![0, 2];
245        let outgoing_nodes = vec![3, 5];
246
247        let base_cell = BaseCell {
248            incoming_nodes: incoming_nodes.clone(),
249            outgoing_nodes: outgoing_nodes.clone(),
250            edges,
251        };
252        let matrix_cell = base_cell.process();
253
254        assert_eq!(incoming_nodes, matrix_cell.incoming_nodes);
255        assert_eq!(outgoing_nodes, matrix_cell.outgoing_nodes);
256        assert_eq!(matrix_cell.matrix, vec![13, 15, 10, 12]);
257
258        assert_eq!(matrix_cell.get_distance_row(0), vec![13, 15]);
259        assert_eq!(matrix_cell.get_distance_row(2), vec![10, 12]);
260    }
261
262    #[test]
263    #[should_panic]
264    fn matrix_cell_row_invalid() {
265        let edges: Vec<InputEdge<usize>> = vec![
266            InputEdge::new(0, 1, 3),
267            InputEdge::new(1, 2, 3),
268            InputEdge::new(4, 2, 1),
269            InputEdge::new(2, 3, 6),
270            InputEdge::new(0, 4, 2),
271            InputEdge::new(4, 5, 2),
272            InputEdge::new(5, 3, 7),
273            InputEdge::new(1, 5, 2),
274        ];
275
276        // check first set of source, target nodes
277        let incoming_nodes = vec![0, 4];
278        let outgoing_nodes = vec![3, 5];
279
280        let base_cell = BaseCell {
281            incoming_nodes,
282            outgoing_nodes,
283            edges,
284        };
285        let matrix_cell = base_cell.process();
286        matrix_cell.get_distance_row(1);
287    }
288
289    #[test]
290    fn dimacs_extract() {
291        // regression test from handling DIMACS data set
292        let incoming_nodes = vec![
293            9425886, 8380081, 9425867, 8380040, 8380040, 9425848, 8380040, 9425887, 9425899,
294            9425952, 10105412, 10105432, 9425958, 8380092,
295        ];
296        let outgoing_nodes = vec![
297            9425844, 9425847, 9425861, 8380080, 10105465, 9425852, 8380082, 8380066, 9425885,
298            9425900, 9425953, 10105463, 10105408, 10105431,
299        ];
300        let edges = vec![
301            InputEdge::new(8380040, 9425844, 2852),
302            InputEdge::new(8380040, 9425847, 1641),
303            InputEdge::new(8380040, 9425849, 1334),
304            InputEdge::new(8380040, 9425861, 425),
305            InputEdge::new(8380040, 9425866, 1380),
306            InputEdge::new(8380051, 9425870, 2713),
307            InputEdge::new(8380051, 9425891, 2378),
308            InputEdge::new(8380051, 10105410, 1114),
309            InputEdge::new(8380051, 10105412, 1013),
310            InputEdge::new(8380052, 9425891, 1225),
311            InputEdge::new(8380052, 9425893, 892),
312            InputEdge::new(8380052, 10105410, 2375),
313            InputEdge::new(8380053, 9425893, 2497),
314            InputEdge::new(8380053, 9425921, 885),
315            InputEdge::new(8380053, 10105410, 1332),
316            InputEdge::new(8380073, 8380074, 2886),
317            InputEdge::new(8380073, 8380075, 864),
318            InputEdge::new(8380073, 9425896, 126),
319            InputEdge::new(8380074, 8380073, 2886),
320            InputEdge::new(8380075, 8380073, 864),
321            InputEdge::new(8380075, 8380076, 3560),
322            InputEdge::new(8380075, 8380078, 1770),
323            InputEdge::new(8380075, 9425897, 826),
324            InputEdge::new(8380076, 8380075, 3560),
325            InputEdge::new(8380076, 9425896, 3335),
326            InputEdge::new(8380076, 9425956, 2295),
327            InputEdge::new(8380078, 8380075, 1770),
328            InputEdge::new(8380081, 8380080, 667),
329            InputEdge::new(8380081, 8380083, 901),
330            InputEdge::new(8380081, 10105432, 1233),
331            InputEdge::new(8380083, 8380081, 901),
332            InputEdge::new(8380088, 8380089, 1638),
333            InputEdge::new(8380088, 8380090, 889),
334            InputEdge::new(8380088, 9425950, 2582),
335            InputEdge::new(8380089, 8380088, 1638),
336            InputEdge::new(8380090, 8380088, 889),
337            InputEdge::new(8380090, 8380091, 1311),
338            InputEdge::new(8380090, 8380092, 508),
339            InputEdge::new(8380091, 8380090, 1311),
340            InputEdge::new(8380092, 8380090, 508),
341            InputEdge::new(8380092, 9425952, 3106),
342            InputEdge::new(8380092, 10105464, 1979),
343            InputEdge::new(8380092, 10105465, 1334),
344            InputEdge::new(9425848, 9425849, 1917),
345            InputEdge::new(9425848, 9425850, 859),
346            InputEdge::new(9425848, 9425852, 1140),
347            InputEdge::new(9425848, 9425867, 2888),
348            InputEdge::new(9425848, 9425868, 1885),
349            InputEdge::new(9425849, 8380040, 1334),
350            InputEdge::new(9425849, 9425848, 1917),
351            InputEdge::new(9425849, 9425850, 1657),
352            InputEdge::new(9425850, 9425848, 859),
353            InputEdge::new(9425850, 9425849, 1657),
354            InputEdge::new(9425850, 9425869, 1253),
355            InputEdge::new(9425850, 10105411, 2474),
356            InputEdge::new(9425866, 8380040, 1380),
357            InputEdge::new(9425866, 9425869, 690),
358            InputEdge::new(9425866, 10105412, 3284),
359            InputEdge::new(9425867, 8380082, 1249),
360            InputEdge::new(9425867, 9425848, 2888),
361            InputEdge::new(9425867, 9425919, 1560),
362            InputEdge::new(9425868, 9425848, 1885),
363            InputEdge::new(9425868, 9425919, 1525),
364            InputEdge::new(9425868, 9425920, 2467),
365            InputEdge::new(9425869, 9425850, 1253),
366            InputEdge::new(9425869, 9425866, 690),
367            InputEdge::new(9425869, 9425870, 552),
368            InputEdge::new(9425870, 8380051, 2713),
369            InputEdge::new(9425870, 9425869, 552),
370            InputEdge::new(9425870, 10105406, 1196),
371            InputEdge::new(9425886, 8380066, 2224),
372            InputEdge::new(9425886, 9425887, 584),
373            InputEdge::new(9425886, 9425889, 2113),
374            InputEdge::new(9425886, 9425890, 1065),
375            InputEdge::new(9425887, 9425885, 491),
376            InputEdge::new(9425887, 9425886, 584),
377            InputEdge::new(9425887, 9425888, 904),
378            InputEdge::new(9425888, 9425887, 904),
379            InputEdge::new(9425888, 9425891, 1111),
380            InputEdge::new(9425888, 10105412, 2549),
381            InputEdge::new(9425889, 9425886, 2113),
382            InputEdge::new(9425889, 9425891, 491),
383            InputEdge::new(9425889, 9425892, 2112),
384            InputEdge::new(9425890, 9425886, 1065),
385            InputEdge::new(9425890, 9425894, 983),
386            InputEdge::new(9425890, 9425895, 4556),
387            InputEdge::new(9425891, 8380051, 2378),
388            InputEdge::new(9425891, 8380052, 1225),
389            InputEdge::new(9425891, 9425888, 1111),
390            InputEdge::new(9425891, 9425889, 491),
391            InputEdge::new(9425892, 9425889, 2112),
392            InputEdge::new(9425892, 9425893, 573),
393            InputEdge::new(9425892, 9425895, 1038),
394            InputEdge::new(9425892, 9425957, 3897),
395            InputEdge::new(9425893, 8380052, 892),
396            InputEdge::new(9425893, 8380053, 2497),
397            InputEdge::new(9425893, 9425892, 573),
398            InputEdge::new(9425894, 9425890, 983),
399            InputEdge::new(9425894, 9425896, 1070),
400            InputEdge::new(9425894, 9425954, 5245),
401            InputEdge::new(9425895, 9425890, 4556),
402            InputEdge::new(9425895, 9425892, 1038),
403            InputEdge::new(9425895, 9425954, 1544),
404            InputEdge::new(9425895, 9425955, 3563),
405            InputEdge::new(9425896, 8380073, 126),
406            InputEdge::new(9425896, 8380076, 3335),
407            InputEdge::new(9425896, 9425894, 1070),
408            InputEdge::new(9425897, 8380075, 826),
409            InputEdge::new(9425897, 9425898, 672),
410            InputEdge::new(9425897, 9425899, 989),
411            InputEdge::new(9425898, 9425897, 672),
412            InputEdge::new(9425899, 9425897, 989),
413            InputEdge::new(9425899, 9425900, 424),
414            InputEdge::new(9425919, 9425867, 1560),
415            InputEdge::new(9425919, 9425868, 1525),
416            InputEdge::new(9425919, 10105437, 2967),
417            InputEdge::new(9425920, 9425868, 2467),
418            InputEdge::new(9425920, 9425921, 414),
419            InputEdge::new(9425920, 10105411, 1016),
420            InputEdge::new(9425921, 8380053, 885),
421            InputEdge::new(9425921, 9425920, 414),
422            InputEdge::new(9425921, 10105437, 1242),
423            InputEdge::new(9425950, 8380088, 2582),
424            InputEdge::new(9425950, 9425951, 828),
425            InputEdge::new(9425950, 9425957, 1589),
426            InputEdge::new(9425950, 10105438, 1657),
427            InputEdge::new(9425951, 9425950, 828),
428            InputEdge::new(9425951, 9425952, 371),
429            InputEdge::new(9425951, 10105461, 861),
430            InputEdge::new(9425952, 8380092, 3106),
431            InputEdge::new(9425952, 9425951, 371),
432            InputEdge::new(9425952, 9425953, 742),
433            InputEdge::new(9425954, 9425894, 5245),
434            InputEdge::new(9425954, 9425895, 1544),
435            InputEdge::new(9425954, 9425956, 1306),
436            InputEdge::new(9425955, 9425895, 3563),
437            InputEdge::new(9425955, 9425957, 1202),
438            InputEdge::new(9425955, 9425958, 997),
439            InputEdge::new(9425956, 8380076, 2295),
440            InputEdge::new(9425956, 9425954, 1306),
441            InputEdge::new(9425957, 9425892, 3897),
442            InputEdge::new(9425957, 9425950, 1589),
443            InputEdge::new(9425957, 9425955, 1202),
444            InputEdge::new(9425957, 10105438, 1667),
445            InputEdge::new(9425958, 9425955, 997),
446            InputEdge::new(9425958, 10105462, 616),
447            InputEdge::new(9425958, 10105463, 1463),
448            InputEdge::new(10105406, 9425870, 1196),
449            InputEdge::new(10105406, 10105410, 1970),
450            InputEdge::new(10105406, 10105411, 508),
451            InputEdge::new(10105410, 8380051, 1114),
452            InputEdge::new(10105410, 8380052, 2375),
453            InputEdge::new(10105410, 8380053, 1332),
454            InputEdge::new(10105410, 10105406, 1970),
455            InputEdge::new(10105411, 9425850, 2474),
456            InputEdge::new(10105411, 9425920, 1016),
457            InputEdge::new(10105411, 10105406, 508),
458            InputEdge::new(10105412, 8380051, 1013),
459            InputEdge::new(10105412, 9425866, 3284),
460            InputEdge::new(10105412, 9425888, 2549),
461            InputEdge::new(10105412, 10105408, 1003),
462            InputEdge::new(10105432, 8380081, 1233),
463            InputEdge::new(10105432, 10105431, 1229),
464            InputEdge::new(10105432, 10105438, 7863),
465            InputEdge::new(10105437, 9425919, 2967),
466            InputEdge::new(10105437, 9425921, 1242),
467            InputEdge::new(10105437, 10105438, 2667),
468            InputEdge::new(10105438, 9425950, 1657),
469            InputEdge::new(10105438, 9425957, 1667),
470            InputEdge::new(10105438, 10105432, 7863),
471            InputEdge::new(10105438, 10105437, 2667),
472            InputEdge::new(10105461, 9425951, 861),
473            InputEdge::new(10105462, 9425958, 616),
474            InputEdge::new(10105464, 8380092, 1979),
475        ];
476
477        let base_cell = BaseCell {
478            incoming_nodes,
479            outgoing_nodes,
480            edges,
481        };
482        let _matrix_cell = base_cell.process();
483        // assert_eq!(matrix_cell.incoming_nodes, incoming_nodes);
484    }
485}
toolbox_rs/cell.rs

toolbox_rs/
cell.rs
