- 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 java.lang.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.
-
-
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>
-
-
Field Summary
Fields Modifier and Type Field Description private int[]
component
private int[]
depth
private int[]
firstNodeInPath
private Graph<V,E>
graph
private java.util.Set<E>
heavyEdges
private java.util.List<V>
indexList
private int[]
lengthPath
private java.util.Set<E>
lightEdges
private int
numberOfPaths
private int[]
parent
private int[]
path
private java.util.List<java.util.List<V>>
paths
private int[]
positionInPath
private java.util.Set<V>
roots
private int[]
sizeSubtree
private java.util.Map<V,java.lang.Integer>
vertexMap
-
Constructor Summary
Constructors Constructor Description HeavyPathDecomposition(Graph<V,E> forest, java.util.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 private void
allocateArrays()
private void
decompose()
private void
dfsIterative(int u, int c)
An iterative dfs implementation for computing the paths.java.util.Set<E>
getHeavyEdges()
Set of heavy edges.HeavyPathDecomposition.InternalState
getInternalState()
Return the internal representation of the data.java.util.Set<E>
getLightEdges()
Set of light edges.TreeToPathDecompositionAlgorithm.PathDecomposition<V,E>
getPathDecomposition()
Computes a path decomposition.private void
normalizeGraph()
-
-
-
Field Detail
-
roots
private final java.util.Set<V> roots
-
vertexMap
private java.util.Map<V,java.lang.Integer> vertexMap
-
indexList
private java.util.List<V> 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
private java.util.List<java.util.List<V>> paths
-
heavyEdges
private java.util.Set<E> heavyEdges
-
lightEdges
private java.util.Set<E> lightEdges
-
-
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, java.util.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
-
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
public java.util.Set<E> getHeavyEdges()
Set of heavy edges.- Returns:
- (immutable) set of heavy edges
-
getLightEdges
public java.util.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
-
-