public class GlobalMincut extends Object
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
Constructor and Description |
---|
GlobalMincut(EdgeWeightedGraph G)
Computes a minimum cut in an edge-weighted 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 edge-weighted 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 v-w
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 command-line arguments