org.jgrapht.alg.interfaces

## Interface MinimumSTCutAlgorithm<V,E>

• Type Parameters:
`V` - the graph vertex type
`E` - the graph edge type
All Known Implementing Classes:
EdmondsKarpMFImpl, GusfieldGomoryHuCutTree, MaximumFlowAlgorithmBase, PushRelabelMFImpl

`public interface MinimumSTCutAlgorithm<V,E>`
Given a weighted graph G(V,E) (directed or undirected). This class computes a minimum s-t cut. A cut is a partitioning of the vertices into two disjoint sets S, T such that s ∈ S, t ∈ T, and that S ∪ 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 source-sink pairs. This is computationally expensive. Instead, use the StoerWagnerMinimumCut implementation.
Author:
Joris Kinable
• ### Method Summary

All Methods
Modifier and Type Method and Description
`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 `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 `calculateMinCut(Object, Object)` In case of a directed graph, only the edges with their tail in S and their head in T are returned.
`Set<V>` `getSinkPartition()`
Returns the sink partition T, t ∈ T, of the cut obtained after the last invocation of `calculateMinCut(Object, Object)`
`Set<V>` `getSourcePartition()`
Returns the source partition S, s ∈ S, of the cut obtained after the last invocation of `calculateMinCut(Object, Object)`
• ### Method Detail

• #### calculateMinCut

```double calculateMinCut(V source,
V sink)```
Computes a minimum capacity s-t cut.
Parameters:
`source` - s
`sink` - t
Returns:
capacity of the cut
• #### getSourcePartition

`Set<V> getSourcePartition()`
Returns the source partition S, s ∈ S, of the cut obtained after the last invocation of `calculateMinCut(Object, Object)`
Returns:
source partition S
• #### getSinkPartition

`Set<V> getSinkPartition()`
Returns the sink partition T, t ∈ T, of the cut obtained after the last invocation of `calculateMinCut(Object, Object)`
Returns:
source partition T
• #### getCutEdges

`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 `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.
Returns:
set of edges which run from S to T