Package org.jgrapht.alg.decomposition

Class HeavyPathDecomposition.InternalState

  • Enclosing class:
    HeavyPathDecomposition<V,​E>
    public class HeavyPathDecomposition.InternalState
extends java.lang.Object
    Internal representation of the data

    • Constructor Summary

      Constructors 
      Constructor Description
      InternalState()  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int getComponent​(V v)
      Returns the component id of vertex $v$ in the internal DFS tree/forest.
      int[] getComponentArray()
      Return the internal component array.
      int getDepth​(V v)
      Returns the depth of vertex $v$ in the internal DFS tree/forest.
      int[] getDepthArray()
      Return the internal depth array.
      int[] getFirstNodeInPathArray()
      Return the internal firstNodeInPath array.
      java.util.List<V> getIndexList()
      Return the index list, a mapping from unique integers to vertices.
      V getParent​(V v)
      Returns the parent of vertex $v$ in the internal DFS tree/forest.
      int[] getParentArray()
      Return the internal parent array.
      int[] getPathArray()
      Return the internal path array.
      int[] getPositionInPathArray()
      Return the internal positionInPath array.
      int getSizeSubtree​(V v)
      Returns the size of vertex $v$'s subtree in the internal DFS tree/forest.
      int[] getSizeSubtreeArray()
      Return the internal sizeSubtree array.
      java.util.Map<V,​java.lang.Integer> getVertexMap()
      Return the vertex map, a mapping from vertices to unique integers.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • InternalState

        public InternalState()

    • Method Detail

      • getParent

        public V getParent​(V v)
        Returns the parent of vertex $v$ in the internal DFS tree/forest. If the vertex $v$ has not been explored or it is the root of its tree, $null$ will be returned.
        Parameters:
        v - vertex
        Returns:
        parent of vertex $v$ in the DFS tree/forest

      • getDepth

        public int getDepth​(V v)
        Returns the depth of vertex $v$ in the internal DFS tree/forest.

        The depth of a vertex $v$ is defined as the number of edges traversed on the path from the root of the DFS tree to vertex $v$. The root of each DFS tree has depth 0.

        If the vertex $v$ has not been explored, $-1$ will be returned.

        Parameters:
        v - vertex
        Returns:
        depth of vertex $v$ in the DFS tree/forest

      • getSizeSubtree

        public int getSizeSubtree​(V v)
        Returns the size of vertex $v$'s subtree in the internal DFS tree/forest.

        The size of a vertex $v$'s subtree is defined as the number of vertices in the subtree rooted at $v$ (including $v).

        If the vertex $v$ has not been explored, $0$ will be returned.

        Parameters:
        v - vertex
        Returns:
        size of vertex $v$'s subtree in the DFS tree/forest

      • getComponent

        public int getComponent​(V v)
        Returns the component id of vertex $v$ in the internal DFS tree/forest. For two vertices $u$ and $v$, $component[u] = component[v]$ iff $u$ and $v$ are in the same tree.

        The component ids are numbers between $0$ and $numberOfTrees - 1$.

        If the vertex $v$ has not been explored, $-1$ will be returned.

        Parameters:
        v - vertex
        Returns:
        component id of vertex $v$ in the DFS tree/forest

      • getVertexMap

        public java.util.Map<V,​java.lang.Integer> getVertexMap()
        Return the vertex map, a mapping from vertices to unique integers. For each vertex $v \in V$, let $vertexMap(v) = x$ such that no two vertices share the same x and all x's are integers between $0$ and $|V| - 1$. Let $indexList(x) = v$ be the reverse mapping from integers to vertices. Note: The structure returned is immutable.
        Returns:
        the vertexMap

      • getIndexList

        public java.util.List<V> getIndexList()
        Return the index list, a mapping from unique integers to vertices. For each vertex $v \in V$, let $vertexMap(v) = x$ such that no two vertices share the same x and all x's are integers between $0$ and $|V| - 1$. Let $indexList(x) = v$ be the reverse mapping from integers to vertices. Note: The structure returned is immutable.
        Returns:
        the indexList

      • getDepthArray

        public int[] getDepthArray()
        Return the internal depth array. For each vertex $v \in V$, $depthArray[normalizeVertex(v)] = getDepth(v)$
        Returns:
        internal depth array

      • getSizeSubtreeArray

        public int[] getSizeSubtreeArray()
        Return the internal sizeSubtree array. For each vertex $v$, $sizeSubtreeArray[normalizeVertex(v)] = getSizeSubtree(v)$
        Returns:
        internal sizeSubtree array

      • getComponentArray

        public int[] getComponentArray()
        Return the internal component array. For each vertex $v$, $componentArray[normalizeVertex(v)] = getComponent(v)$
        Returns:
        internal component array

      • getPathArray

        public int[] getPathArray()
        Return the internal path array. For each vertex $v$, $pathArray[normalizeVertex(v)] = i$ iff $v$ appears on path $i$ or $-1$ if $v$ doesn't belong to any path.
        Returns:
        internal path array

      • getPositionInPathArray

        public int[] getPositionInPathArray()
        Return the internal positionInPath array. For each vertex $v$, $positionInPathArray[normalizeVertex(v)] = k$ iff $v$ appears as the $k-th$ vertex on its path (0-indexed) or $-1$ if $v$ doesn't belong to any path.
        Returns:
        internal positionInPath array

      • getFirstNodeInPathArray

        public int[] getFirstNodeInPathArray()
        Return the internal firstNodeInPath array. For each path $i$, $firstNodeInPath[i] = normalizeVertex(v)$ iff $v$ appears as the first vertex on the path.
        Returns:
        internal firstNodeInPath array

      • getParentArray

        public int[] getParentArray()
        Return the internal parent array. For each vertex $v \in V$, $parentArray[normalizeVertex(v)] = normalizeVertex(u)$ if $getParent(v) = u$ or $-1$ if $getParent(v) = null$.
        Returns:
        internal parent array