dndtree 0.3.1

DND-Tree dynamic connectivity data structure
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

# DND-Tree

A Rust implementation of the **DND‑Tree** dynamic connectivity data structure from:

**_Constant-time Connectivity Querying in Dynamic Graphs_**,  
Proceedings of the ACM on Management of Data, Volume 2, Issue 6  
Article No.: 230, Pages 1 - 23  
<https://dl.acm.org/doi/abs/10.1145/3698805>

The Improved D-Tree (ID-Tree) is an improvement on the D-Tree data structure from:

**_Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs._**,
Proc. VLDB Endow. 15, 11 (2022), 3263–3276
<https://www.vldb.org/pvldb/vol15/p3263-chen.pdf>

## Complexity Summary

| Operation        | DND‑Tree     | D‑Tree                                   |
|------------------|--------------|-------------------------------------------|
| Query processing | O(α)         | O(h)                                      |
| Edge insertion   | O(h)         | O(h · nbr_update)                         |
| Edge deletion    | O(h)         | O(h² · nbr_scan)                          |

**Where:**

- **α** — inverse Ackermann function (a very small constant, α < 5)  
- **h** — average vertex depth in the maintained spanning tree  
- **nbr_update** — time to insert or delete a vertex in a neighbor list  
- **nbr_scan** — time to scan all neighbors of a vertex  

# Variants

The full reference C++ implementation has buffered tree operations in-place
which the paper utilizes for temporal capabilities. The Rust implementations
do not have this capability. A part of the buffered operations includes dedup
of tree operations which the Rust implementations also do the remaining
overhead of the buffered operations is minor but measurable.

## C++
CPPDNDTree => Reference implementation accessed via ffi

## Rust
IDTree => Dedicated ID-Tree only build  
DNDTree- => DSU implemented as array back doubly linked list

# Benches

The expensive DSU maintenance operations are avoided by the ID-Tree but it pays
by having to traverse the spanning tree for each query.


## road-usroads-48.mtx

This is a medium sized (126k nodes) graph with average degree 2.
```
                         | CPPDNDTree |  IDTree    | DNDTree
Result Type              | Mean (ns)  | Mean (ns)  | Mean (ns)  
-----------------------------------------------------------------
--- INSERTION ---                                               
Non-Tree Edge            | 2590.14    | 2474.09    | 1699.68    
Tree Edge                | 480.23     | 251.95     | 234.50     
Non-Tree Reroot          | 745.96     | 392.92     | 391.72     
Tree Reroot              | 426.55     | 146.56     | 181.44     
-----------------------------------------------------------------
--- QUERY (COLD) ---                                            
Disconnected             | 120.87     | 2499.36    | 111.04     
Connected                | 75.03      | 4215.66    | 116.51     
-----------------------------------------------------------------
--- QUERY (WARM) ---                                            
Disconnected             | 36.25      | 1716.17    | 30.28      
Connected                | 33.66      | 3291.43    | 28.46      
-----------------------------------------------------------------
--- DELETION ---                                                
Non-Tree Edge            | 215.90     | 74.85      | 81.31      
Tree Edge (Replaced)     | 5209.38    | 3072.58    | 3120.77    
Tree Edge (Split)        | 846.16     | 244.82     | 390.12     
```

## bdo_exploration_graph.mtx

This is a small planar graph (~1k nodes) with average 2.6 degrees.
```
                         | CPPDNDTree | IDTree     | DNDTree
Result Type              | Mean (ns)  | Mean (ns)  | Mean (ns)  
----------------------------------------------------------------
--- INSERTION ---                                         
Non-Tree Edge            | 269.37     | 147.24     | 123.83      
Tree Edge                | 143.41     | 52.24      | 56.48       
Non-Tree Reroot          | 335.36     | 168.10     | 153.10      
Tree Reroot              | 158.55     | 53.06      | 64.88       
-----------------------------------------------------------------
--- QUERY (COLD) ---                                             
Disconnected             | 35.10      | 43.85      | 30.57       
Connected                | 36.26      | 49.94      | 31.21       
-----------------------------------------------------------------
--- QUERY (WARM) ---                                             
Disconnected             | 31.58      | 43.38      | 28.94       
Connected                | 31.65      | 49.28      | 29.01       
-----------------------------------------------------------------
--- DELETION ---                                                 
Non-Tree Edge            | 95.94      | 39.69      | 38.73       
Tree Edge (Replaced)     | 544.92     | 182.60     | 179.81      
Tree Edge (Split)        | 217.16     | 61.39      | 79.31       
```