- 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.
- Author:
- Alexandru Valeanu
-
Nested Class Summary
Modifier 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> -
Constructor Summary
ConstructorDescriptionCreate 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 TypeMethodDescriptionSet of heavy edges.Return the internal representation of the data.Set of light edges.Computes a path decomposition.
-
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
-
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
-