Module org.jgrapht.core

Package org.jgrapht.alg.connectivity

Class TreeDynamicConnectivity<T>

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 connectivity

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 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 by
private java.util.Map<TreeDynamicConnectivity.Node,AVLTree<T>>	singletonNodes	Mapping from zero-degree nodes to their trees.

Constructor Summary

Constructors

Constructor	Description
TreeDynamicConnectivity()	Constructs a new TreeDynamicConnectivity instance

Method Summary

Modifier and Type	Method	Description
boolean	add(T element)	Adds an element to this data structure.
private void	addIfAbsent(T element)	Adds the element to this data structure if it is not already present
boolean	connected(T first, T second)	Checks if the first and second belong to the same tree.
boolean	contains(T element)	Checks if this data structure contains the element.
boolean	cut(T first, T second)	Removes an edge between the first and second.
private TreeDynamicConnectivity.Node	getNode(T element)	Returns an internal representation of the element
private AVLTree<T>	getTree(TreeDynamicConnectivity.Node node)	Returns a binary tree, which contains an Euler tour of the tree the node belong to
boolean	link(T first, T second)	Adds an edge between the first and second elements.
private void	makeFirstArc(AVLTree<T> tree, TreeDynamicConnectivity.Arc arc)	Makes the arc the first arc traversed by the Euler tour
private void	makeLastArc(AVLTree<T> tree, TreeDynamicConnectivity.Node node, TreeDynamicConnectivity.Arc arc)	Makes the arc the last arc of the node according to the Euler tour
private void	makeRoot(AVLTree<T> tree, TreeDynamicConnectivity.Node node)	Makes the node the root of the tree.
boolean	remove(T element)	Removes the element from this data structure.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

Constructor Detail

TreeDynamicConnectivity

public TreeDynamicConnectivity()

Constructs a new TreeDynamicConnectivity instance

Method Detail

add

public boolean add(T element)

Adds an element to this data structure. If the element has been added before, this method returns false 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 the element from this data structure. This method has no effect if the element hasn't been added to this data structure

This 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 the element.

This method has expected $\mathcal{O}(1)$ running time complexity

Parameters:

element - an element to check presence of

Returns:

true if the element is stored in this data structure, false otherwise

link

public boolean link(T first,
                    T second)

Adds an edge between the first and second 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 element

second - an element

Returns:

true upon successful modification, false otherwise

connected

public boolean connected(T first,
                         T second)

Checks if the first and second belong to the same tree. The method will return false if either of the elements hasn't been added to this data structure

This method has $\mathcal{O}(\log n)$ running time complexity

Parameters:

first - an element

second - 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 the first and second. This method doesn't have any effect if there's no edge between these elements

This method has $\mathcal{O}(\log n)$ running time complexity

Parameters:

first - an element

second - an element

Returns:

true upon successful modification, false otherwise

makeRoot

private void makeRoot(AVLTree<T> tree,
                      TreeDynamicConnectivity.Node node)

Makes the node the root of the tree. In practice, this means that the value of the node is the first in the Euler tour

Parameters:

tree - a tree the node is stored in

node - a node to make a root

makeFirstArc

private void makeFirstArc(AVLTree<T> tree,
                          TreeDynamicConnectivity.Arc arc)

Makes the arc the first arc traversed by the Euler tour

Parameters:

tree - corresponding binary tree the Euler tour is stored in

arc - an arc to use for tree re-rooting

makeLastArc

private void makeLastArc(AVLTree<T> tree,
                         TreeDynamicConnectivity.Node node,
                         TreeDynamicConnectivity.Arc arc)

Makes the arc the last arc of the node according to the Euler tour

Parameters:

tree - corresponding binary tree the Euler tour is stored in

node - a new root node

arc - an arc incident to the node

getNode

private TreeDynamicConnectivity.Node getNode(T element)

Returns an internal representation of the element

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 the node belong to

Parameters:

node - a node

Returns:

a corresponding binary tree an Euler tour is stored in

addIfAbsent

private void addIfAbsent(T element)

Adds the element to this data structure if it is not already present

Parameters:

element - a user specified element