Module org.jgrapht.core
Package org.jgrapht.alg.connectivity

Class 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

    Author:
    Timofey Chudakov

    • 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