
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Known Implementing Classes:
BoykovKolmogorovMFImpl
,DinicMFImpl
,EdmondsKarpMFImpl
,GusfieldGomoryHuCutTree
,MaximumFlowAlgorithmBase
,PushRelabelMFImpl
public interface MinimumSTCutAlgorithm<V,E>
Given a weighted graph $G(V,E)$ (directed or undirected). This class computes a minimum $st$ cut. A cut is a partitioning of the vertices into two disjoint sets $S, T $such that $s \in S, t \in T$, and that $S \cup T = V$. The capacity of a cut is defined as the sum of the weights of the edges from $S$ to $T$. In case of a directed graph, only the edges with their tail in $S$ and their head in $T$ are counted. In cased of a undirected graph, all edges with one endpoint in $S$ and one endpoint in $T$ are counted. For a given $s$ and $t$, this class computes two partitions $S$ and $T$ such that the capacity of the cut is minimized. When each edge has equal weight, by definition this class minimizes the number of edges from $S$ to $T$. Note: it is not recommended to use this class to calculate the overall minimum cut in a graph by iteratively invoking this class for all sourcesink pairs. This is computationally expensive. Instead, use the StoerWagnerMinimumCut implementation. Author:
 Joris Kinable


Method Summary
All Methods Instance Methods Abstract Methods Modifier and Type Method Description 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 ofcalculateMinCut(Object, Object)
java.util.Set<E>
getCutEdges()
Returns the set of edges which run from $S$ to $T$, in the $st$ cut obtained after the last invocation ofcalculateMinCut(Object, Object)
In case of a directed graph, only the edges with their tail in $S$ and their head in $T$ are returned.java.util.Set<V>
getSinkPartition()
Returns the sink partition $T$, $t \in T$, of the cut obtained after the last invocation ofcalculateMinCut(Object, Object)
java.util.Set<V>
getSourcePartition()
Returns the source partition $S$, $s \in S$, of the cut obtained after the last invocation ofcalculateMinCut(Object, Object)



Method Detail

calculateMinCut
double calculateMinCut(V source, V sink)
Computes a minimum capacity $st$ cut. Parameters:
source
 ssink
 t Returns:
 capacity of the cut

getCutCapacity
double getCutCapacity()
Returns the capacity of the cut obtained after the last invocation ofcalculateMinCut(Object, Object)
 Returns:
 capacity of the cut

getSourcePartition
java.util.Set<V> getSourcePartition()
Returns the source partition $S$, $s \in S$, of the cut obtained after the last invocation ofcalculateMinCut(Object, Object)
 Returns:
 source partition S

getSinkPartition
java.util.Set<V> getSinkPartition()
Returns the sink partition $T$, $t \in T$, of the cut obtained after the last invocation ofcalculateMinCut(Object, Object)
 Returns:
 source partition T

getCutEdges
java.util.Set<E> getCutEdges()
Returns the set of edges which run from $S$ to $T$, in the $st$ cut obtained after the last invocation ofcalculateMinCut(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. Returns:
 set of edges which run from $S$ to $T$

