Package org.jgrapht.alg

Class StoerWagnerMinimumCut<V,E>

java.lang.Object
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

  • Constructor Details

    • StoerWagnerMinimumCut

      public StoerWagnerMinimumCut(WeightedGraph<V,E> graph)
      Will compute the minimum cut in graph.
      Parameters:
      graph - graph over which to run algorithm

  • Method Details

    • 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<V,E>.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