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 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

  • Field Details

    • minToTreeMap

      private 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 Map<T,TreeDynamicConnectivity<T>.Node> nodeMap
      Mapping from the user specified values to the internal nodes they're represented by

    • singletonNodes

      private Map<TreeDynamicConnectivity<T>.Node,AVLTree<T>> 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 new TreeDynamicConnectivity instance

  • Method Details

    • 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<T>.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<T>.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<T>.Node node, TreeDynamicConnectivity<T>.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<T>.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<T>.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