Class GusfieldGomoryHuCutTree<V,E>
 java.lang.Object

 org.jgrapht.alg.flow.GusfieldGomoryHuCutTree<V,E>

 Type Parameters:
V
 the graph vertex typeE
 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 GomoryHu tree (GHT) using the algorithm proposed by Dan Gusfield. For a definition of GHTs, refer to: Gomory, R., Hu, T. Multiterminal network flows. Journal of the Socieity for Industrial and Applied mathematics, 9(4), p551570, 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), p142155, 1990
In an undirected graph, there exist $\frac{n(n1)}{2}$ different vertex pairs. This class computes the maximum flow/minimum cut between each of these pairs efficiently by performing exactly $(n1)$ minimum $st$ cut computations. If your application needs fewer than $n1$ flow/cut computations, consider computing the maximum flows/minimum cuts manually throughMaximumFlowAlgorithm
/MinimumSTCutAlgorithm
.The runtime complexity of this class is $O((V1)Q)$, where $Q$ is the runtime complexity of the algorithm used to compute $st$ cuts in the graph. By default, this class uses the
PushRelabelMFImpl
implementation to calculate minimum st 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)
orgetGomoryHuTree()
. Moreover, this class only calculates the value of the maximum flow between a sourcedestination 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 alternativeMaximumFlowAlgorithm
implementations.In contrast to an Equivalent Flow Tree (
GusfieldEquivalentFlowTree
), GomoryHu 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 Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm
FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm
MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>


Constructor Summary
Constructors Constructor 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 Instance Methods Concrete Methods Modifier and Type Method Description double
calculateMinCut()
Calculates the minimum cut in the graph, that is, the minimum cut over all $st$ pairs.double
calculateMinCut(V source, V sink)
Computes a minimum capacity $st$ cut.double
getCutCapacity()
Returns the capacity of the cut obtained after the last invocation ofMinimumSTCutAlgorithm.calculateMinCut(Object, Object)
Set<E>
getCutEdges()
Returns the set of edges which run from $S$ to $T$, in the $st$ cut obtained after the last invocation ofMinimumSTCutAlgorithm.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 operationMap<E,Double>
getFlowMap()
Unsupported operationSimpleWeightedGraph<V,DefaultWeightedEdge>
getGomoryHuTree()
Returns the GomoryHu Tree as an actual tree (graph).MaximumFlowAlgorithm.MaximumFlow<E>
getMaximumFlow(V source, V sink)
Unsupported operationdouble
getMaximumFlowValue(V source, V sink)
Returns the Maximum flow between source and sink.Set<V>
getSinkPartition()
Returns the sink partition $T$, $t \in T$, of the cut obtained after the last invocation ofMinimumSTCutAlgorithm.calculateMinCut(Object, Object)
Set<V>
getSourcePartition()
Returns the source partition $S$, $s \in S$, of the cut obtained after the last invocation ofMinimumSTCutAlgorithm.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.FlowAlgorithm
getFlow




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 graphepsilon
 precision


Method Detail

getGomoryHuTree
public SimpleWeightedGraph<V,DefaultWeightedEdge> getGomoryHuTree()
Returns the GomoryHu 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:
 GomoryHu Tree

getMaximumFlow
public MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(V source, V sink)
Unsupported operation Specified by:
getMaximumFlow
in interfaceMaximumFlowAlgorithm<V,E>
 Parameters:
source
 source of the flow inside the networksink
 sink of the flow inside the network Returns:
 nothing

getMaximumFlowValue
public double getMaximumFlowValue(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:
getMaximumFlowValue
in interfaceMaximumFlowAlgorithm<V,E>
 Parameters:
source
 source vertexsink
 sink vertex Returns:
 the Maximum flow between source and sink.

getFlowMap
public Map<E,Double> getFlowMap()
Unsupported operation Specified by:
getFlowMap
in interfaceFlowAlgorithm<V,E>
 Returns:
 nothing

getFlowDirection
public V getFlowDirection(E e)
Unsupported operation Specified by:
getFlowDirection
in interfaceFlowAlgorithm<V,E>
 Parameters:
e
 edge Returns:
 nothing

calculateMinCut
public double calculateMinCut(V source, V sink)
Description copied from interface:MinimumSTCutAlgorithm
Computes a minimum capacity $st$ cut. Specified by:
calculateMinCut
in interfaceMinimumSTCutAlgorithm<V,E>
 Parameters:
source
 ssink
 t Returns:
 capacity of the cut

calculateMinCut
public double calculateMinCut()
Calculates the minimum cut in the graph, that is, the minimum cut over all $st$ pairs. The same result can be obtained with theStoerWagnerMinimumCut
implementation. After invoking this method, the source/sink partitions corresponding to the minimum cut can be queried through thegetSourcePartition()
andgetSinkPartition()
methods. After computing the GomoryHu 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 ofMinimumSTCutAlgorithm.calculateMinCut(Object, Object)
 Specified by:
getCutCapacity
in interfaceMinimumSTCutAlgorithm<V,E>
 Returns:
 capacity of the cut

getSourcePartition
public Set<V> getSourcePartition()
Description copied from interface:MinimumSTCutAlgorithm
Returns the source partition $S$, $s \in S$, of the cut obtained after the last invocation ofMinimumSTCutAlgorithm.calculateMinCut(Object, Object)
 Specified by:
getSourcePartition
in interfaceMinimumSTCutAlgorithm<V,E>
 Returns:
 source partition S

getSinkPartition
public Set<V> getSinkPartition()
Description copied from interface:MinimumSTCutAlgorithm
Returns the sink partition $T$, $t \in T$, of the cut obtained after the last invocation ofMinimumSTCutAlgorithm.calculateMinCut(Object, Object)
 Specified by:
getSinkPartition
in interfaceMinimumSTCutAlgorithm<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 $st$ cut obtained after the last invocation ofMinimumSTCutAlgorithm.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 interfaceMinimumSTCutAlgorithm<V,E>
 Returns:
 set of edges which run from $S$ to $T$

