public class GlobalMincut extends Object
GlobalMincut
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
Constructor and Description 

GlobalMincut(EdgeWeightedGraph G)
Computes a minimum cut in an edgeweighted graph.

Modifier and Type  Method and Description 

boolean 
cut(int v)
Returns
true if the vertex v is one side of the
mincut and false otherwise. 
static void 
main(String[] args)
Unit tests the
GlobalMincut data type. 
double 
weight()
Returns the weight of the minimum cut.

public GlobalMincut(EdgeWeightedGraph G)
G
 the edgeweighted graphIllegalArgumentException
 if the number of vertices of G
is less than 2
.IllegalArgumentException
 if any edge weight is negativepublic double weight()
public boolean cut(int v)
true
if the vertex v
is one side of the
mincut and false
otherwise. An edge vw
crosses the mincut if and only if v and w have
opposite parity.v
 the vertex to checktrue
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
public static void main(String[] args)
GlobalMincut
data type.args
 the commandline arguments