public class GlobalMincut extends Object
GlobalMincut
class represents a data type for computing a
global minimum cut in an edgeweighted graph where the edge
weights are nonnegative. A cut is a partition of the set
of vertices of a graph 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 is a cut for which the weight is not
larger than the weight of any other cut.
The weight()
method returns the weight of the minimum cut and the
cut(int v)
method determines if a vertex v
is on the first or
on the second subset of vertices of the minimum cut.
This is an implementation of Stoerâ€“Wagner's algorithm using an index
priority queue and the unionfind data type in order to simplify dealing with
contracting edges. Precisely, the index priority queue is an instance of
IndexMaxPQ
which is based on a binary heap. As a consequence, the
constructor takes O(V (V + E ) log
V ) time and O(V) extra space (not including the
graph), where V is the number of vertices and E is the
number of edges. However, this time can be reduced to O(V E
+ V^{2} log V) by using an index priority queue
implemented using Fibonacci heaps.
Afterwards, the weight()
and cut(int v)
methods take constant
time.
For additional documentation, see
Constructor and Description 

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

Modifier and Type  Method and Description 

boolean 
cut(int v)
Returns
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. 
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
or if anny edge weight is negativepublic double weight()
public boolean cut(int v)
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.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
and (G.V()  1)
public static void main(String[] args)
GlobalMincut
data type.args
 the commandline arguments