org.jgrapht.alg.flow

## Class GusfieldGomoryHuCutTree<V,E>

• Type Parameters:
`V` - the graph vertex type
`E` - the graph edge type
All Implemented Interfaces:
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 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 `calculateMaximumFlow(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

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm

`MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>`
• ### Constructor Summary

Constructors
Constructor and Description
`GusfieldGomoryHuCutTree(Graph<V,E> network)`
Constructs a new GusfieldEquivalentFlowTree instance.
```GusfieldGomoryHuCutTree(Graph<V,E> network, double epsilon)```
Constructs a new GusfieldEquivalentFlowTree instance.
```GusfieldGomoryHuCutTree(Graph<V,E> network, MinimumSTCutAlgorithm<V,E> minimumSTCutAlgorithm)```
Constructs a new GusfieldEquivalentFlowTree instance.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`double` ```calculateMaximumFlow(V source, V sink)```
Returns the Maximum flow between source and sink.
`double` `calculateMinCut()`
Calculates the minimum cut in the graph, that is, the minimum cut over all s-t pairs.
`double` ```calculateMinCut(V source, V sink)```
Computes a minimum capacity s-t cut.
`double` `getCutCapacity()`
Returns the capacity of the cut obtained after the last invocation of `MinimumSTCutAlgorithm.calculateMinCut(Object, Object)`
`Set<E>` `getCutEdges()`
Returns the set of edges which run from S to T, in the s-t cut obtained after the last invocation of `MinimumSTCutAlgorithm.calculateMinCut(Object, Object)` In case of a directed graph, only the edges with their tail in S and their head in T are returned.
`V` `getFlowDirection(E e)`
Unsupported operation
`Map<E,Double>` `getFlowMap()`
Unsupported operation
`SimpleWeightedGraph<V,DefaultWeightedEdge>` `getGomoryHuTree()`
Returns the Gomory-Hu Tree as an actual tree (graph).
`MaximumFlowAlgorithm.MaximumFlow<E>` ```getMaximumFlow(V source, V sink)```
Unsupported operation
`double` `getMaximumFlowValue()`
Returns rhw maximum flow value, that was calculated during the last `calculateMaximumFlow(Object, Object)` call.
`Set<V>` `getSinkPartition()`
Returns the sink partition T, t ∈ T, of the cut obtained after the last invocation of `MinimumSTCutAlgorithm.calculateMinCut(Object, Object)`
`Set<V>` `getSourcePartition()`
Returns the source partition S, s ∈ S, of the cut obtained after the last invocation of `MinimumSTCutAlgorithm.calculateMinCut(Object, Object)`
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Methods inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm

`buildMaximumFlow`
• ### 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
• ### Method Detail

• #### getGomoryHuTree

`public SimpleWeightedGraph<V,DefaultWeightedEdge> getGomoryHuTree()`
Returns the Gomory-Hu Tree as an actual tree (graph). Note that this tree is not necessarily unique. The edge weights represent the flow values/cut weights. This method runs in O(n) time.
Returns:
Gomory-Hu Tree
• #### getMaximumFlow

```public MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(V source,
V sink)```
Unsupported operation
Specified by:
`getMaximumFlow` in interface `MaximumFlowAlgorithm<V,E>`
Parameters:
`source` - source of the flow inside the network
`sink` - sink of the flow inside the network
Returns:
nothing
• #### calculateMaximumFlow

```public double calculateMaximumFlow(V source,
V sink)```
Returns the Maximum flow between source and sink. The algorithm is only executed once; successive invocations of this method will return in O(1) time.
Specified by:
`calculateMaximumFlow` in interface `MaximumFlowAlgorithm<V,E>`
Parameters:
`source` - source vertex
`sink` - sink vertex
Returns:
the Maximum flow between source and sink.
• #### getMaximumFlowValue

`public double getMaximumFlowValue()`
Returns rhw maximum flow value, that was calculated during the last `calculateMaximumFlow(Object, Object)` call.
Specified by:
`getMaximumFlowValue` in interface `MaximumFlowAlgorithm<V,E>`
Returns:
maximum flow value
• #### getFlowMap

`public Map<E,Double> getFlowMap()`
Unsupported operation
Specified by:
`getFlowMap` in interface `MaximumFlowAlgorithm<V,E>`
Returns:
nothing
• #### getFlowDirection

`public V getFlowDirection(E e)`
Unsupported operation
Specified by:
`getFlowDirection` in interface `MaximumFlowAlgorithm<V,E>`
Parameters:
`e` - edge
Returns:
nothing
• #### calculateMinCut

```public double calculateMinCut(V source,
V sink)```
Description copied from interface: `MinimumSTCutAlgorithm`
Computes a minimum capacity s-t cut.
Specified by:
`calculateMinCut` in interface `MinimumSTCutAlgorithm<V,E>`
Parameters:
`source` - s
`sink` - t
Returns:
capacity of the cut
• #### calculateMinCut

`public double calculateMinCut()`
Calculates the minimum cut in the graph, that is, the minimum cut over all s-t pairs. The same result can be obtained with the `StoerWagnerMinimumCut` implementation. After invoking this method, the source/sink partitions corresponding to the minimum cut can be queried through the `getSourcePartition()` and `getSinkPartition()` methods. After computing the Gomory-Hu Cut tree, this method runs in O(N) time.
Returns:
weight of the minimum cut in the graph
• #### getCutCapacity

`public double getCutCapacity()`
Description copied from interface: `MinimumSTCutAlgorithm`
Returns the capacity of the cut obtained after the last invocation of `MinimumSTCutAlgorithm.calculateMinCut(Object, Object)`
Specified by:
`getCutCapacity` in interface `MinimumSTCutAlgorithm<V,E>`
Returns:
capacity of the cut
• #### getSourcePartition

`public Set<V> getSourcePartition()`
Description copied from interface: `MinimumSTCutAlgorithm`
Returns the source partition S, s ∈ S, of the cut obtained after the last invocation of `MinimumSTCutAlgorithm.calculateMinCut(Object, Object)`
Specified by:
`getSourcePartition` in interface `MinimumSTCutAlgorithm<V,E>`
Returns:
source partition S
• #### getSinkPartition

`public Set<V> getSinkPartition()`
Description copied from interface: `MinimumSTCutAlgorithm`
Returns the sink partition T, t ∈ T, of the cut obtained after the last invocation of `MinimumSTCutAlgorithm.calculateMinCut(Object, Object)`
Specified by:
`getSinkPartition` in interface `MinimumSTCutAlgorithm<V,E>`
Returns:
source partition T
• #### getCutEdges

`public Set<E> getCutEdges()`
Description copied from interface: `MinimumSTCutAlgorithm`
Returns the set of edges which run from S to T, in the s-t cut obtained after the last invocation of `MinimumSTCutAlgorithm.calculateMinCut(Object, Object)` In case of a directed graph, only the edges with their tail in S and their head in T are returned. In cased of a undirected graph, all edges with one endpoint in S and one endpoint in T are returned.
Specified by:
`getCutEdges` in interface `MinimumSTCutAlgorithm<V,E>`
Returns:
set of edges which run from S to T