Class HeavyPathDecomposition<V,E>

java.lang.Object
org.jgrapht.alg.decomposition.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.

  • Field Details

    • graph

      private final Graph<V,E> graph
    • roots

      private final Set<V> roots
    • vertexMap

      private Map<V,Integer> vertexMap
    • indexList

      private 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 List<List<V>> paths
    • heavyEdges

      private Set<E> heavyEdges
    • lightEdges

      private Set<E> lightEdges
  • Constructor Details

    • 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 Details

    • 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) vertex
      c - the component number to be used for u's tree
    • decompose

      private void decompose()
    • 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<V,E>.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