 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: 519527
 Author:
 Timofey Chudakov


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.boolean
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
.boolean
link(T first, T second)
Adds an edge between thefirst
andsecond
elements.boolean
remove(T element)
Removes theelement
from this data structure.



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

