 org.jgrapht.alg.decomposition

## Class HeavyPathDecomposition<V,E>

• Type Parameters:
V - the graph vertex type
E - 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 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.

Author:
Alexandru Valeanu
• ### Nested Class Summary

Nested Classes
Modifier and Type Class and 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 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.
• ### Method Summary

All Methods
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.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### 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 tree
root - 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 forest
roots - 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 interface TreeToPathDecompositionAlgorithm<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 