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 Summary

Constructors
Constructor and Description
InternalState()
• ### Method Summary

All Methods
Modifier and Type Method and 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.
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.
Map<V,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 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. Note: the indexing of paths is consistent with PathDecomposition#getPaths(). 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. Note: the indexing of paths is consistent with PathDecomposition#getPaths(). 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