V
 the graph vertex typeE
 the graph edge typepublic class GusfieldGomoryHuCutTree<V,E> extends Object implements MaximumFlowAlgorithm<V,E>, MinimumSTCutAlgorithm<V,E>
MaximumFlowAlgorithm
/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)
or
getGomoryHuTree()
. 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
alternative MaximumFlowAlgorithm
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.
MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>
FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>
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.

Modifier and Type  Method and 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 of
MinimumSTCutAlgorithm.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 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 GomoryHu Tree as an actual tree (graph).

MaximumFlowAlgorithm.MaximumFlow<E> 
getMaximumFlow(V source,
V sink)
Unsupported operation

double 
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 of
MinimumSTCutAlgorithm.calculateMinCut(Object, Object) 
Set<V> 
getSourcePartition()
Returns the source partition $S$, $s \in S$, of the cut obtained after the last invocation of
MinimumSTCutAlgorithm.calculateMinCut(Object, Object) 
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
getFlow
public GusfieldGomoryHuCutTree(Graph<V,E> network)
network
 input graphpublic GusfieldGomoryHuCutTree(Graph<V,E> network, double epsilon)
network
 input graphepsilon
 precisionpublic SimpleWeightedGraph<V,DefaultWeightedEdge> getGomoryHuTree()
public MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(V source, V sink)
getMaximumFlow
in interface MaximumFlowAlgorithm<V,E>
source
 source of the flow inside the networksink
 sink of the flow inside the networkpublic double getMaximumFlowValue(V source, V sink)
getMaximumFlowValue
in interface MaximumFlowAlgorithm<V,E>
source
 source vertexsink
 sink vertexpublic Map<E,Double> getFlowMap()
getFlowMap
in interface FlowAlgorithm<V,E>
public V getFlowDirection(E e)
getFlowDirection
in interface FlowAlgorithm<V,E>
e
 edgepublic double calculateMinCut(V source, V sink)
MinimumSTCutAlgorithm
calculateMinCut
in interface MinimumSTCutAlgorithm<V,E>
source
 ssink
 tpublic double calculateMinCut()
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 GomoryHu Cut tree, this method runs
in $O(N)$ time.public double getCutCapacity()
MinimumSTCutAlgorithm
MinimumSTCutAlgorithm.calculateMinCut(Object, Object)
getCutCapacity
in interface MinimumSTCutAlgorithm<V,E>
public Set<V> getSourcePartition()
MinimumSTCutAlgorithm
MinimumSTCutAlgorithm.calculateMinCut(Object, Object)
getSourcePartition
in interface MinimumSTCutAlgorithm<V,E>
public Set<V> getSinkPartition()
MinimumSTCutAlgorithm
MinimumSTCutAlgorithm.calculateMinCut(Object, Object)
getSinkPartition
in interface MinimumSTCutAlgorithm<V,E>
public Set<E> getCutEdges()
MinimumSTCutAlgorithm
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.getCutEdges
in interface MinimumSTCutAlgorithm<V,E>
Copyright © 2019. All rights reserved.