java.lang.Object
org.jgrapht.alg.StoerWagnerMinimumCut<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
public class StoerWagnerMinimumCut<V,E>
extends java.lang.Object
Implements the Stoer and Wagner minimum cut
algorithm. Deterministically computes the minimum cut in $O(|V||E| + |V| \log |V|)$ time.
This implementation uses Java's PriorityQueue and requires $O(|V||E| \log |E|)$ time. M. Stoer
and F. Wagner, "A Simple Min-Cut Algorithm", Journal of the ACM, volume 44, number 4. pp 585-591,
1997.
- Author:
- Robby McKilliam, Ernst de Ridder
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
StoerWagnerMinimumCut.VertexAndWeight
Class for weighted vertices -
Field Summary
Fields Modifier and Type Field Description protected java.util.Set<V>
bestCut
protected double
bestCutWeight
-
Constructor Summary
Constructors Constructor Description StoerWagnerMinimumCut(Graph<V,E> graph)
Will compute the minimum cut in graph. -
Method Summary
Modifier and Type Method Description protected StoerWagnerMinimumCut.VertexAndWeight
mergeVertices(java.util.Set<V> s, java.util.Set<V> t)
Merges vertex $t$ into vertex $s$, summing the weights as required.java.util.Set<V>
minCut()
Return a set of vertices on one side of the cutdouble
minCutWeight()
Return the weight of the minimum cutprotected void
minimumCutPhase(java.util.Set<V> a)
Implements the MinimumCutPhase function of Stoer and Wagner.double
vertexWeight(java.util.Set<V> v)
Compute the sum of the weights entering a vertex
-
Field Details
-
bestCutWeight
protected double bestCutWeight -
bestCut
-
-
Constructor Details
-
StoerWagnerMinimumCut
Will compute the minimum cut in graph.- Parameters:
graph
- graph over which to run algorithm- Throws:
java.lang.IllegalArgumentException
- if a negative weight edge is foundjava.lang.IllegalArgumentException
- if graph has less than 2 vertices
-
-
Method Details
-
minimumCutPhase
Implements the MinimumCutPhase function of Stoer and Wagner.- Parameters:
a
- the vertex
-
minCutWeight
public double minCutWeight()Return the weight of the minimum cut- Returns:
- the weight of the minimum cut
-
minCut
Return a set of vertices on one side of the cut- Returns:
- a set of vertices on one side of the cut
-
mergeVertices
protected StoerWagnerMinimumCut.VertexAndWeight mergeVertices(java.util.Set<V> s, java.util.Set<V> t)Merges vertex $t$ into vertex $s$, summing the weights as required. Returns the merged vertex and the sum of its weights- Parameters:
s
- the first vertext
- the second vertex- Returns:
- the merged vertex and its weight
-
vertexWeight
Compute the sum of the weights entering a vertex- Parameters:
v
- the vertex- Returns:
- the sum of the weights entering a vertex
-