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((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.
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 $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(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, waitgetFlowpublic 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)
MinimumSTCutAlgorithmcalculateMinCut 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 Gomory-Hu Cut tree, this method runs
in $O(N)$ time.public double getCutCapacity()
MinimumSTCutAlgorithmMinimumSTCutAlgorithm.calculateMinCut(Object, Object)getCutCapacity in interface MinimumSTCutAlgorithm<V,E>public Set<V> getSourcePartition()
MinimumSTCutAlgorithmMinimumSTCutAlgorithm.calculateMinCut(Object, Object)getSourcePartition in interface MinimumSTCutAlgorithm<V,E>public Set<V> getSinkPartition()
MinimumSTCutAlgorithmMinimumSTCutAlgorithm.calculateMinCut(Object, Object)getSinkPartition in interface MinimumSTCutAlgorithm<V,E>public Set<E> getCutEdges()
MinimumSTCutAlgorithmMinimumSTCutAlgorithm.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.