Class GlobalMincut

  • public class GlobalMincut
    extends Object
    The GlobalMincut class represents a data type for computing a global minimum cut in a graph with non-negative edge weights. A cut is a partition of the vertices into two nonempty subsets. An edge that has one endpoint in each subset of a cut is a crossing edge. The weight of a cut is the sum of the weights of its crossing edges. A global minimum cut whose weight is no larger than the weight of any other cut.

    This is an implementation of Stoer-Wagner's algorithm. The constructor takes O(V (V + E) log V) time, where V is the number of vertices and E is the number of edges. The weight and isCut methods take Θ(1) time. It uses Θ(V) extra space (not including the graph).

    For additional documentation, see

    • M. Stoer and F. Wagner (1997). A simple min-cut algorithm. Journal of the ACM , 44(4):585-591.
    Marcelo Silva
    • Method Detail

      • weight

        public double weight()
        Returns the weight of the minimum cut.
        the weight of the minimum cut
      • cut

        public boolean cut​(int v)
        Returns true if the vertex v is one side of the mincut and false otherwise. An edge v-w crosses the mincut if and only if v and w have opposite parity.
        v - the vertex to check
        true if the vertex v is on the first subset of vertices of the minimum cut; or false if the vertex v is on the second subset.
        IllegalArgumentException - unless vertex v is between 0 <= v < V
      • main

        public static void main​(String[] args)
        Unit tests the GlobalMincut data type.
        args - the command-line arguments