org.jgrapht.alg
Class StoerWagnerMinimumCut<V,E>

java.lang.Object
  extended by org.jgrapht.alg.StoerWagnerMinimumCut<V,E>

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
protected  class StoerWagnerMinimumCut.VertexAndWeight
          Class for weighted vertices
 
Field Summary
protected  Set<V> bestCut
           
protected  double bestCutWeight
           
 
Constructor Summary
StoerWagnerMinimumCut(UndirectedGraph<V,E> graph)
          Will compute the minimum cut in graph.
 
Method Summary
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


minCutWeight

public double minCutWeight()
Return the weight of the minimum cut


minCut

public Set<V> minCut()
Return 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


vertexWeight

public double vertexWeight(Set<V> v)
Compute the sum of the weights entering a vertex



Copyright © 2013. All rights reserved.