# DND-Tree
A Rust implementation of the **ID‑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>
*This is essentially the DNDTree data structure with the disjoint set tree removed.*
## Algorithmic Complexity
| Query processing | $O(\alpha)$ | $O(h)$ |
| Edge insertion | $O(h)$ | $O(h \cdot \text{nbr}_\text{update})$ |
| Edge deletion | $O(h)$ | $O(h^2 \cdot \text{nbr}_\text{scan})$ |
Where:
- $\alpha$ is the inverse Ackermann function, a small constant ($\alpha$ < 5)
- $h$ is the average vertex depth in the spanning tree.
- $\text{nbr}_\text{update}$ is the time to insert a vertex into neighbors of a vertex or to
delete a vertex from neighbors of a vertex.
- $\text{nbr}_\text{scan}$ is the 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
--- 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) ---
-----------------------------------------------------------------
--- QUERY (WARM) ---
-----------------------------------------------------------------
--- DELETION ---
Tree Edge (Replaced) | 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
--- 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) ---
-----------------------------------------------------------------
--- QUERY (WARM) ---
-----------------------------------------------------------------
--- DELETION ---
Tree Edge (Replaced) | 217.16 | 61.39 | 79.31
```
# Features
## Core ID‑Tree Operations
- Dynamic insertion and deletion of undirected edges.
- Amortized‑efficient connectivity queries.
(For a truly constant query time see the DS-Tree variant from the same paper.)
- Balanced rerooting and centroid maintenance following the original algorithm.
## Graph Utilities
Additional helpers built on top of the ID‑Tree adjacency graph:
- Shortest‑path queries (BFS).
- Fundamental cycle‑basis extraction.
- Connected‑component enumeration.
- Active‑node tracking and filtering.
- Subset‑betweenness computations for specialized workloads.
## Optional Python Bindings
Enable the `python` feature to expose the API to Python via PyO3.
```toml
[features]
python = ["pyo3"]
```