Class HeavyPathDecomposition<V,E>
 java.lang.Object

 org.jgrapht.alg.decomposition.HeavyPathDecomposition<V,E>

 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
TreeToPathDecompositionAlgorithm<V,E>
public class HeavyPathDecomposition<V,E> extends Object implements TreeToPathDecompositionAlgorithm<V,E>
Algorithm for computing the heavy path decomposition of a rooted tree/forest.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.
 Author:
 Alexandru Valeanu


Nested Class Summary
Nested Classes Modifier and Type Class Description class
HeavyPathDecomposition.InternalState
Internal representation of the data
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.TreeToPathDecompositionAlgorithm
TreeToPathDecompositionAlgorithm.PathDecomposition<V,E>, TreeToPathDecompositionAlgorithm.PathDecompositionImpl<V,E>


Constructor Summary
Constructors Constructor 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.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.



Constructor Detail

HeavyPathDecomposition
public 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. 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
public 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). 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 Detail

getHeavyEdges
public Set<E> getHeavyEdges()
Set of heavy edges. Returns:
 (immutable) set of heavy edges

getLightEdges
public Set<E> getLightEdges()
Set of light edges. Returns:
 (immutable) set of light edges

getPathDecomposition
public TreeToPathDecompositionAlgorithm.PathDecomposition<V,E> getPathDecomposition()
Computes a path decomposition. Specified by:
getPathDecomposition
in interfaceTreeToPathDecompositionAlgorithm<V,E>
 Returns:
 a path decomposition

getInternalState
public HeavyPathDecomposition.InternalState 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

