- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
TreeToPathDecompositionAlgorithm<V,
E>
Heavy path decomposition is a technique for decomposing a rooted tree/forest into a set of disjoint paths.
The techniques was first introduced in Sleator, D. D.; Tarjan, R. E. (1983). "A Data Structure for Dynamic Trees". Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81 doi:10.1145/800076.802464
In a heavy path decomposition, the edges set is partitioned into two sets, a set of heavy edges and a set of light ones according to the relative number of nodes in the vertex's subtree. We define the size of a vertex v in the forest, denoted by size(v), to be the number of descendants of v, including v itself. We define a tree edge (v,parent(v)) to be heavy if $2*size(v)$ > $size(parent(v))$ and light, otherwise. The set of heavy edges form the edges of the decomposition.
A benefit of this decomposition is that on any root-to-leaf path of a tree with n nodes, there can be at most $log_2(n)$ light edges.
This implementation runs in $O(|V|)$ time and requires $O(|V|)$ extra memory, where $|V|$ is the number of vertices in the tree/forest.
Note: If an edge is not reachable from any of the roots provided, then that edge is neither light nor heavy.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionclass
Internal representation of the dataNested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.TreeToPathDecompositionAlgorithm
TreeToPathDecompositionAlgorithm.PathDecomposition<V,
E>, TreeToPathDecompositionAlgorithm.PathDecompositionImpl<V, E> -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int[]
private int[]
private int[]
private int[]
private int
private int[]
private int[]
private int[]
private int[]
-
Constructor Summary
ConstructorsConstructorDescriptionCreate an instance with a reference to the forest that we will decompose and to the sets of roots of the forest (one root per tree).HeavyPathDecomposition
(Graph<V, E> tree, V root) Create an instance with a reference to the tree that we will decompose and to the root of the tree. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
private void
private void
dfsIterative
(int u, int c) An iterative dfs implementation for computing the paths.Set of heavy edges.Return the internal representation of the data.Set of light edges.Computes a path decomposition.private void
-
Field Details
-
graph
-
roots
-
vertexMap
-
indexList
-
sizeSubtree
private int[] sizeSubtree -
parent
private int[] parent -
depth
private int[] depth -
component
private int[] component -
path
private int[] path -
lengthPath
private int[] lengthPath -
positionInPath
private int[] positionInPath -
firstNodeInPath
private int[] firstNodeInPath -
numberOfPaths
private int numberOfPaths -
paths
-
heavyEdges
-
lightEdges
-
-
Constructor Details
-
HeavyPathDecomposition
Create an instance with a reference to the tree that we will decompose and to the root of the tree. Note: The constructor will NOT check if the input graph is a valid tree.- Parameters:
tree
- the input treeroot
- the root of the tree
-
HeavyPathDecomposition
Create an instance with a reference to the forest that we will decompose and to the sets of roots of the forest (one root per tree). Note: If two roots appear in the same tree, an error will be thrown. Note: The constructor will NOT check if the input graph is a valid forest.- Parameters:
forest
- the input forestroots
- the set of roots of the graph
-
-
Method Details
-
allocateArrays
private void allocateArrays() -
normalizeGraph
private void normalizeGraph() -
dfsIterative
private void dfsIterative(int u, int c) An iterative dfs implementation for computing the paths. For each node u we have to execute two sequences of operations: 1: before the 'recursive' call (the then part of the if-statement) 2: after the 'recursive' call (the else part of the if-statement)- Parameters:
u
- the (normalized) vertexc
- the component number to be used for u's tree
-
decompose
private void decompose() -
getHeavyEdges
Set of heavy edges.- Returns:
- (immutable) set of heavy edges
-
getLightEdges
Set of light edges.- Returns:
- (immutable) set of light edges
-
getPathDecomposition
Computes a path decomposition.- Specified by:
getPathDecomposition
in interfaceTreeToPathDecompositionAlgorithm<V,
E> - Returns:
- a path decomposition
-
getInternalState
Return the internal representation of the data. Note: this data representation is intended only for use by other components within JGraphT- Returns:
- the internal state representation
-