Module org.jgrapht.core
Package org.jgrapht.alg.decomposition

Class HeavyPathDecomposition.InternalState

java.lang.Object
org.jgrapht.alg.decomposition.HeavyPathDecomposition.InternalState
Enclosing class:
HeavyPathDecomposition<V,E>
public class HeavyPathDecomposition.InternalState extends Object
Internal representation of the data

  • Constructor Details

    • InternalState

      public InternalState()

  • Method Details

    • 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 Map<V,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 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