Algorithm 1: ID-Insert
Input: a new edge (π’, π£) and the ID-Tree index
Output: the updated ID-Tree
1 ππππ‘π’ β compute the root of π’;
2 ππππ‘π£ β compute the root of π£;
/* non-tree edge insertion */
3 if ππππ‘π’ = ππππ‘π£ then
4 if ππππ‘β(π’) < ππππ‘β(π£) then swap(π’, π£);
5 if ππππ‘β(π’) β ππππ‘β(π£) β€ 1 then return;
/* reduce tree deviation */
6 π€ β π’;
7 for 1 β€ π < (ππππ‘β(π’) β ππππ‘β(π£)) / 2 do
8 π€ β ππππππ‘(π€);
9 Unlink(π€);
10 Link(ReRoot(π’), π£, ππππ‘π£ );
11 return;
/* tree edge insertion */
12 if π π‘_π ππ§π(ππππ‘π’) > π π‘_π ππ§π(ππππ‘π£) then
13 swap(π’, π£);
14 swap(ππππ‘π’, ππππ‘π£);
15 Link(ReRoot(π’), π£, ππππ‘π£);
Most processes are the same as that of D-Tree. We first conduct a connectivity
query to identify if two vertices are in the same tree. Lines 3β11 apply the
BFS heuristic for non-tree edge insertion. When the depth gap between π’ and π£
is over 1, a major difference from D-Tree is about the strategy of BFS heuristic in
Line 7. D-Tree uses the threshold ππππ‘β(π’) β ππππ‘β(π£) β 2 instead of ππππ‘β (π’) βππππ‘β(π£)2 . To reduce
the average depth, we add half vertices from π’ to its ancestor with the same depth of π£ to the
- ReRoot(π’) rotates the tree and makes π’ as the new root. It updates the parent-child relationship
and the subtree size attribute from π’ to the original root. The time complexity of ReRoot() is π(ππππ‘β(π’)).
ReRoot from Algorithm 1 of Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended Version):
Algorithm: reroot(nw)
input : tree node nw of D-tree with the root r
output : nw, new root of the rerooted D-tree
1 ch = nw; cur = nw.parent; nw.parent = NULL;
2 while cur, NULL do
3 g = cur.parent
4 cur.parent = ch
5 remove ch from cur.children
6 add cur to ch.children
7 ch = cur; cur = g;
8 while ch.parent, NULL do
9 ch.size = ch.size - ch.parent.size
10 ch.parent.size = ch.parent.size + ch.size
11 ch = ch.parent
12 return uw
- Link(π’, π£, ππππ‘π£) adds a tree ππ’ rooted in π’ to the children of π£. ππππ‘π£ is the root of π£. Given that
the subtree size of π£ is changed, it updates the subtree size for each vertex from π£ to the root.
We apply the centroid heuristic by recording the first vertex with a subtree size larger than π π‘_π ππ§π(ππππ‘π£)/2.
If such a vertex is found, we reroot the tree, and the operator returns the new root.
The time complexity of Link() is π(ππππ‘β(π£)).
Link from Algorithm 6 of Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended Version):
Algorithm: link(ππ’, ππ’, ππ£)
input : a node ππ’ in D-tree π· with the root ππ’, the root ππ£ of a D-tree currently not connected to π· via a tree edge
output : merged D-tree with new tree edge (ππ’, ππ£)
1 add ππ£ to ππ’.πβππππππ
2 ππ£.ππππππ‘ = ππ’
3 π = ππ’ππ; // new centroid
4 π = ππ’
5 while π β ππ’ππ do
6 π.π ππ§π = π.π ππ§π + ππ£.π ππ§π
7 if π.π ππ§π> (ππ’.π ππ§π + ππ£.π ππ§π)/2 and π == ππ’ππ then π = π;
8 π = π.ππππππ‘
9 if π β ππ’ππ and π β ππ’ then ππ’
- Unlink(π’) disconnect the subtree of π’ from the original tree.
All ancestors of π’ are scanned to update the subtree size.
The time complexity of Unlink() is π (ππππ‘β(π’)).
UnLink from Algorithm 7 of Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended Version):
Algorithm: unlink(π’)
input : a non-root node π’ in D-tree π·
output : two D-trees, not connected via tree edges
1 π = π’
2 while π.ππππππ‘ β ππ’ππ do
3 π = π.ππππππ‘
4 π.π ππ§π = π.π ππ§π β π’.π ππ§π
5 remove π’ from π’.ππππππ‘.πβππππππ
6 π’.ππππππ‘ = ππ’ππ
7 return (π’, π)
Algorithm 2: ID-Delete
Input: an existing edge (π’, π£) and the ID-Tree
Output: the updated ID-Tree
1 if ππππππ‘(π’) β π£ β§ ππππππ‘(π£) β π’ then return;
2 if ππππππ‘(π£) = π’ then swap(π’, π£);
3 ππππ‘π£ β Unlink(π’);
/* reduce the worst-case time complexity of searching replacement edge in subtree */
4 if π π‘_π ππ§π(ππππ‘π£) < π π‘_π ππ§π(π’) then swap(π’, ππππ‘π£);
/* search subtree rooted in π’ */
5 π β an empty queue, π.ππ’π β(π’);
6 π β {π’};
/* π maintains all visited vertices */
7 while π β β
do
8 π₯ β π.πππ ();
9 foreach π¦ β π (π₯) do
10 if π¦ = ππππππ‘ (π₯) then continue;
11 else if π₯ = ππππππ‘ (π¦) then
12 π.ππ’π β(π¦);
13 π β π βͺ {π¦};
14 else
15 π π’ππ β true;
16 foreach π€ from π¦ to the root do
17 if π€ β π then
18 π π’ππ β false;
19 break;
20 else
21 π β π βͺ {π€ };
22 if π π’ππ then
23 ππππ‘π£ β Link(ReRoot(π₯), π¦, ππππ‘π£ );
24 return;
Algorithm 3: Disjoint-set operators
1 Procedure Find(π₯)
2 if π₯.ππππππ‘ β π₯ then
3 π₯.ππππππ‘ β Find(π₯);
4 return π₯.ππππππ‘;
5 return π₯;
6 Procedure Union(π₯, π¦)
7 π₯ β Find(π₯);
8 π¦ β Find(π¦);
9 if π₯ = π¦ then return;
10 if π₯.π ππ§π > π¦.π ππ§π then swap(π₯, π¦);
11 π₯.ππππππ‘ β π¦;
12 π¦.π ππ§π β π₯.π ππ§π + π¦.π ππ§π;
Double Linked List
DSnode
- ππ // id of the corresponding vertex;
- ππππππ‘ // pointer to the parentβs DSnode in π·π-tree;
- πππ // previous pointer in the DLL of the parentβs children;
- πππ₯π‘ // next pointer in the DLL of the parentβs children;
- πβππππππ // start position of the DDL of children.
Algorithm 4: DS-Tree operators
1 Procedure UnlinkDS(π’)
2 DSnode(π’).πππ.πππ₯π‘ β DSnode(π’).πππ₯π‘;
3 DSnode(π’).πππ₯π‘.πππ β DSnode(π’).πππ;
4 DSnode(π’).ππππππ‘ β DSnode(π’);
5 DSnode(π’).πππ β Null;
6 DSnode(π’).πππ₯π‘ β Null;
7 Procedure LinkDS(π’, π£)
/* union without find and comparing size */
/* the input satisfies π π‘_π ππ§π (π’) β€ π π‘_π ππ§π (π£) */
/* union two DS-Trees */
8 DSnode(π’).ππππππ‘ β DSnode(π£);
/* add π’ to the new DLL */
9 DSnode(π’).πππ β DSnode(π£).πβππππππ;
10 DSnode(π’).πππ₯π‘ β DSnode(π£).πβππππππ.πππ₯π‘;
11 DSnode(π’).πππ.πππ₯π‘ β DSnode(π’);
12 DSnode(π’).πππ₯π‘ .πππ β DSnode(π’);
13 Procedure FindDS(π’)
14 if DSnode(π’).ππππππ‘ β DSnode(π’) then
15 ππππ‘ β FindDS(DSnode(π’).ππππππ‘.ππ);
16 UnlinkDS(π’);
17 LinkDS(π’, ππππ‘);
18 return ππππ‘;
19 return π’;
20 Procedure Isolate(π’)
/* assign children of π’ to the root */
21 ππππ‘π’ β FindDS(π’);
22 UnlinkDS(π’);
23 foreach child π€ of π’ in π·π-Tree do
24 UnlinkDS(π€);
25 LinkDS(π€, ππππ‘π’ );
26 Procedure ReRootDS(π’)
27 ππππ‘π’ β FindDS(π’);
28 swap(DSnode(π’), DSnode(ππππ‘π’));
29 DSnode(π’).ππ β π’;
30 DSnode(ππππ‘π’).ππ β ππππ‘π’;
Algorithm 5: DND-Insert
Input: an existing edge (π’, π£) and the DND-Trees index
Output: the updated DND-Trees
1 ππππ‘π’ β FindDS(π’);
2 ππππ‘π£ β FindDS(π£);
/* 3 Lines 3β14 of Algorithm 1; */
/* non-tree edge insertion */
3 if ππππ‘π’ = ππππ‘π£ then
4 if ππππ‘β(π’) < ππππ‘β(π£) then swap(π’, π£);
5 if ππππ‘β(π’) β ππππ‘β(π£) β€ 1 then return;
/* reduce tree deviation */
6 π€ β π’;
7 for 1 β€ π < (ππππ‘β(π’) β ππππ‘β(π£)) / 2 do
8 π€ β ππππππ‘(π€);
9 Unlink(π€);
10 Link(ReRoot(π’), π£, ππππ‘π£ );
11 return;
/* tree edge insertion */
12 if π π‘_π ππ§π(ππππ‘π’) > π π‘_π ππ§π(ππππ‘π£) then
13 swap(π’, π£);
14 swap(ππππ‘π’, ππππ‘π£);
4 ReRoot(π’);
5 LinkDS(ππππ‘π’, ππππ‘π£);
6 Link(π’, π£, ππππ‘π£);
Algorithm 6: DND-Delete
Input: an existing edge (π’, π£) and the DND-Trees index
Output: the updated DND-Trees
1 (π’, ππππ‘π£, π π’ππ, π) β ID-Delete(π’, π£);
2 ReRootDS(ππππ‘π£);
3 if π π’ππ then return;
/* π’ is the root of the smaller ID-Tree */
4 Isolate(π’);
5 π β π \ {π’};
6 foreach π€ β π do
7 Isolate(π€);
8 LinkDS(π€, π’);