Class 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
    • 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