issundb_core/
lib.rs

1pub(crate) mod columns;
2pub(crate) mod csr;
3mod error;
4mod graph;
5pub(crate) mod matrices;
6mod schema;
7pub(crate) mod storage;
8
9pub use error::Error;
10pub use graph::{DegreeDirection, Graph, ReadTxn, TriangleCountSpec, WriteTxn};
11pub use schema::{
12    DirectedNeighborEntry, EdgeId, EdgeRecord, LabelId, Language, NeighborEntry, NodeId,
13    NodeRecord, PropValue, TypeId, WeightedPath,
14};
15
16#[cfg(test)]
17mod tests {
18    use serde_json::json;
19    use tempfile::TempDir;
20
21    use super::*;
22
23    fn open_tmp() -> (TempDir, Graph) {
24        let dir = TempDir::new().unwrap();
25        let g = Graph::open(dir.path(), 1).unwrap();
26        (dir, g)
27    }
28
29    #[test]
30    fn insert_and_read_node() {
31        let (_dir, g) = open_tmp();
32
33        let id = g
34            .add_node("Person", &json!({ "name": "Alice", "age": 30 }))
35            .unwrap();
36        let record = g.get_node(id).unwrap().expect("node should exist");
37
38        // Deserialize props back and assert
39        let props: serde_json::Value = rmp_serde::from_slice(&record.props).unwrap();
40        assert_eq!(props["name"], "Alice");
41        assert_eq!(props["age"], 30);
42    }
43
44    #[test]
45    fn insert_and_read_edge() {
46        let (_dir, g) = open_tmp();
47
48        let alice = g.add_node("Person", &json!({ "name": "Alice" })).unwrap();
49        let bob = g.add_node("Person", &json!({ "name": "Bob" })).unwrap();
50        let eid = g
51            .add_edge(alice, bob, "KNOWS", &json!({ "since": 2020 }))
52            .unwrap();
53
54        let edge = g.get_edge(eid).unwrap().expect("edge should exist");
55        assert_eq!(edge.src, alice);
56        assert_eq!(edge.dst, bob);
57
58        let neighbors = g.out_neighbors(alice).unwrap();
59        assert_eq!(neighbors.len(), 1);
60        assert_eq!(neighbors[0].node, bob);
61        assert_eq!(neighbors[0].edge, eid);
62    }
63
64    #[test]
65    fn multiple_nodes_get_unique_ids() {
66        let (_dir, g) = open_tmp();
67        let ids: Vec<_> = (0..10)
68            .map(|i| g.add_node("Node", &json!({ "i": i })).unwrap())
69            .collect();
70        let unique: std::collections::HashSet<_> = ids.iter().collect();
71        assert_eq!(unique.len(), 10);
72    }
73
74    #[test]
75    fn nodes_by_label_returns_correct_set() {
76        let (_dir, g) = open_tmp();
77
78        let a = g.add_node("Person", &json!({})).unwrap();
79        let b = g.add_node("Person", &json!({})).unwrap();
80        let _c = g.add_node("Company", &json!({})).unwrap();
81
82        let mut persons = g.nodes_by_label("Person").unwrap();
83        persons.sort_unstable();
84        assert_eq!(persons, vec![a, b]);
85
86        let companies = g.nodes_by_label("Company").unwrap();
87        assert_eq!(companies.len(), 1);
88
89        let missing = g.nodes_by_label("Robot").unwrap();
90        assert!(missing.is_empty());
91    }
92
93    #[test]
94    fn edges_by_type_returns_correct_set() {
95        let (_dir, g) = open_tmp();
96
97        let alice = g.add_node("Person", &json!({})).unwrap();
98        let bob = g.add_node("Person", &json!({})).unwrap();
99        let corp = g.add_node("Company", &json!({})).unwrap();
100
101        let e1 = g.add_edge(alice, bob, "KNOWS", &json!({})).unwrap();
102        let e2 = g.add_edge(alice, corp, "WORKS_AT", &json!({})).unwrap();
103        let e3 = g.add_edge(bob, corp, "WORKS_AT", &json!({})).unwrap();
104
105        let knows = g.edges_by_type("KNOWS").unwrap();
106        assert_eq!(knows, vec![e1]);
107
108        let mut works = g.edges_by_type("WORKS_AT").unwrap();
109        works.sort_unstable();
110        assert_eq!(works, vec![e2, e3]);
111
112        let missing = g.edges_by_type("FOLLOWS").unwrap();
113        assert!(missing.is_empty());
114    }
115
116    #[test]
117    fn label_idx_consistent_across_reopen() {
118        let dir = TempDir::new().unwrap();
119        let id = {
120            let g = Graph::open(dir.path(), 1).unwrap();
121            g.add_node("Person", &json!({})).unwrap()
122        };
123        let g2 = Graph::open(dir.path(), 1).unwrap();
124        let persons = g2.nodes_by_label("Person").unwrap();
125        assert_eq!(persons, vec![id]);
126    }
127
128    #[test]
129    fn csr_hot_path_returns_correct_neighbors() {
130        let (_dir, g) = open_tmp();
131        let a = g.add_node("N", &json!({})).unwrap();
132        let b = g.add_node("N", &json!({})).unwrap();
133        let c = g.add_node("N", &json!({})).unwrap();
134        let e1 = g.add_edge(a, b, "E", &json!({})).unwrap();
135        let e2 = g.add_edge(a, c, "E", &json!({})).unwrap();
136
137        g.rebuild_csr().unwrap();
138
139        let mut out = g.out_neighbors(a).unwrap();
140        out.sort_unstable_by_key(|ne| ne.node);
141        assert_eq!(out.len(), 2);
142        let edge_ids: Vec<_> = out.iter().map(|ne| ne.edge).collect();
143        assert!(edge_ids.contains(&e1));
144        assert!(edge_ids.contains(&e2));
145    }
146
147    #[test]
148    fn csr_fallback_to_lmdb_for_new_nodes() {
149        let (_dir, g) = open_tmp();
150        // Snapshot is built empty on open; nodes added after open are not in it yet.
151        // rebuild_csr is NOT called here, so out_neighbors must fall back to LMDB.
152        let a = g.add_node("N", &json!({})).unwrap();
153        let b = g.add_node("N", &json!({})).unwrap();
154        let eid = g.add_edge(a, b, "E", &json!({})).unwrap();
155
156        let out = g.out_neighbors(a).unwrap();
157        assert_eq!(out.len(), 1);
158        assert_eq!(out[0].edge, eid);
159    }
160
161    #[test]
162    fn csr_snapshot_rebuilds_correctly_on_reopen() {
163        let dir = TempDir::new().unwrap();
164        let (a, b, eid) = {
165            let g = Graph::open(dir.path(), 1).unwrap();
166            let a = g.add_node("N", &json!({})).unwrap();
167            let b = g.add_node("N", &json!({})).unwrap();
168            let eid = g.add_edge(a, b, "E", &json!({})).unwrap();
169            (a, b, eid)
170        };
171        let g2 = Graph::open(dir.path(), 1).unwrap();
172        let out = g2.out_neighbors(a).unwrap();
173        assert_eq!(out.len(), 1);
174        assert_eq!(out[0].node, b);
175        assert_eq!(out[0].edge, eid);
176    }
177
178    // ------------------------------------------------------------------
179    // BFS
180    // ------------------------------------------------------------------
181
182    #[test]
183    fn bfs_hops_zero_returns_start_only() {
184        let (_dir, g) = open_tmp();
185        let a = g.add_node("N", &json!({})).unwrap();
186        let b = g.add_node("N", &json!({})).unwrap();
187        g.add_edge(a, b, "E", &json!({})).unwrap();
188
189        let result = g.bfs(a, 0).unwrap();
190        assert_eq!(result, vec![a]);
191    }
192
193    #[test]
194    fn bfs_linear_chain_respects_hop_limit() {
195        let (_dir, g) = open_tmp();
196        // Build a → b → c → d
197        let a = g.add_node("N", &json!({})).unwrap();
198        let b = g.add_node("N", &json!({})).unwrap();
199        let c = g.add_node("N", &json!({})).unwrap();
200        let d = g.add_node("N", &json!({})).unwrap();
201        g.add_edge(a, b, "E", &json!({})).unwrap();
202        g.add_edge(b, c, "E", &json!({})).unwrap();
203        g.add_edge(c, d, "E", &json!({})).unwrap();
204        g.rebuild_csr().unwrap();
205
206        let mut hop1 = g.bfs(a, 1).unwrap();
207        hop1.sort_unstable();
208        assert_eq!(hop1, vec![a, b]);
209
210        let mut hop2 = g.bfs(a, 2).unwrap();
211        hop2.sort_unstable();
212        assert_eq!(hop2, vec![a, b, c]);
213
214        let mut hop3 = g.bfs(a, 3).unwrap();
215        hop3.sort_unstable();
216        assert_eq!(hop3, vec![a, b, c, d]);
217    }
218
219    #[test]
220    fn bfs_does_not_revisit_nodes_in_a_cycle() {
221        let (_dir, g) = open_tmp();
222        // Build a → b → c → a  (cycle)
223        let a = g.add_node("N", &json!({})).unwrap();
224        let b = g.add_node("N", &json!({})).unwrap();
225        let c = g.add_node("N", &json!({})).unwrap();
226        g.add_edge(a, b, "E", &json!({})).unwrap();
227        g.add_edge(b, c, "E", &json!({})).unwrap();
228        g.add_edge(c, a, "E", &json!({})).unwrap();
229        g.rebuild_csr().unwrap();
230
231        let mut result = g.bfs(a, 10).unwrap();
232        result.sort_unstable();
233        assert_eq!(result, vec![a, b, c]);
234    }
235
236    #[test]
237    fn bfs_isolated_node_returns_only_itself() {
238        let (_dir, g) = open_tmp();
239        let a = g.add_node("N", &json!({})).unwrap();
240        let _b = g.add_node("N", &json!({})).unwrap();
241        g.rebuild_csr().unwrap();
242
243        let result = g.bfs(a, 5).unwrap();
244        assert_eq!(result, vec![a]);
245    }
246
247    #[test]
248    fn bfs_works_via_dynamic_matrix_materialization_without_manual_rebuild() {
249        let (_dir, g) = open_tmp();
250        // Dynamic materialization automatically loads the newly added nodes into CSR snapshot and MatrixSet.
251        let a = g.add_node("N", &json!({})).unwrap();
252        let b = g.add_node("N", &json!({})).unwrap();
253        let c = g.add_node("N", &json!({})).unwrap();
254        g.add_edge(a, b, "E", &json!({})).unwrap();
255        g.add_edge(b, c, "E", &json!({})).unwrap();
256
257        let mut result = g.bfs(a, 2).unwrap();
258        result.sort_unstable();
259        assert_eq!(result, vec![a, b, c]);
260    }
261
262    // ------------------------------------------------------------------
263    // DFS and Traversal Algorithms
264    // ------------------------------------------------------------------
265
266    #[test]
267    fn dfs_hops_zero_returns_start_only() {
268        let (_dir, g) = open_tmp();
269        let a = g.add_node("N", &json!({})).unwrap();
270        let b = g.add_node("N", &json!({})).unwrap();
271        g.add_edge(a, b, "E", &json!({})).unwrap();
272
273        let result = g.dfs(a, 0).unwrap();
274        assert_eq!(result, vec![a]);
275    }
276
277    #[test]
278    fn dfs_linear_chain_pre_order_and_limit() {
279        let (_dir, g) = open_tmp();
280        // Build a → b → c → d
281        let a = g.add_node("N", &json!({})).unwrap();
282        let b = g.add_node("N", &json!({})).unwrap();
283        let c = g.add_node("N", &json!({})).unwrap();
284        let d = g.add_node("N", &json!({})).unwrap();
285        g.add_edge(a, b, "E", &json!({})).unwrap();
286        g.add_edge(b, c, "E", &json!({})).unwrap();
287        g.add_edge(c, d, "E", &json!({})).unwrap();
288        g.rebuild_csr().unwrap();
289
290        let hop1 = g.dfs(a, 1).unwrap();
291        assert_eq!(hop1, vec![a, b]);
292
293        let hop2 = g.dfs(a, 2).unwrap();
294        assert_eq!(hop2, vec![a, b, c]);
295
296        let hop3 = g.dfs(a, 3).unwrap();
297        assert_eq!(hop3, vec![a, b, c, d]);
298    }
299
300    #[test]
301    fn dfs_does_not_loop_on_cycle() {
302        let (_dir, g) = open_tmp();
303        // Build a → b → c → a  (cycle)
304        let a = g.add_node("N", &json!({})).unwrap();
305        let b = g.add_node("N", &json!({})).unwrap();
306        let c = g.add_node("N", &json!({})).unwrap();
307        g.add_edge(a, b, "E", &json!({})).unwrap();
308        g.add_edge(b, c, "E", &json!({})).unwrap();
309        g.add_edge(c, a, "E", &json!({})).unwrap();
310        g.rebuild_csr().unwrap();
311
312        let result = g.dfs(a, 10).unwrap();
313        assert_eq!(result.len(), 3);
314        assert_eq!(result[0], a);
315        assert_eq!(result[1], b);
316        assert_eq!(result[2], c);
317    }
318
319    #[test]
320    fn cycle_detection() {
321        let (_dir, g) = open_tmp();
322
323        // Empty graph is acyclic
324        assert!(!g.detect_cycle().unwrap());
325
326        // Acyclic linear graph
327        let a = g.add_node("N", &json!({})).unwrap();
328        let b = g.add_node("N", &json!({})).unwrap();
329        let c = g.add_node("N", &json!({})).unwrap();
330        g.add_edge(a, b, "E", &json!({})).unwrap();
331        g.add_edge(b, c, "E", &json!({})).unwrap();
332        assert!(!g.detect_cycle().unwrap());
333
334        // Self loop
335        let d = g.add_node("N", &json!({})).unwrap();
336        g.add_edge(d, d, "E", &json!({})).unwrap();
337        assert!(g.detect_cycle().unwrap());
338    }
339
340    #[test]
341    fn cycle_detection_multi_hop() {
342        let (_dir, g) = open_tmp();
343        let a = g.add_node("N", &json!({})).unwrap();
344        let b = g.add_node("N", &json!({})).unwrap();
345        let c = g.add_node("N", &json!({})).unwrap();
346        g.add_edge(a, b, "E", &json!({})).unwrap();
347        g.add_edge(b, c, "E", &json!({})).unwrap();
348        g.add_edge(c, a, "E", &json!({})).unwrap();
349        g.rebuild_csr().unwrap();
350
351        assert!(g.detect_cycle().unwrap());
352    }
353
354    #[test]
355    fn all_neighbors_retrieval() {
356        let (_dir, g) = open_tmp();
357        let a = g.add_node("N", &json!({})).unwrap();
358        let b = g.add_node("N", &json!({})).unwrap();
359        let c = g.add_node("N", &json!({})).unwrap();
360
361        let e1 = g.add_edge(a, b, "OUT", &json!({})).unwrap();
362        let e2 = g.add_edge(c, a, "IN", &json!({})).unwrap();
363
364        g.rebuild_csr().unwrap();
365
366        let mut neighbors = g.all_neighbors(a).unwrap();
367        neighbors.sort_by_key(|ne| ne.node);
368
369        assert_eq!(neighbors.len(), 2);
370
371        // Neighbor b: outgoing edge
372        assert_eq!(neighbors[0].node, b);
373        assert_eq!(neighbors[0].edge, e1);
374        assert!(neighbors[0].outgoing); // is_outgoing == true
375
376        // Neighbor c: incoming edge
377        assert_eq!(neighbors[1].node, c);
378        assert_eq!(neighbors[1].edge, e2);
379        assert!(!neighbors[1].outgoing); // is_outgoing == false
380    }
381
382    // ------------------------------------------------------------------
383    // Phase 2 Pathing Algorithms
384    // ------------------------------------------------------------------
385
386    #[test]
387    fn all_paths_linear_and_multiple() {
388        let (_dir, g) = open_tmp();
389        let a = g.add_node("N", &json!({})).unwrap();
390        let b = g.add_node("N", &json!({})).unwrap();
391        let c = g.add_node("N", &json!({})).unwrap();
392
393        // Single linear path: a → b → c
394        g.add_edge(a, b, "E", &json!({})).unwrap();
395        g.add_edge(b, c, "E", &json!({})).unwrap();
396        g.rebuild_csr().unwrap();
397
398        let paths = g.all_paths(a, c).unwrap();
399        assert_eq!(paths, vec![vec![a, b, c]]);
400
401        // Add a second, parallel path: a → c
402        g.add_edge(a, c, "E", &json!({})).unwrap();
403        g.rebuild_csr().unwrap();
404
405        let mut paths = g.all_paths(a, c).unwrap();
406        paths.sort_by_key(|p| p.len());
407        assert_eq!(paths.len(), 2);
408        assert_eq!(paths[0], vec![a, c]);
409        assert_eq!(paths[1], vec![a, b, c]);
410    }
411
412    #[test]
413    fn all_paths_cyclic_avoids_infinite_loop() {
414        let (_dir, g) = open_tmp();
415        let a = g.add_node("N", &json!({})).unwrap();
416        let b = g.add_node("N", &json!({})).unwrap();
417        let c = g.add_node("N", &json!({})).unwrap();
418        // Path: a → b → c, plus cycle b → a
419        g.add_edge(a, b, "E", &json!({})).unwrap();
420        g.add_edge(b, c, "E", &json!({})).unwrap();
421        g.add_edge(b, a, "E", &json!({})).unwrap();
422        g.rebuild_csr().unwrap();
423
424        let paths = g.all_paths(a, c).unwrap();
425        // Should only return the simple path vec![a, b, c]
426        assert_eq!(paths, vec![vec![a, b, c]]);
427    }
428
429    #[test]
430    fn all_shortest_paths_multiple() {
431        let (_dir, g) = open_tmp();
432        let a = g.add_node("N", &json!({})).unwrap();
433        let b = g.add_node("N", &json!({})).unwrap();
434        let c = g.add_node("N", &json!({})).unwrap();
435        let d = g.add_node("N", &json!({})).unwrap();
436
437        // Two paths of length 2: a → b → d and a → c → d
438        g.add_edge(a, b, "E", &json!({})).unwrap();
439        g.add_edge(b, d, "E", &json!({})).unwrap();
440        g.add_edge(a, c, "E", &json!({})).unwrap();
441        g.add_edge(c, d, "E", &json!({})).unwrap();
442        g.rebuild_csr().unwrap();
443
444        let mut paths = g.all_shortest_paths(a, d).unwrap();
445        paths.sort();
446
447        let mut expected = vec![vec![a, b, d], vec![a, c, d]];
448        expected.sort();
449
450        assert_eq!(paths, expected);
451    }
452
453    #[test]
454    fn all_shortest_paths_unreachable_returns_empty() {
455        let (_dir, g) = open_tmp();
456        let a = g.add_node("N", &json!({})).unwrap();
457        let b = g.add_node("N", &json!({})).unwrap();
458        assert!(g.all_shortest_paths(a, b).unwrap().is_empty());
459    }
460
461    #[test]
462    fn longest_path_selection() {
463        let (_dir, g) = open_tmp();
464        let a = g.add_node("N", &json!({})).unwrap();
465        let b = g.add_node("N", &json!({})).unwrap();
466        let c = g.add_node("N", &json!({})).unwrap();
467
468        // Paths: a → b → c (length 2) and a → c (length 1)
469        g.add_edge(a, b, "E", &json!({})).unwrap();
470        g.add_edge(b, c, "E", &json!({})).unwrap();
471        g.add_edge(a, c, "E", &json!({})).unwrap();
472        g.rebuild_csr().unwrap();
473
474        let path = g.longest_path(a, c).unwrap().unwrap();
475        assert_eq!(path, vec![a, b, c]);
476    }
477
478    #[test]
479    fn longest_path_unreachable_returns_none() {
480        let (_dir, g) = open_tmp();
481        let a = g.add_node("N", &json!({})).unwrap();
482        let b = g.add_node("N", &json!({})).unwrap();
483        assert!(g.longest_path(a, b).unwrap().is_none());
484    }
485
486    // ------------------------------------------------------------------
487    // Phase 3 Dijkstra Algorithm
488    // ------------------------------------------------------------------
489
490    #[test]
491    fn dijkstra_shortest_path_same_node() {
492        let (_dir, g) = open_tmp();
493        let a = g.add_node("N", &json!({})).unwrap();
494        let wp = g.shortest_path_dijkstra(a, a).unwrap().unwrap();
495        assert_eq!(wp.nodes, vec![a]);
496        assert_eq!(wp.total_weight, 0.0);
497    }
498
499    #[test]
500    fn dijkstra_shortest_path_linear_and_weighted_decision() {
501        let (_dir, g) = open_tmp();
502        let a = g.add_node("N", &json!({})).unwrap();
503        let b = g.add_node("N", &json!({})).unwrap();
504        let c = g.add_node("N", &json!({})).unwrap();
505
506        // Path 1: a → b → c (2 hops) with weights 1.5 and 2.0 (total cost = 3.5)
507        g.add_edge(a, b, "E", &json!({ "cost": 1.5 })).unwrap();
508        g.add_edge(b, c, "E", &json!({ "cost": 2.0 })).unwrap();
509
510        // Path 2: a → c (1 hop) with weight 10.0 (total cost = 10.0)
511        g.add_edge(a, c, "E", &json!({ "cost": 10.0 })).unwrap();
512
513        g.rebuild_csr().unwrap();
514
515        // Dijkstra must select the longer hop path (a → b → c) because its total cost (3.5) is smaller than 10.0
516        let wp = g.shortest_path_dijkstra(a, c).unwrap().unwrap();
517        assert_eq!(wp.nodes, vec![a, b, c]);
518        assert_eq!(wp.total_weight, 3.5);
519    }
520
521    #[test]
522    fn dijkstra_shortest_path_defaults_to_one() {
523        let (_dir, g) = open_tmp();
524        let a = g.add_node("N", &json!({})).unwrap();
525        let b = g.add_node("N", &json!({})).unwrap();
526        let c = g.add_node("N", &json!({})).unwrap();
527
528        // Path: a → b (no cost property, defaults to 1.0)
529        g.add_edge(a, b, "E", &json!({})).unwrap();
530        // Path: b → c (non-numeric property, defaults to 1.0)
531        g.add_edge(b, c, "E", &json!({ "cost": "invalid" }))
532            .unwrap();
533
534        g.rebuild_csr().unwrap();
535
536        let wp = g.shortest_path_dijkstra(a, c).unwrap().unwrap();
537        assert_eq!(wp.nodes, vec![a, b, c]);
538        assert_eq!(wp.total_weight, 2.0);
539    }
540
541    #[test]
542    fn dijkstra_shortest_path_unreachable_returns_none() {
543        let (_dir, g) = open_tmp();
544        let a = g.add_node("N", &json!({})).unwrap();
545        let b = g.add_node("N", &json!({})).unwrap();
546        assert!(g.shortest_path_dijkstra(a, b).unwrap().is_none());
547    }
548
549    // ------------------------------------------------------------------
550    // Phase 4 Spanning Forest Algorithm
551    // ------------------------------------------------------------------
552
553    #[test]
554    fn spanning_forest_empty() {
555        let (_dir, g) = open_tmp();
556        let forest = g.spanning_forest("weight", false).unwrap();
557        assert!(forest.is_empty());
558    }
559
560    #[test]
561    fn spanning_forest_min_max_cyclic() {
562        let (_dir, g) = open_tmp();
563        let a = g.add_node("N", &json!({})).unwrap();
564        let b = g.add_node("N", &json!({})).unwrap();
565        let c = g.add_node("N", &json!({})).unwrap();
566
567        // Cyclic triangle graph:
568        // a-b weight 1.0
569        // b-c weight 2.0
570        // a-c weight 3.0
571        let e_ab = g.add_edge(a, b, "E", &json!({ "cost": 1.0 })).unwrap();
572        let e_bc = g.add_edge(b, c, "E", &json!({ "cost": 2.0 })).unwrap();
573        let e_ac = g.add_edge(a, c, "E", &json!({ "cost": 3.0 })).unwrap();
574
575        // Minimum Spanning Forest: should pick e_ab (1.0) and e_bc (2.0)
576        let mut min_forest = g.spanning_forest("cost", false).unwrap();
577        min_forest.sort();
578        let mut expected_min = vec![e_ab, e_bc];
579        expected_min.sort();
580        assert_eq!(min_forest, expected_min);
581
582        // Maximum Spanning Forest: should pick e_ac (3.0) and e_bc (2.0)
583        let mut max_forest = g.spanning_forest("cost", true).unwrap();
584        max_forest.sort();
585        let mut expected_max = vec![e_bc, e_ac];
586        expected_max.sort();
587        assert_eq!(max_forest, expected_max);
588    }
589
590    #[test]
591    fn spanning_forest_disconnected() {
592        let (_dir, g) = open_tmp();
593
594        // Component 1: a-b (cost 5.0)
595        let a = g.add_node("N", &json!({})).unwrap();
596        let b = g.add_node("N", &json!({})).unwrap();
597        let e_ab = g.add_edge(a, b, "E", &json!({ "cost": 5.0 })).unwrap();
598
599        // Component 2: c-d (cost 10.0)
600        let c = g.add_node("N", &json!({})).unwrap();
601        let d = g.add_node("N", &json!({})).unwrap();
602        let e_cd = g.add_edge(c, d, "E", &json!({ "cost": 10.0 })).unwrap();
603
604        g.rebuild_csr().unwrap();
605
606        let mut forest = g.spanning_forest("cost", false).unwrap();
607        forest.sort();
608
609        let mut expected = vec![e_ab, e_cd];
610        expected.sort();
611
612        assert_eq!(forest, expected);
613    }
614
615    // ------------------------------------------------------------------
616    // Phase 5 Label Propagation Algorithm
617    // ------------------------------------------------------------------
618
619    #[test]
620    fn label_propagation_empty() {
621        let (_dir, g) = open_tmp();
622        let labels = g.label_propagation(10).unwrap();
623        assert!(labels.is_empty());
624    }
625
626    #[test]
627    fn label_propagation_singletons() {
628        let (_dir, g) = open_tmp();
629        let a = g.add_node("N", &json!({})).unwrap();
630        let b = g.add_node("N", &json!({})).unwrap();
631
632        let labels = g.label_propagation(10).unwrap();
633        assert_eq!(labels.len(), 2);
634        assert_eq!(labels[&a], a);
635        assert_eq!(labels[&b], b);
636    }
637
638    #[test]
639    fn label_propagation_cliques() {
640        let (_dir, g) = open_tmp();
641
642        // Clique 1: nodes a, b, c (fully connected triangle)
643        let a = g.add_node("N", &json!({})).unwrap();
644        let b = g.add_node("N", &json!({})).unwrap();
645        let c = g.add_node("N", &json!({})).unwrap();
646        g.add_edge(a, b, "E", &json!({})).unwrap();
647        g.add_edge(b, c, "E", &json!({})).unwrap();
648        g.add_edge(c, a, "E", &json!({})).unwrap();
649
650        // Clique 2: nodes d, e, f (fully connected triangle)
651        let d = g.add_node("N", &json!({})).unwrap();
652        let e = g.add_node("N", &json!({})).unwrap();
653        let f = g.add_node("N", &json!({})).unwrap();
654        g.add_edge(d, e, "E", &json!({})).unwrap();
655        g.add_edge(e, f, "E", &json!({})).unwrap();
656        g.add_edge(f, d, "E", &json!({})).unwrap();
657
658        g.rebuild_csr().unwrap();
659
660        let labels = g.label_propagation(100).unwrap();
661        assert_eq!(labels.len(), 6);
662
663        // Within Clique 1, they must all share the same community label
664        let comm1 = labels[&a];
665        assert_eq!(labels[&b], comm1);
666        assert_eq!(labels[&c], comm1);
667
668        // Within Clique 2, they must all share the same community label
669        let comm2 = labels[&d];
670        assert_eq!(labels[&e], comm2);
671        assert_eq!(labels[&f], comm2);
672
673        // Clique 1 and Clique 2 should have different community labels since they are disconnected
674        assert_ne!(comm1, comm2);
675    }
676
677    // ------------------------------------------------------------------
678    // Phase 6 Harmonic closeness centrality
679    // ------------------------------------------------------------------
680
681    #[test]
682    fn harmonic_centrality_empty() {
683        let (_dir, g) = open_tmp();
684        let scores = g.harmonic_centrality().unwrap();
685        assert!(scores.is_empty());
686    }
687
688    #[test]
689    fn harmonic_centrality_singletons() {
690        let (_dir, g) = open_tmp();
691        let a = g.add_node("N", &json!({})).unwrap();
692        let b = g.add_node("N", &json!({})).unwrap();
693
694        let scores = g.harmonic_centrality().unwrap();
695        assert_eq!(scores.len(), 2);
696        assert_eq!(scores[&a], 0.0);
697        assert_eq!(scores[&b], 0.0);
698    }
699
700    #[test]
701    fn harmonic_centrality_linear_chain() {
702        let (_dir, g) = open_tmp();
703        // A -> B -> C
704        let a = g.add_node("N", &json!({})).unwrap();
705        let b = g.add_node("N", &json!({})).unwrap();
706        let c = g.add_node("N", &json!({})).unwrap();
707
708        g.add_edge(a, b, "E", &json!({})).unwrap();
709        g.add_edge(b, c, "E", &json!({})).unwrap();
710
711        g.rebuild_csr().unwrap();
712
713        let scores = g.harmonic_centrality().unwrap();
714        assert_eq!(scores.len(), 3);
715
716        // A can reach B (dist 1) and C (dist 2): centrality = 1/1 + 1/2 = 1.5
717        assert!((scores[&a] - 1.5).abs() < 1e-6);
718        // B can reach C (dist 1): centrality = 1/1 = 1.0
719        assert!((scores[&b] - 1.0).abs() < 1e-6);
720        // C can reach no one: centrality = 0.0
721        assert!((scores[&c] - 0.0).abs() < 1e-6);
722    }
723
724    #[test]
725    fn harmonic_centrality_triangle_clique() {
726        let (_dir, g) = open_tmp();
727        // A -> B -> C -> A
728        let a = g.add_node("N", &json!({})).unwrap();
729        let b = g.add_node("N", &json!({})).unwrap();
730        let c = g.add_node("N", &json!({})).unwrap();
731
732        g.add_edge(a, b, "E", &json!({})).unwrap();
733        g.add_edge(b, c, "E", &json!({})).unwrap();
734        g.add_edge(c, a, "E", &json!({})).unwrap();
735
736        g.rebuild_csr().unwrap();
737
738        let scores = g.harmonic_centrality().unwrap();
739        assert_eq!(scores.len(), 3);
740
741        // Each node can reach one node at distance 1, and the other at distance 2
742        // Centrality for each should be 1/1 + 1/2 = 1.5
743        for &score in scores.values() {
744            assert!((score - 1.5).abs() < 1e-6);
745        }
746    }
747
748    #[test]
749    fn harmonic_centrality_disconnected() {
750        let (_dir, g) = open_tmp();
751        // Component 1: A -> B
752        let a = g.add_node("N", &json!({})).unwrap();
753        let b = g.add_node("N", &json!({})).unwrap();
754        g.add_edge(a, b, "E", &json!({})).unwrap();
755
756        // Component 2: C
757        let c = g.add_node("N", &json!({})).unwrap();
758
759        g.rebuild_csr().unwrap();
760
761        let scores = g.harmonic_centrality().unwrap();
762        assert_eq!(scores.len(), 3);
763        assert!((scores[&a] - 1.0).abs() < 1e-6);
764        assert!((scores[&b] - 0.0).abs() < 1e-6);
765        assert!((scores[&c] - 0.0).abs() < 1e-6);
766    }
767
768    // ------------------------------------------------------------------
769    // Phase 7 Betweenness centrality
770    // ------------------------------------------------------------------
771
772    #[test]
773    fn betweenness_centrality_empty() {
774        let (_dir, g) = open_tmp();
775        let scores = g.betweenness_centrality().unwrap();
776        assert!(scores.is_empty());
777    }
778
779    #[test]
780    fn betweenness_centrality_singletons() {
781        let (_dir, g) = open_tmp();
782        let a = g.add_node("N", &json!({})).unwrap();
783        let b = g.add_node("N", &json!({})).unwrap();
784
785        let scores = g.betweenness_centrality().unwrap();
786        assert_eq!(scores.len(), 2);
787        assert_eq!(scores[&a], 0.0);
788        assert_eq!(scores[&b], 0.0);
789    }
790
791    #[test]
792    fn betweenness_centrality_linear_chain() {
793        let (_dir, g) = open_tmp();
794        // A -> B -> C
795        let a = g.add_node("N", &json!({})).unwrap();
796        let b = g.add_node("N", &json!({})).unwrap();
797        let c = g.add_node("N", &json!({})).unwrap();
798
799        g.add_edge(a, b, "E", &json!({})).unwrap();
800        g.add_edge(b, c, "E", &json!({})).unwrap();
801
802        g.rebuild_csr().unwrap();
803
804        let scores = g.betweenness_centrality().unwrap();
805        assert_eq!(scores.len(), 3);
806        assert_eq!(scores[&a], 0.0);
807        assert_eq!(scores[&b], 1.0);
808        assert_eq!(scores[&c], 0.0);
809    }
810
811    #[test]
812    fn betweenness_centrality_diamond_graph() {
813        let (_dir, g) = open_tmp();
814        //     B
815        //   /   \
816        // A       D
817        //   \   /
818        //     C
819        let a = g.add_node("N", &json!({})).unwrap();
820        let b = g.add_node("N", &json!({})).unwrap();
821        let c = g.add_node("N", &json!({})).unwrap();
822        let d = g.add_node("N", &json!({})).unwrap();
823
824        g.add_edge(a, b, "E", &json!({})).unwrap();
825        g.add_edge(a, c, "E", &json!({})).unwrap();
826        g.add_edge(b, d, "E", &json!({})).unwrap();
827        g.add_edge(c, d, "E", &json!({})).unwrap();
828
829        g.rebuild_csr().unwrap();
830
831        let scores = g.betweenness_centrality().unwrap();
832        assert_eq!(scores.len(), 4);
833        assert_eq!(scores[&a], 0.0);
834        assert_eq!(scores[&d], 0.0);
835        assert!((scores[&b] - 0.5).abs() < 1e-6);
836        assert!((scores[&c] - 0.5).abs() < 1e-6);
837    }
838
839    #[test]
840    fn betweenness_centrality_disconnected() {
841        let (_dir, g) = open_tmp();
842        // Component 1: A -> B -> C
843        let a = g.add_node("N", &json!({})).unwrap();
844        let b = g.add_node("N", &json!({})).unwrap();
845        let c = g.add_node("N", &json!({})).unwrap();
846        g.add_edge(a, b, "E", &json!({})).unwrap();
847        g.add_edge(b, c, "E", &json!({})).unwrap();
848
849        // Component 2: D (isolated)
850        let d = g.add_node("N", &json!({})).unwrap();
851
852        g.rebuild_csr().unwrap();
853
854        let scores = g.betweenness_centrality().unwrap();
855        assert_eq!(scores.len(), 4);
856        assert_eq!(scores[&a], 0.0);
857        assert_eq!(scores[&b], 1.0);
858        assert_eq!(scores[&c], 0.0);
859        assert_eq!(scores[&d], 0.0);
860    }
861
862    // ------------------------------------------------------------------
863    // Phase 8 Strongly connected components
864    // ------------------------------------------------------------------
865
866    #[test]
867    fn strongly_connected_components_empty() {
868        let (_dir, g) = open_tmp();
869        let comps = g.strongly_connected_components().unwrap();
870        assert!(comps.is_empty());
871    }
872
873    #[test]
874    fn strongly_connected_components_singletons() {
875        let (_dir, g) = open_tmp();
876        let a = g.add_node("N", &json!({})).unwrap();
877        let b = g.add_node("N", &json!({})).unwrap();
878
879        let comps = g.strongly_connected_components().unwrap();
880        assert_eq!(comps.len(), 2);
881        assert_ne!(comps[&a], comps[&b]);
882    }
883
884    #[test]
885    fn strongly_connected_components_linear_chain() {
886        let (_dir, g) = open_tmp();
887        // A -> B -> C
888        let a = g.add_node("N", &json!({})).unwrap();
889        let b = g.add_node("N", &json!({})).unwrap();
890        let c = g.add_node("N", &json!({})).unwrap();
891
892        g.add_edge(a, b, "E", &json!({})).unwrap();
893        g.add_edge(b, c, "E", &json!({})).unwrap();
894
895        g.rebuild_csr().unwrap();
896
897        let comps = g.strongly_connected_components().unwrap();
898        assert_eq!(comps.len(), 3);
899        assert_ne!(comps[&a], comps[&b]);
900        assert_ne!(comps[&b], comps[&c]);
901        assert_ne!(comps[&a], comps[&c]);
902    }
903
904    #[test]
905    fn strongly_connected_components_loop() {
906        let (_dir, g) = open_tmp();
907        // A -> B -> C -> A
908        let a = g.add_node("N", &json!({})).unwrap();
909        let b = g.add_node("N", &json!({})).unwrap();
910        let c = g.add_node("N", &json!({})).unwrap();
911
912        g.add_edge(a, b, "E", &json!({})).unwrap();
913        g.add_edge(b, c, "E", &json!({})).unwrap();
914        g.add_edge(c, a, "E", &json!({})).unwrap();
915
916        g.rebuild_csr().unwrap();
917
918        let comps = g.strongly_connected_components().unwrap();
919        assert_eq!(comps.len(), 3);
920        assert_eq!(comps[&a], comps[&b]);
921        assert_eq!(comps[&b], comps[&c]);
922    }
923
924    #[test]
925    fn strongly_connected_components_disconnected_clusters() {
926        let (_dir, g) = open_tmp();
927        // Loop 1: A -> B -> A
928        let a = g.add_node("N", &json!({})).unwrap();
929        let b = g.add_node("N", &json!({})).unwrap();
930        g.add_edge(a, b, "E", &json!({})).unwrap();
931        g.add_edge(b, a, "E", &json!({})).unwrap();
932
933        // Loop 2: C -> D -> C
934        let c = g.add_node("N", &json!({})).unwrap();
935        let d = g.add_node("N", &json!({})).unwrap();
936        g.add_edge(c, d, "E", &json!({})).unwrap();
937        g.add_edge(d, c, "E", &json!({})).unwrap();
938
939        g.rebuild_csr().unwrap();
940
941        let comps = g.strongly_connected_components().unwrap();
942        assert_eq!(comps.len(), 4);
943        assert_eq!(comps[&a], comps[&b]);
944        assert_eq!(comps[&c], comps[&d]);
945        assert_ne!(comps[&a], comps[&c]);
946    }
947
948    // ------------------------------------------------------------------
949    // Phase 9 Degree centrality
950    // ------------------------------------------------------------------
951
952    #[test]
953    fn degree_centrality_empty() {
954        let (_dir, g) = open_tmp();
955        let scores = g.degree_centrality(DegreeDirection::Both).unwrap();
956        assert!(scores.is_empty());
957    }
958
959    #[test]
960    fn degree_centrality_singletons() {
961        let (_dir, g) = open_tmp();
962        let a = g.add_node("N", &json!({})).unwrap();
963        let b = g.add_node("N", &json!({})).unwrap();
964
965        for dir in &[
966            DegreeDirection::In,
967            DegreeDirection::Out,
968            DegreeDirection::Both,
969        ] {
970            let scores = g.degree_centrality(*dir).unwrap();
971            assert_eq!(scores.len(), 2);
972            assert_eq!(scores[&a], 0);
973            assert_eq!(scores[&b], 0);
974        }
975    }
976
977    #[test]
978    fn degree_centrality_linear_chain() {
979        let (_dir, g) = open_tmp();
980        // A -> B -> C
981        let a = g.add_node("N", &json!({})).unwrap();
982        let b = g.add_node("N", &json!({})).unwrap();
983        let c = g.add_node("N", &json!({})).unwrap();
984
985        g.add_edge(a, b, "E", &json!({})).unwrap();
986        g.add_edge(b, c, "E", &json!({})).unwrap();
987
988        g.rebuild_csr().unwrap();
989
990        // Direction::Out
991        let out_scores = g.degree_centrality(DegreeDirection::Out).unwrap();
992        assert_eq!(out_scores[&a], 1);
993        assert_eq!(out_scores[&b], 1);
994        assert_eq!(out_scores[&c], 0);
995
996        // Direction::In
997        let in_scores = g.degree_centrality(DegreeDirection::In).unwrap();
998        assert_eq!(in_scores[&a], 0);
999        assert_eq!(in_scores[&b], 1);
1000        assert_eq!(in_scores[&c], 1);
1001
1002        // Direction::Both
1003        let both_scores = g.degree_centrality(DegreeDirection::Both).unwrap();
1004        assert_eq!(both_scores[&a], 1);
1005        assert_eq!(both_scores[&b], 2);
1006        assert_eq!(both_scores[&c], 1);
1007    }
1008
1009    #[test]
1010    fn degree_centrality_disconnected() {
1011        let (_dir, g) = open_tmp();
1012        // Component 1: A -> B
1013        let a = g.add_node("N", &json!({})).unwrap();
1014        let b = g.add_node("N", &json!({})).unwrap();
1015        g.add_edge(a, b, "E", &json!({})).unwrap();
1016
1017        // Component 2: C (isolated)
1018        let c = g.add_node("N", &json!({})).unwrap();
1019
1020        g.rebuild_csr().unwrap();
1021
1022        let both_scores = g.degree_centrality(DegreeDirection::Both).unwrap();
1023        assert_eq!(both_scores[&a], 1);
1024        assert_eq!(both_scores[&b], 1);
1025        assert_eq!(both_scores[&c], 0);
1026    }
1027
1028    // ------------------------------------------------------------------
1029    // Phase 10 Maximum flow
1030    // ------------------------------------------------------------------
1031
1032    #[test]
1033    fn maximum_flow_trivial() {
1034        let (_dir, g) = open_tmp();
1035        let a = g.add_node("N", &json!({})).unwrap();
1036        let flow = g.maximum_flow(a, a, "cap").unwrap();
1037        assert_eq!(flow, 0.0);
1038    }
1039
1040    #[test]
1041    fn maximum_flow_single_path_bottleneck() {
1042        let (_dir, g) = open_tmp();
1043        // A -(10.0)-> B -(5.0)-> C
1044        let a = g.add_node("N", &json!({})).unwrap();
1045        let b = g.add_node("N", &json!({})).unwrap();
1046        let c = g.add_node("N", &json!({})).unwrap();
1047
1048        g.add_edge(a, b, "E", &json!({ "capacity": 10.0 })).unwrap();
1049        g.add_edge(b, c, "E", &json!({ "capacity": 5.0 })).unwrap();
1050
1051        g.rebuild_csr().unwrap();
1052
1053        let flow = g.maximum_flow(a, c, "capacity").unwrap();
1054        assert!((flow - 5.0).abs() < 1e-6);
1055    }
1056
1057    #[test]
1058    fn maximum_flow_diamond_parallel() {
1059        let (_dir, g) = open_tmp();
1060        //      B (10.0)
1061        //    /   \
1062        // A        D
1063        //    \   /
1064        //      C (5.0)
1065        let a = g.add_node("N", &json!({})).unwrap();
1066        let b = g.add_node("N", &json!({})).unwrap();
1067        let c = g.add_node("N", &json!({})).unwrap();
1068        let d = g.add_node("N", &json!({})).unwrap();
1069
1070        g.add_edge(a, b, "E", &json!({ "cap": 10.0 })).unwrap();
1071        g.add_edge(b, d, "E", &json!({ "cap": 10.0 })).unwrap();
1072        g.add_edge(a, c, "E", &json!({ "cap": 5.0 })).unwrap();
1073        g.add_edge(c, d, "E", &json!({ "cap": 5.0 })).unwrap();
1074
1075        g.rebuild_csr().unwrap();
1076
1077        let flow = g.maximum_flow(a, d, "cap").unwrap();
1078        assert!((flow - 15.0).abs() < 1e-6);
1079    }
1080
1081    #[test]
1082    fn maximum_flow_redirection() {
1083        let (_dir, g) = open_tmp();
1084        // Standard flow network requiring redirection:
1085        // A -> B (3.0), A -> C (2.0)
1086        // B -> C (1.0), B -> D (2.0)
1087        // C -> D (3.0)
1088        // Augmenting path 1: A -> B -> C -> D (flows: 1.0)
1089        // Augmenting path 2: A -> B -> D (flows: 2.0)
1090        // Augmenting path 3: A -> C -> D (flows: 2.0 - but A -> C is only 2.0 and B -> C redirect is used)
1091        // Let's verify max flow is 5.0.
1092        let a = g.add_node("N", &json!({})).unwrap();
1093        let b = g.add_node("N", &json!({})).unwrap();
1094        let c = g.add_node("N", &json!({})).unwrap();
1095        let d = g.add_node("N", &json!({})).unwrap();
1096
1097        g.add_edge(a, b, "E", &json!({ "cap": 3.0 })).unwrap();
1098        g.add_edge(a, c, "E", &json!({ "cap": 2.0 })).unwrap();
1099        g.add_edge(b, c, "E", &json!({ "cap": 1.0 })).unwrap();
1100        g.add_edge(b, d, "E", &json!({ "cap": 2.0 })).unwrap();
1101        g.add_edge(c, d, "E", &json!({ "cap": 3.0 })).unwrap();
1102
1103        g.rebuild_csr().unwrap();
1104
1105        let flow = g.maximum_flow(a, d, "cap").unwrap();
1106        assert!((flow - 5.0).abs() < 1e-6);
1107    }
1108
1109    #[test]
1110    fn maximum_flow_disconnected() {
1111        let (_dir, g) = open_tmp();
1112        let a = g.add_node("N", &json!({})).unwrap();
1113        let b = g.add_node("N", &json!({})).unwrap();
1114        let flow = g.maximum_flow(a, b, "cap").unwrap();
1115        assert_eq!(flow, 0.0);
1116    }
1117
1118    // ------------------------------------------------------------------
1119    // Phase 11 Top-k path search
1120    // ------------------------------------------------------------------
1121
1122    #[test]
1123    fn shortest_path_top_k_trivial() {
1124        let (_dir, g) = open_tmp();
1125        let a = g.add_node("N", &json!({})).unwrap();
1126        let paths = g.shortest_path_top_k(a, a, 3, "weight").unwrap();
1127        assert_eq!(paths.len(), 1);
1128        assert_eq!(paths[0].nodes, vec![a]);
1129        assert_eq!(paths[0].total_weight, 0.0);
1130    }
1131
1132    #[test]
1133    fn shortest_path_top_k_linear_chain() {
1134        let (_dir, g) = open_tmp();
1135        // A -> B -> C
1136        let a = g.add_node("N", &json!({})).unwrap();
1137        let b = g.add_node("N", &json!({})).unwrap();
1138        let c = g.add_node("N", &json!({})).unwrap();
1139
1140        g.add_edge(a, b, "E", &json!({ "cost": 2.0 })).unwrap();
1141        g.add_edge(b, c, "E", &json!({ "cost": 3.0 })).unwrap();
1142
1143        g.rebuild_csr().unwrap();
1144
1145        let paths = g.shortest_path_top_k(a, c, 3, "cost").unwrap();
1146        assert_eq!(paths.len(), 1);
1147        assert_eq!(paths[0].nodes, vec![a, b, c]);
1148        assert!((paths[0].total_weight - 5.0).abs() < 1e-6);
1149    }
1150
1151    #[test]
1152    fn shortest_path_top_k_diamond() {
1153        let (_dir, g) = open_tmp();
1154        //      B (cost 1.0, 1.0)
1155        //    /   \
1156        // A        D
1157        //    \   /
1158        //      C (cost 2.0, 2.0)
1159        let a = g.add_node("N", &json!({})).unwrap();
1160        let b = g.add_node("N", &json!({})).unwrap();
1161        let c = g.add_node("N", &json!({})).unwrap();
1162        let d = g.add_node("N", &json!({})).unwrap();
1163
1164        g.add_edge(a, b, "E", &json!({ "cost": 1.0 })).unwrap();
1165        g.add_edge(b, d, "E", &json!({ "cost": 1.0 })).unwrap();
1166        g.add_edge(a, c, "E", &json!({ "cost": 2.0 })).unwrap();
1167        g.add_edge(c, d, "E", &json!({ "cost": 2.0 })).unwrap();
1168
1169        g.rebuild_csr().unwrap();
1170
1171        let paths = g.shortest_path_top_k(a, d, 3, "cost").unwrap();
1172        assert_eq!(paths.len(), 2);
1173
1174        // Path 1: A -> B -> D (cost 2.0)
1175        assert_eq!(paths[0].nodes, vec![a, b, d]);
1176        assert!((paths[0].total_weight - 2.0).abs() < 1e-6);
1177
1178        // Path 2: A -> C -> D (cost 4.0)
1179        assert_eq!(paths[1].nodes, vec![a, c, d]);
1180        assert!((paths[1].total_weight - 4.0).abs() < 1e-6);
1181    }
1182
1183    #[test]
1184    fn shortest_path_top_k_cyclic() {
1185        let (_dir, g) = open_tmp();
1186        // A -> B (cost 1.0)
1187        // B -> C (cost 1.0)
1188        // C -> D (cost 1.0)
1189        // A -> C (cost 3.0)
1190        // B -> A (cost 1.0 - cycle)
1191        let a = g.add_node("N", &json!({})).unwrap();
1192        let b = g.add_node("N", &json!({})).unwrap();
1193        let c = g.add_node("N", &json!({})).unwrap();
1194        let d = g.add_node("N", &json!({})).unwrap();
1195
1196        g.add_edge(a, b, "E", &json!({ "cost": 1.0 })).unwrap();
1197        g.add_edge(b, c, "E", &json!({ "cost": 1.0 })).unwrap();
1198        g.add_edge(c, d, "E", &json!({ "cost": 1.0 })).unwrap();
1199        g.add_edge(a, c, "E", &json!({ "cost": 3.0 })).unwrap();
1200        g.add_edge(b, a, "E", &json!({ "cost": 1.0 })).unwrap();
1201
1202        g.rebuild_csr().unwrap();
1203
1204        let paths = g.shortest_path_top_k(a, d, 4, "cost").unwrap();
1205        assert_eq!(paths.len(), 2);
1206
1207        // Path 1: A -> B -> C -> D (cost 3.0)
1208        assert_eq!(paths[0].nodes, vec![a, b, c, d]);
1209        assert!((paths[0].total_weight - 3.0).abs() < 1e-6);
1210
1211        // Path 2: A -> C -> D (cost 4.0)
1212        assert_eq!(paths[1].nodes, vec![a, c, d]);
1213        assert!((paths[1].total_weight - 4.0).abs() < 1e-6);
1214    }
1215
1216    #[test]
1217    fn shortest_path_top_k_disconnected() {
1218        let (_dir, g) = open_tmp();
1219        let a = g.add_node("N", &json!({})).unwrap();
1220        let b = g.add_node("N", &json!({})).unwrap();
1221        let paths = g.shortest_path_top_k(a, b, 3, "cost").unwrap();
1222        assert!(paths.is_empty());
1223    }
1224
1225    // ------------------------------------------------------------------
1226    // shortest_path
1227    // ------------------------------------------------------------------
1228
1229    #[test]
1230    fn shortest_path_same_node() {
1231        let (_dir, g) = open_tmp();
1232        let a = g.add_node("N", &json!({})).unwrap();
1233        let path = g.shortest_path(a, a).unwrap();
1234        assert_eq!(path, Some(vec![a]));
1235    }
1236
1237    #[test]
1238    fn shortest_path_direct_edge() {
1239        let (_dir, g) = open_tmp();
1240        let a = g.add_node("N", &json!({})).unwrap();
1241        let b = g.add_node("N", &json!({})).unwrap();
1242        g.add_edge(a, b, "E", &json!({})).unwrap();
1243        g.rebuild_csr().unwrap();
1244        let path = g.shortest_path(a, b).unwrap().unwrap();
1245        assert_eq!(path, vec![a, b]);
1246    }
1247
1248    #[test]
1249    fn shortest_path_multi_hop() {
1250        let (_dir, g) = open_tmp();
1251        let a = g.add_node("N", &json!({})).unwrap();
1252        let b = g.add_node("N", &json!({})).unwrap();
1253        let c = g.add_node("N", &json!({})).unwrap();
1254        g.add_edge(a, b, "E", &json!({})).unwrap();
1255        g.add_edge(b, c, "E", &json!({})).unwrap();
1256        g.rebuild_csr().unwrap();
1257        let path = g.shortest_path(a, c).unwrap().unwrap();
1258        assert_eq!(path, vec![a, b, c]);
1259    }
1260
1261    #[test]
1262    fn shortest_path_returns_shortest_not_any_path() {
1263        let (_dir, g) = open_tmp();
1264        let a = g.add_node("N", &json!({})).unwrap();
1265        let b = g.add_node("N", &json!({})).unwrap();
1266        let c = g.add_node("N", &json!({})).unwrap();
1267        // Two paths: a→b→c (length 2) and a→c (length 1).
1268        g.add_edge(a, b, "E", &json!({})).unwrap();
1269        g.add_edge(b, c, "E", &json!({})).unwrap();
1270        g.add_edge(a, c, "E", &json!({})).unwrap();
1271        g.rebuild_csr().unwrap();
1272        let path = g.shortest_path(a, c).unwrap().unwrap();
1273        assert_eq!(path.len(), 2); // [a, c]
1274    }
1275
1276    #[test]
1277    fn shortest_path_unreachable_returns_none() {
1278        let (_dir, g) = open_tmp();
1279        let a = g.add_node("N", &json!({})).unwrap();
1280        let b = g.add_node("N", &json!({})).unwrap();
1281        g.rebuild_csr().unwrap();
1282        assert!(g.shortest_path(a, b).unwrap().is_none());
1283    }
1284
1285    // ------------------------------------------------------------------
1286    // page_rank
1287    // ------------------------------------------------------------------
1288
1289    #[test]
1290    fn page_rank_all_nodes_present() {
1291        let (_dir, g) = open_tmp();
1292        let a = g.add_node("N", &json!({})).unwrap();
1293        let b = g.add_node("N", &json!({})).unwrap();
1294        let c = g.add_node("N", &json!({})).unwrap();
1295        g.add_edge(a, b, "E", &json!({})).unwrap();
1296        g.add_edge(b, c, "E", &json!({})).unwrap();
1297        g.add_edge(c, a, "E", &json!({})).unwrap();
1298        g.rebuild_csr().unwrap();
1299
1300        let pr = g.page_rank(20, 0.85).unwrap();
1301        assert_eq!(pr.len(), 3);
1302        assert!(pr.contains_key(&a));
1303        // In a balanced cycle, all ranks converge to 1/n.
1304        for &score in pr.values() {
1305            assert!((score - 1.0 / 3.0).abs() < 1e-3, "rank = {score}");
1306        }
1307    }
1308
1309    #[test]
1310    fn page_rank_empty_graph_returns_empty() {
1311        let (_dir, g) = open_tmp();
1312        g.rebuild_csr().unwrap();
1313        assert!(g.page_rank(10, 0.85).unwrap().is_empty());
1314    }
1315
1316    // ------------------------------------------------------------------
1317    // connected_components
1318    // ------------------------------------------------------------------
1319
1320    #[test]
1321    fn connected_components_single_component() {
1322        let (_dir, g) = open_tmp();
1323        let a = g.add_node("N", &json!({})).unwrap();
1324        let b = g.add_node("N", &json!({})).unwrap();
1325        let c = g.add_node("N", &json!({})).unwrap();
1326        g.add_edge(a, b, "E", &json!({})).unwrap();
1327        g.add_edge(b, c, "E", &json!({})).unwrap();
1328
1329        let cc = g.connected_components().unwrap();
1330        assert_eq!(cc.len(), 3);
1331        assert_eq!(cc[&a], cc[&b]);
1332        assert_eq!(cc[&b], cc[&c]);
1333    }
1334
1335    #[test]
1336    fn connected_components_two_components() {
1337        let (_dir, g) = open_tmp();
1338        let a = g.add_node("N", &json!({})).unwrap();
1339        let b = g.add_node("N", &json!({})).unwrap();
1340        let c = g.add_node("N", &json!({})).unwrap();
1341        let d = g.add_node("N", &json!({})).unwrap();
1342        g.add_edge(a, b, "E", &json!({})).unwrap();
1343        g.add_edge(c, d, "E", &json!({})).unwrap();
1344
1345        let cc = g.connected_components().unwrap();
1346        assert_eq!(cc.len(), 4);
1347        assert_eq!(cc[&a], cc[&b]);
1348        assert_eq!(cc[&c], cc[&d]);
1349        assert_ne!(cc[&a], cc[&c]);
1350    }
1351
1352    #[test]
1353    fn connected_components_graphblas_path_node_zero_connected() {
1354        // Regression: after rebuild_csr the GraphBLAS path runs. Node index 0
1355        // must join its component rather than being stranded as a singleton by a
1356        // label value colliding with the semiring's implicit zero.
1357        let (_dir, g) = open_tmp();
1358        let a = g.add_node("N", &json!({})).unwrap();
1359        let b = g.add_node("N", &json!({})).unwrap();
1360        let c = g.add_node("N", &json!({})).unwrap();
1361        g.add_edge(a, b, "E", &json!({})).unwrap();
1362        g.add_edge(b, c, "E", &json!({})).unwrap();
1363        g.rebuild_csr().unwrap();
1364
1365        let cc = g.connected_components().unwrap();
1366        let distinct: std::collections::HashSet<u64> = cc.values().copied().collect();
1367        assert_eq!(distinct.len(), 1, "all three nodes form one component");
1368        assert_eq!(cc[&a], cc[&b]);
1369        assert_eq!(cc[&b], cc[&c]);
1370    }
1371
1372    #[test]
1373    fn connected_components_graphblas_path_keeps_components_separate() {
1374        // Regression: the GraphBLAS WCC propagation must reduce over neighbor
1375        // labels, not the adjacency matrix value. Two disjoint edges A->B and
1376        // C->D form two components; a MinFirst semiring collapses every
1377        // edge-touching node into one component, so this guards MinSecond.
1378        let (_dir, g) = open_tmp();
1379        let a = g.add_node("N", &json!({})).unwrap();
1380        let b = g.add_node("N", &json!({})).unwrap();
1381        let c = g.add_node("N", &json!({})).unwrap();
1382        let d = g.add_node("N", &json!({})).unwrap();
1383        g.add_edge(a, b, "E", &json!({})).unwrap();
1384        g.add_edge(c, d, "E", &json!({})).unwrap();
1385        g.rebuild_csr().unwrap();
1386
1387        let cc = g.connected_components().unwrap();
1388        assert_eq!(cc.len(), 4);
1389        assert_eq!(cc[&a], cc[&b]);
1390        assert_eq!(cc[&c], cc[&d]);
1391        assert_ne!(cc[&a], cc[&c], "disjoint edges must be separate components");
1392    }
1393
1394    #[test]
1395    fn connected_components_weakly_connected_via_reverse_edge() {
1396        let (_dir, g) = open_tmp();
1397        // a → b and b → c: all three are weakly connected.
1398        let a = g.add_node("N", &json!({})).unwrap();
1399        let b = g.add_node("N", &json!({})).unwrap();
1400        let c = g.add_node("N", &json!({})).unwrap();
1401        g.add_edge(a, b, "E", &json!({})).unwrap();
1402        // Only edge from a to b; c is reachable from b, not from a → c.
1403        g.add_edge(c, b, "E", &json!({})).unwrap();
1404
1405        let cc = g.connected_components().unwrap();
1406        assert_eq!(cc[&a], cc[&b]);
1407        assert_eq!(cc[&b], cc[&c]);
1408    }
1409
1410    #[test]
1411    fn label_name_roundtrip() {
1412        let (_dir, g) = open_tmp();
1413        let id = g.add_node("Person", &json!({})).unwrap();
1414        let rec = g.get_node(id).unwrap().unwrap();
1415        assert_eq!(
1416            g.label_name(rec.primary_label().unwrap())
1417                .unwrap()
1418                .as_deref(),
1419            Some("Person")
1420        );
1421    }
1422
1423    #[test]
1424    fn type_name_roundtrip() {
1425        let (_dir, g) = open_tmp();
1426        let a = g.add_node("N", &json!({})).unwrap();
1427        let b = g.add_node("N", &json!({})).unwrap();
1428        let eid = g.add_edge(a, b, "KNOWS", &json!({})).unwrap();
1429        let rec = g.get_edge(eid).unwrap().unwrap();
1430        assert_eq!(
1431            g.type_name(rec.edge_type).unwrap().as_deref(),
1432            Some("KNOWS")
1433        );
1434    }
1435
1436    #[test]
1437    fn label_name_unknown_id_returns_none() {
1438        let (_dir, g) = open_tmp();
1439        assert!(g.label_name(9999).unwrap().is_none());
1440    }
1441
1442    #[test]
1443    fn graphblas_bfs_page_rank_sssp() {
1444        let (_dir, g) = open_tmp();
1445        let a = g.add_node("Person", &json!({})).unwrap();
1446        let b = g.add_node("Person", &json!({})).unwrap();
1447        let c = g.add_node("Person", &json!({})).unwrap();
1448        g.add_edge(a, b, "KNOWS", &json!({})).unwrap();
1449        g.add_edge(b, c, "KNOWS", &json!({})).unwrap();
1450        g.rebuild_csr().unwrap();
1451
1452        // BFS from a with 1 hop should reach a and b only.
1453        let bfs1 = g.bfs_graphblas(a, 1).unwrap();
1454        assert!(bfs1.contains(&a));
1455        assert!(bfs1.contains(&b));
1456        assert!(!bfs1.contains(&c));
1457
1458        // BFS from a with 2 hops should reach all three.
1459        let bfs2 = g.bfs_graphblas(a, 2).unwrap();
1460        assert!(bfs2.contains(&a));
1461        assert!(bfs2.contains(&b));
1462        assert!(bfs2.contains(&c));
1463
1464        // PageRank returns one entry per node.
1465        let pr = g.page_rank_graphblas(10, 0.85).unwrap();
1466        assert_eq!(pr.len(), 3);
1467        for &id in &[a, b, c] {
1468            assert!(pr.contains_key(&id));
1469            assert!(*pr.get(&id).unwrap() > 0.0);
1470        }
1471
1472        // SSSP a→c should return the two-hop path [a, b, c].
1473        let path = g
1474            .shortest_path_graphblas(a, c)
1475            .unwrap()
1476            .expect("path a→c must exist");
1477        assert_eq!(path, vec![a, b, c]);
1478
1479        // SSSP a→a is a trivial path.
1480        let trivial = g.shortest_path_graphblas(a, a).unwrap().unwrap();
1481        assert_eq!(trivial, vec![a]);
1482
1483        // SSSP in reverse direction (no edge) returns None.
1484        assert!(g.shortest_path_graphblas(c, a).unwrap().is_none());
1485    }
1486}
1487
1488#[cfg(test)]
1489mod prop_tests {
1490    use proptest::prelude::*;
1491    use tempfile::TempDir;
1492
1493    use super::*;
1494
1495    // Each test opens one LMDB environment for all iterations so that the
1496    // process does not exhaust lock-file descriptors across hundreds of
1497    // open/close cycles.  The graph accumulates state across iterations; all
1498    // assertions are stated in terms of the incremental deltas observed within
1499    // each iteration, not absolute counts.
1500
1501    /// Node IDs returned by successive `add_node` calls are strictly increasing.
1502    #[test]
1503    fn node_ids_are_monotonically_increasing() {
1504        let _dir = TempDir::new().unwrap();
1505        let g = Graph::open(_dir.path(), 1).unwrap();
1506        let config = ProptestConfig {
1507            fork: false,
1508            cases: 200,
1509            ..Default::default()
1510        };
1511        proptest!(config, |(label in "[A-Z]{1,4}")| {
1512            let a = g.add_node(&label, &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1513            let b = g.add_node(&label, &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1514            prop_assert!(a < b);
1515        });
1516    }
1517
1518    /// Edge IDs returned by successive `add_edge` calls are strictly increasing.
1519    #[test]
1520    fn edge_ids_are_monotonically_increasing() {
1521        let _dir = TempDir::new().unwrap();
1522        let g = Graph::open(_dir.path(), 1).unwrap();
1523        let src = g.add_node("N", &()).unwrap();
1524        let dst = g.add_node("N", &()).unwrap();
1525        let config = ProptestConfig {
1526            fork: false,
1527            cases: 200,
1528            ..Default::default()
1529        };
1530        proptest!(config, |(_dummy in 0u8..=255)| {
1531            let a = g.add_edge(src, dst, "E", &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1532            let b = g.add_edge(src, dst, "E", &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1533            prop_assert!(a < b);
1534        });
1535    }
1536
1537    /// Every pair of `add_node` calls produces two distinct IDs.
1538    #[test]
1539    fn node_ids_are_unique() {
1540        let _dir = TempDir::new().unwrap();
1541        let g = Graph::open(_dir.path(), 1).unwrap();
1542        let config = ProptestConfig {
1543            fork: false,
1544            cases: 200,
1545            ..Default::default()
1546        };
1547        proptest!(config, |(_dummy in 0u8..=255)| {
1548            let a = g.add_node("N", &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1549            let b = g.add_node("N", &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1550            prop_assert_ne!(a, b);
1551        });
1552    }
1553
1554    /// Every `add_edge(src, dst)` adds exactly one entry to `out_neighbors(src)`
1555    /// and one to `in_neighbors(dst)`.
1556    #[test]
1557    fn adjacency_round_trip() {
1558        let _dir = TempDir::new().unwrap();
1559        let g = Graph::open(_dir.path(), 1).unwrap();
1560        let src = g.add_node("N", &()).unwrap();
1561        let dst = g.add_node("N", &()).unwrap();
1562        let config = ProptestConfig {
1563            fork: false,
1564            cases: 200,
1565            ..Default::default()
1566        };
1567        proptest!(config, |(_dummy in 0u8..=255)| {
1568            let before_out = g.out_neighbors(src).unwrap().len();
1569            let before_in = g.in_neighbors(dst).unwrap().len();
1570            let eid = g.add_edge(src, dst, "E", &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1571            let out: Vec<_> = g.out_neighbors(src).unwrap();
1572            let inc: Vec<_> = g.in_neighbors(dst).unwrap();
1573            prop_assert_eq!(out.len(), before_out + 1);
1574            prop_assert_eq!(inc.len(), before_in + 1);
1575            prop_assert!(out.iter().any(|ne| ne.edge == eid));
1576            prop_assert!(inc.iter().any(|ne| ne.edge == eid));
1577        });
1578    }
1579
1580    /// Each `add_node("Target", ...)` call adds exactly one entry to
1581    /// `nodes_by_label("Target")`, and nodes of other labels are never included.
1582    #[test]
1583    fn label_index_exact_membership() {
1584        let _dir = TempDir::new().unwrap();
1585        let g = Graph::open(_dir.path(), 1).unwrap();
1586        let config = ProptestConfig {
1587            fork: false,
1588            cases: 200,
1589            ..Default::default()
1590        };
1591        proptest!(config, |(insert_other in proptest::bool::ANY)| {
1592            let before = g.nodes_by_label("Target").unwrap().len();
1593            let id = g.add_node("Target", &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1594            if insert_other {
1595                g.add_node("Other", &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1596            }
1597            let after = g.nodes_by_label("Target").unwrap();
1598            prop_assert_eq!(after.len(), before + 1);
1599            prop_assert!(after.contains(&id));
1600        });
1601    }
1602
1603    /// Each `add_edge(..., "Target", ...)` call adds exactly one entry to
1604    /// `edges_by_type("Target")`, and edges of other types are never included.
1605    #[test]
1606    fn type_index_exact_membership() {
1607        let _dir = TempDir::new().unwrap();
1608        let g = Graph::open(_dir.path(), 1).unwrap();
1609        let a = g.add_node("N", &()).unwrap();
1610        let b = g.add_node("N", &()).unwrap();
1611        let config = ProptestConfig {
1612            fork: false,
1613            cases: 200,
1614            ..Default::default()
1615        };
1616        proptest!(config, |(insert_other in proptest::bool::ANY)| {
1617            let before = g.edges_by_type("Target").unwrap().len();
1618            let eid = g.add_edge(a, b, "Target", &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1619            if insert_other {
1620                g.add_edge(a, b, "Other", &()).map_err(|e| TestCaseError::fail(e.to_string()))?;
1621            }
1622            let after = g.edges_by_type("Target").unwrap();
1623            prop_assert_eq!(after.len(), before + 1);
1624            prop_assert!(after.contains(&eid));
1625        });
1626    }
1627}
1628
1629#[cfg(test)]
1630mod differential_tests {
1631    use std::collections::HashMap;
1632
1633    use proptest::prelude::*;
1634    use serde_json::json;
1635    use tempfile::TempDir;
1636
1637    use super::*;
1638
1639    fn open_tmp() -> (TempDir, Graph) {
1640        let dir = TempDir::new().unwrap();
1641        let g = Graph::open(dir.path(), 1).unwrap();
1642        (dir, g)
1643    }
1644
1645    /// Union-find reference for weakly connected components: treat every edge
1646    /// as undirected and union its endpoints. This is the textbook definition
1647    /// the GraphBLAS min-label propagation in `connected_components` computes.
1648    fn reference_wcc(n: usize, edges: &[(usize, usize)]) -> Vec<usize> {
1649        fn find(parent: &mut [usize], mut x: usize) -> usize {
1650            while parent[x] != x {
1651                parent[x] = parent[parent[x]];
1652                x = parent[x];
1653            }
1654            x
1655        }
1656        let mut parent: Vec<usize> = (0..n).collect();
1657        for &(a, b) in edges {
1658            let (ra, rb) = (find(&mut parent, a), find(&mut parent, b));
1659            if ra != rb {
1660                parent[ra] = rb;
1661            }
1662        }
1663        (0..n).map(|i| find(&mut parent, i)).collect()
1664    }
1665
1666    /// Two component labelings agree iff they induce the same partition: nodes
1667    /// share a label under one exactly when they share a label under the other.
1668    /// This is convention-independent, so it does not depend on which integer
1669    /// each side picked as a component representative.
1670    fn same_partition<A: Eq, B: Eq>(xs: &[A], ys: &[B]) -> bool {
1671        let n = xs.len();
1672        (0..n).all(|i| (0..n).all(|j| (xs[i] == xs[j]) == (ys[i] == ys[j])))
1673    }
1674
1675    proptest! {
1676        #![proptest_config(ProptestConfig { cases: 64, ..ProptestConfig::default() })]
1677
1678        #[test]
1679        fn connected_components_matches_union_find(
1680            n in 1usize..12,
1681            edges in prop::collection::vec((0usize..12, 0usize..12), 0..24),
1682        ) {
1683            // A fresh graph per case: whole-graph algorithms cannot share state.
1684            let edges: Vec<(usize, usize)> =
1685                edges.into_iter().filter(|&(a, b)| a < n && b < n).collect();
1686            let (_dir, g) = open_tmp();
1687            let ids: Vec<NodeId> = (0..n)
1688                .map(|_| g.add_node("N", &json!({})).unwrap())
1689                .collect();
1690            for &(a, b) in &edges {
1691                g.add_edge(ids[a], ids[b], "E", &json!({})).unwrap();
1692            }
1693            g.rebuild_csr().unwrap();
1694
1695            let got: HashMap<NodeId, u64> = g.connected_components().unwrap();
1696            let impl_labels: Vec<u64> = ids.iter().map(|id| got[id]).collect();
1697            let ref_labels = reference_wcc(n, &edges);
1698
1699            prop_assert!(
1700                same_partition(&impl_labels, &ref_labels),
1701                "WCC partition mismatch: impl={:?} ref={:?} edges={:?}",
1702                impl_labels, ref_labels, edges
1703            );
1704        }
1705    }
1706}
issundb_core/lib.rs

issundb_core/
lib.rs
