Package edu.princeton.cs.algs4
Class GlobalMincut
 Object

 edu.princeton.cs.algs4.GlobalMincut

public class GlobalMincut extends Object
TheGlobalMincut
class represents a data type for computing a global minimum cut in a graph with nonnegative 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 StoerWagner'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 mincut algorithm. Journal of the ACM , 44(4):585591.
 Author:
 Marcelo Silva


Constructor Summary
Constructors Constructor Description GlobalMincut(EdgeWeightedGraph G)
Computes a minimum cut in an edgeweighted graph.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
cut(int v)
Returnstrue
if the vertexv
is one side of the mincut andfalse
otherwise.static void
main(String[] args)
Unit tests theGlobalMincut
data type.double
weight()
Returns the weight of the minimum cut.



Constructor Detail

GlobalMincut
public GlobalMincut(EdgeWeightedGraph G)
Computes a minimum cut in an edgeweighted graph. Parameters:
G
 the edgeweighted graph Throws:
IllegalArgumentException
 if the number of vertices ofG
is less than2
.IllegalArgumentException
 if any edge weight is negative


Method Detail

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

cut
public boolean cut(int v)
Returnstrue
if the vertexv
is one side of the mincut andfalse
otherwise. An edge vw crosses the mincut if and only if v and w have opposite parity. Parameters:
v
 the vertex to check Returns:
true
if the vertexv
is on the first subset of vertices of the minimum cut; orfalse
if the vertexv
is on the second subset. Throws:
IllegalArgumentException
 unless vertexv
is between0 <= v < V

main
public static void main(String[] args)
Unit tests theGlobalMincut
data type. Parameters:
args
 the commandline arguments

