Package org.jgrapht.alg

Class StoerWagnerMinimumCut<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    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

    • Field Detail

      • bestCutWeight

        protected double bestCutWeight

      • bestCut

        protected Set<V> bestCut

    • Constructor Detail

      • StoerWagnerMinimumCut

        public StoerWagnerMinimumCut​(Graph<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.
        Parameters:
        a - the vertex

      • minCutWeight

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

      • minCut

        public 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​(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
        Parameters:
        s - the first vertex
        t - the second vertex
        Returns:
        the merged vertex and its weight

      • vertexWeight

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