Package org.jgrapht.alg.interfaces
Interface MinimumSTCutAlgorithm<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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.
-
-
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 ofcalculateMinCut(Object, Object)
java.util.Set<E>
getCutEdges()
Returns the set of edges which run from S to T, in the s-t 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 ∈ T, of the cut obtained after the last invocation ofcalculateMinCut(Object, Object)
java.util.Set<V>
getSourcePartition()
Returns the source partition S, s ∈ 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 s-t 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 ∈ 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 ∈ 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 s-t 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
-
-