 org.jgrapht.alg.interfaces

## Interface MinimumSTCutAlgorithm<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Known Implementing Classes:
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 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 \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 • #### 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\$ 