V
 the graph vertex typeE
 the graph edge typepublic class HeavyPathDecomposition<V,E> extends Object implements 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 roottoleaf 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.
Modifier and Type  Class and Description 

class 
HeavyPathDecomposition.InternalState
Internal representation of the data

TreeToPathDecompositionAlgorithm.PathDecomposition<V,E>, TreeToPathDecompositionAlgorithm.PathDecompositionImpl<V,E>
Constructor and Description 

HeavyPathDecomposition(Graph<V,E> forest,
Set<V> roots)
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).

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.

Modifier and Type  Method and Description 

Set<E> 
getHeavyEdges()
Set of heavy edges.

HeavyPathDecomposition.InternalState 
getInternalState()
Return the internal representation of the data.

Set<E> 
getLightEdges()
Set of light edges.

TreeToPathDecompositionAlgorithm.PathDecomposition<V,E> 
getPathDecomposition()
Computes a path decomposition.

public HeavyPathDecomposition(Graph<V,E> tree, V root)
tree
 the input treeroot
 the root of the treepublic HeavyPathDecomposition(Graph<V,E> forest, Set<V> roots)
forest
 the input forestroots
 the set of roots of the graphpublic Set<E> getHeavyEdges()
public Set<E> getLightEdges()
public TreeToPathDecompositionAlgorithm.PathDecomposition<V,E> getPathDecomposition()
getPathDecomposition
in interface TreeToPathDecompositionAlgorithm<V,E>
public HeavyPathDecomposition.InternalState getInternalState()
Copyright © 2019. All rights reserved.