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

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