MinimumSTCutAlgorithm (JGraphT : a free Java graph library)

Type Parameters:

V - the graph vertex type

E - 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 $s-t$ 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 source-sink 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 $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 \in T$, of the cut obtained after the last invocation of `calculateMinCut(Object, Object)`
`Set<V>`	`getSourcePartition()`	Returns the source partition $S$, $s \in 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
  - getCutCapacity
```
double getCutCapacity()
```
    Returns the capacity of the cut obtained after the last invocation of calculateMinCut(Object, Object)
    
    Returns:
    
    capacity of the cut
  - getSourcePartition
```
Set<V> getSourcePartition()
```
    Returns the source partition $S$, $s \in 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 \in 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$