StoerWagnerMinimumCut (JGraphT : a free Java graph library)

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 cut
`double`	`minCutWeight()`	Return the weight of the minimum cut
`protected 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

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- 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