org.jgrapht.alg

## 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 and Description
`protected class ` `StoerWagnerMinimumCut.VertexAndWeight`
Class for weighted vertices
• ### Field Summary

Fields
Modifier and Type Field and Description
`protected Set<V>` `bestCut`
`protected double` `bestCutWeight`
• ### Constructor Summary

Constructors
Constructor and Description
`StoerWagnerMinimumCut(UndirectedGraph<V,E> graph)`
Will compute the minimum cut in graph.
• ### Method Summary

All Methods
Modifier and Type Method and 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(UndirectedGraph<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

Copyright © 2017. All rights reserved.