## Class StoerWagnerMinimumCut<V,​E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type

public class StoerWagnerMinimumCut<V,​E>
extends 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 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

All Methods
Modifier and Type Method Description
protected StoerWagnerMinimumCut.VertexAndWeight mergeVertices​(Set<V> s, Set<V> t)
Merges vertex $t$ into vertex $s$, summing the weights as required.
Set<V> minCut()
Return a set of vertices on one side of the cut
double minCutWeight()
Return the weight of the minimum cut
protected void minimumCutPhase​(Set<V> a)
Implements the MinimumCutPhase function of Stoer and Wagner.
double vertexWeight​(Set<V> v)
Compute the sum of the weights entering a vertex
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Field Detail

• #### bestCutWeight

protected double bestCutWeight
• #### bestCut

protected Set<V> bestCut
• ### Constructor Detail

• #### StoerWagnerMinimumCut

public StoerWagnerMinimumCut​(Graph<V,​E> graph)
Will compute the minimum cut in graph.
Parameters:
graph - graph over which to run algorithm
Throws:
IllegalArgumentException - if a negative weight edge is found
IllegalArgumentException - if graph has less than 2 vertices
• ### Method Detail

• #### minimumCutPhase

protected void minimumCutPhase​(Set<V> a)
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

public Set<V> 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​(Set<V> s,
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 vertex
t - the second vertex
Returns:
the merged vertex and its weight
• #### vertexWeight

public double vertexWeight​(Set<V> v)
Compute the sum of the weights entering a vertex
Parameters:
v - the vertex
Returns:
the sum of the weights entering a vertex