Package org.jgrapht.alg
Class StoerWagnerMinimumCut<V,E>
- java.lang.Object
-
- org.jgrapht.alg.StoerWagnerMinimumCut<V,E>
-
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
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
StoerWagnerMinimumCut.VertexAndWeight
Class for weighted vertices
-
Constructor Summary
Constructors Constructor Description StoerWagnerMinimumCut(WeightedGraph<V,E> graph)
Will compute the minimum cut in graph.
-
Method Summary
All Methods Instance Methods Concrete Methods 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 Wagnerdouble
vertexWeight(java.util.Set<V> v)
Compute the sum of the weights entering a vertex
-
-
-
Constructor Detail
-
StoerWagnerMinimumCut
public StoerWagnerMinimumCut(WeightedGraph<V,E> graph)
Will compute the minimum cut in graph.- Parameters:
graph
- graph over which to run algorithm
-
-
Method Detail
-
minimumCutPhase
protected void minimumCutPhase(java.util.Set<V> a)
Implements the MinimumCutPhase function of Stoer and Wagner
-
minCutWeight
public double minCutWeight()
Return the weight of the minimum cut
-
minCut
public java.util.Set<V> minCut()
Return 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
-
vertexWeight
public double vertexWeight(java.util.Set<V> v)
Compute the sum of the weights entering a vertex
-
-