Module org.jgrapht.core
Package org.jgrapht.alg

Class StoerWagnerMinimumCut<V,​E>

java.lang.Object
org.jgrapht.alg.StoerWagnerMinimumCut<V,​E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
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, 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 java.util.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

    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

  • Field Details

  • Constructor Details

    • StoerWagnerMinimumCut

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

  • Method Details

    • minimumCutPhase

      protected void minimumCutPhase​(java.util.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 java.util.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​(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
      Parameters:
      s - the first vertex
      t - the second vertex
      Returns:
      the merged vertex and its weight

    • vertexWeight

      public double vertexWeight​(java.util.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