- java.lang.Object
-
- org.jgrapht.alg.connectivity.TreeDynamicConnectivity<T>
-
- Type Parameters:
T
- element type
public class TreeDynamicConnectivity<T> extends java.lang.Object
Data structure for storing dynamic trees and querying node connectivityThis 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 Classes Modifier and Type Class Description private class
TreeDynamicConnectivity.Arc
An internal representation of the tree edges.private class
TreeDynamicConnectivity.Node
An internal representation of the tree nodes.
-
Field Summary
Fields Modifier and Type Field Description private java.util.Map<AVLTree.TreeNode<T>,AVLTree<T>>
minToTreeMap
Mapping from tree minimums to the trees they're stored in.private java.util.Map<T,TreeDynamicConnectivity.Node>
nodeMap
Mapping from the user specified values to the internal nodes they're represented byprivate java.util.Map<TreeDynamicConnectivity.Node,AVLTree<T>>
singletonNodes
Mapping from zero-degree nodes to their trees.
-
Constructor Summary
Constructors Constructor Description TreeDynamicConnectivity()
Constructs a newTreeDynamicConnectivity
instance
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(T element)
Adds anelement
to this data structure.private void
addIfAbsent(T element)
Adds theelement
to this data structure if it is not already presentboolean
connected(T first, T second)
Checks if thefirst
andsecond
belong to the same tree.boolean
contains(T element)
Checks if this data structure contains theelement
.boolean
cut(T first, T second)
Removes an edge between thefirst
andsecond
.private TreeDynamicConnectivity.Node
getNode(T element)
Returns an internal representation of theelement
private AVLTree<T>
getTree(TreeDynamicConnectivity.Node node)
Returns a binary tree, which contains an Euler tour of the tree thenode
belong toboolean
link(T first, T second)
Adds an edge between thefirst
andsecond
elements.private void
makeFirstArc(AVLTree<T> tree, TreeDynamicConnectivity.Arc arc)
Makes thearc
the first arc traversed by the Euler tourprivate void
makeLastArc(AVLTree<T> tree, TreeDynamicConnectivity.Node node, TreeDynamicConnectivity.Arc arc)
Makes thearc
the last arc of thenode
according to the Euler tourprivate void
makeRoot(AVLTree<T> tree, TreeDynamicConnectivity.Node node)
Makes thenode
the root of the tree.boolean
remove(T element)
Removes theelement
from this data structure.
-
-
-
Field Detail
-
minToTreeMap
private java.util.Map<AVLTree.TreeNode<T>,AVLTree<T>> 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
private java.util.Map<T,TreeDynamicConnectivity.Node> nodeMap
Mapping from the user specified values to the internal nodes they're represented by
-
singletonNodes
private java.util.Map<TreeDynamicConnectivity.Node,AVLTree<T>> singletonNodes
Mapping from zero-degree nodes to their trees. This map contains one entry for each zero-degree node
-
-
Method Detail
-
add
public boolean add(T element)
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
public boolean remove(T element)
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
public boolean contains(T element)
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
public boolean link(T first, T second)
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
public boolean connected(T first, T second)
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
public boolean cut(T first, T second)
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
private void makeRoot(AVLTree<T> tree, TreeDynamicConnectivity.Node node)
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
private void makeFirstArc(AVLTree<T> tree, TreeDynamicConnectivity.Arc arc)
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.Node node, TreeDynamicConnectivity.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
private TreeDynamicConnectivity.Node getNode(T element)
Returns an internal representation of theelement
- Parameters:
element
- a user specified node element- Returns:
- an internal representation of the
element
-
getTree
private AVLTree<T> getTree(TreeDynamicConnectivity.Node node)
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
private void addIfAbsent(T element)
Adds theelement
to this data structure if it is not already present- Parameters:
element
- a user specified element
-
-