GlobalMincut (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.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.
Author:

Marcelo Silva

Constructor Summary

Constructors
Constructor and Description

GlobalMincut(EdgeWeightedGraph G)
Computes a minimum cut in an edge-weighted graph.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
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.

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - GlobalMincut
```
public GlobalMincut(EdgeWeightedGraph G)
```
    Computes a minimum cut in an edge-weighted graph.
    
    Parameters:
    
    G - the edge-weighted graph
    
    Throws:
    
    IllegalArgumentException - if the number of vertices of G is less than 2.
    
    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)
```
    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.
    
    Parameters:
    
    v - the vertex to check
    
    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.
    
    Throws:
    
    IllegalArgumentException - unless vertex v is between 0 <= v < V
  - main
```
public static void main(String[] args)
```
    Unit tests the GlobalMincut data type.
    
    Parameters:
    
    args - the command-line arguments