- Type Parameters:
T
- element type
This data structure supports the following operations:
- Adding an element in $\mathcal{O}(\log 1)$
- Checking if an element in present in $\mathcal{O}(1)$
- Connecting two elements in $\mathcal{O}(\log n)$
- Checking if two elements are connected in $\mathcal{O}(\log n)$
- Removing connection between two nodes in $\mathcal{O}(\log n)$
- Removing an element in $\mathcal{O}(deg(element)\cdot\log n + 1)$
This data structure doesn't allow to store graphs with cycles. Also, the edges are considered to be undirected. The memory complexity is linear in the number of inserted elements. The implementation is based on the Euler tour technique.
For the description of the Euler tour data structure, we refer to the Monika Rauch Henzinger, Valerie King: Randomized dynamic graph algorithms with polylogarithmic time per operation. STOC 1995: 519-527
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
An internal representation of the tree edges.private class
An internal representation of the tree nodes. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate Map
<AVLTree.TreeNode<T>, AVLTree<T>> Mapping from tree minimums to the trees they're stored in.private Map
<T, TreeDynamicConnectivity<T>.Node> Mapping from the user specified values to the internal nodes they're represented byMapping from zero-degree nodes to their trees. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionboolean
Adds anelement
to this data structure.private void
addIfAbsent
(T element) Adds theelement
to this data structure if it is not already presentboolean
Checks if thefirst
andsecond
belong to the same tree.boolean
Checks if this data structure contains theelement
.boolean
Removes an edge between thefirst
andsecond
.private TreeDynamicConnectivity<T>.Node
Returns an internal representation of theelement
getTree
(TreeDynamicConnectivity<T>.Node node) Returns a binary tree, which contains an Euler tour of the tree thenode
belong toboolean
Adds an edge between thefirst
andsecond
elements.private void
makeFirstArc
(AVLTree<T> tree, TreeDynamicConnectivity<T>.Arc arc) Makes thearc
the first arc traversed by the Euler tourprivate void
makeLastArc
(AVLTree<T> tree, TreeDynamicConnectivity<T>.Node node, TreeDynamicConnectivity<T>.Arc arc) Makes thearc
the last arc of thenode
according to the Euler tourprivate void
Makes thenode
the root of the tree.boolean
Removes theelement
from this data structure.
-
Field Details
-
minToTreeMap
Mapping from tree minimums to the trees they're stored in. This map contains one entry per each tree, which has at least two nodes. -
nodeMap
Mapping from the user specified values to the internal nodes they're represented by -
singletonNodes
Mapping from zero-degree nodes to their trees. This map contains one entry for each zero-degree node
-
-
Constructor Details
-
TreeDynamicConnectivity
public TreeDynamicConnectivity()Constructs a newTreeDynamicConnectivity
instance
-
-
Method Details
-
add
Adds anelement
to this data structure. If theelement
has been added before, this method returnsfalse
and has no effect.This method has $\mathcal{O}(\log 1)$ running time complexity
- Parameters:
element
- an element to add- Returns:
true
upon successful modification,false
otherwise
-
remove
Removes theelement
from this data structure. This method has no effect if theelement
hasn't been added to this data structureThis method has $\mathcal{O}(deg(element)\cdot\log n + 1)$ running time complexity
- Parameters:
element
- an element to remove- Returns:
true
upon successful modification,false
otherwise
-
contains
Checks if this data structure contains theelement
.This method has expected $\mathcal{O}(1)$ running time complexity
- Parameters:
element
- an element to check presence of- Returns:
true
if theelement
is stored in this data structure,false
otherwise
-
link
Adds an edge between thefirst
andsecond
elements. The method has no effect if the elements are already connected by some path, i.e. belong to the same tree. In the case some of the nodes haven't been added before, they're added to this data structure.This method has $\mathcal{O}(\log n)$ running time complexity
- Parameters:
first
- an elementsecond
- an element- Returns:
true
upon successful modification,false
otherwise
-
connected
Checks if thefirst
andsecond
belong to the same tree. The method will returnfalse
if either of the elements hasn't been added to this data structureThis method has $\mathcal{O}(\log n)$ running time complexity
- Parameters:
first
- an elementsecond
- an element- Returns:
true
if the elements belong to the same tree,false
otherwise
-
cut
Removes an edge between thefirst
andsecond
. This method doesn't have any effect if there's no edge between these elementsThis method has $\mathcal{O}(\log n)$ running time complexity
- Parameters:
first
- an elementsecond
- an element- Returns:
true
upon successful modification,false
otherwise
-
makeRoot
Makes thenode
the root of the tree. In practice, this means that the value of thenode
is the first in the Euler tour- Parameters:
tree
- a tree thenode
is stored innode
- a node to make a root
-
makeFirstArc
Makes thearc
the first arc traversed by the Euler tour- Parameters:
tree
- corresponding binary tree the Euler tour is stored inarc
- an arc to use for tree re-rooting
-
makeLastArc
private void makeLastArc(AVLTree<T> tree, TreeDynamicConnectivity<T>.Node node, TreeDynamicConnectivity<T>.Arc arc) Makes thearc
the last arc of thenode
according to the Euler tour- Parameters:
tree
- corresponding binary tree the Euler tour is stored innode
- a new root nodearc
- an arc incident to thenode
-
getNode
Returns an internal representation of theelement
- Parameters:
element
- a user specified node element- Returns:
- an internal representation of the
element
-
getTree
Returns a binary tree, which contains an Euler tour of the tree thenode
belong to- Parameters:
node
- a node- Returns:
- a corresponding binary tree an Euler tour is stored in
-
addIfAbsent
Adds theelement
to this data structure if it is not already present- Parameters:
element
- a user specified element
-