Package org.jgrapht.alg.flow

Class GusfieldGomoryHuCutTree<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    FlowAlgorithm<V,​E>, MaximumFlowAlgorithm<V,​E>, MinimumSTCutAlgorithm<V,​E>
    public class GusfieldGomoryHuCutTree<V,​E>
extends Object
implements MaximumFlowAlgorithm<V,​E>, MinimumSTCutAlgorithm<V,​E>
    This class computes a Gomory-Hu tree (GHT) using the algorithm proposed by Dan Gusfield. For a definition of GHTs, refer to: Gomory, R., Hu, T. Multi-terminal network flows. Journal of the Socieity for Industrial and Applied mathematics, 9(4), p551-570, 1961. GHTs can be used to efficiently query the maximum flows and minimum cuts for all pairs of vertices. The algorithm is described in: Gusfield, D, Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 19(1), p142-155, 1990
    In an undirected graph, there exist $\frac{n(n-1)}{2}$ different vertex pairs. This class computes the maximum flow/minimum cut between each of these pairs efficiently by performing exactly $(n-1)$ minimum $s-t$ cut computations. If your application needs fewer than $n-1$ flow/cut computations, consider computing the maximum flows/minimum cuts manually through MaximumFlowAlgorithm/MinimumSTCutAlgorithm.

    The runtime complexity of this class is $O((V-1)Q)$, where $Q$ is the runtime complexity of the algorithm used to compute $s-t$ cuts in the graph. By default, this class uses the PushRelabelMFImpl implementation to calculate minimum s-t cuts. This class has a runtime complexity of $O(V^3)$, resulting in a $O(V^4)$ runtime complexity for the overall algorithm.

    Note: this class performs calculations in a lazy manner. The GHT is not calculated until the first invocation of getMaximumFlowValue(Object, Object) or getGomoryHuTree(). Moreover, this class only calculates the value of the maximum flow between a source-destination pair; it does not calculate the corresponding flow per edge. If you need to know the exact flow through an edge, use one of the alternative MaximumFlowAlgorithm implementations.

    In contrast to an Equivalent Flow Tree (GusfieldEquivalentFlowTree), Gomory-Hu trees also provide all minimum cuts for all pairs of vertices!

    This class does not support changes to the underlying graph. The behavior of this class is undefined when the graph is modified after instantiating this class.

    Author:
    Joris Kinable

    • Constructor Detail

      • GusfieldGomoryHuCutTree

        public GusfieldGomoryHuCutTree​(Graph<V,​E> network)
        Constructs a new GusfieldEquivalentFlowTree instance.
        Parameters:
        network - input graph

      • GusfieldGomoryHuCutTree

        public GusfieldGomoryHuCutTree​(Graph<V,​E> network,
                               double epsilon)
        Constructs a new GusfieldEquivalentFlowTree instance.
        Parameters:
        network - input graph
        epsilon - precision

      • GusfieldGomoryHuCutTree

        public GusfieldGomoryHuCutTree​(Graph<V,​E> network,
                               MinimumSTCutAlgorithm<V,​E> minimumSTCutAlgorithm)
        Constructs a new GusfieldEquivalentFlowTree instance.
        Parameters:
        network - input graph
        minimumSTCutAlgorithm - algorithm used to compute the minimum s-t cuts