edu.princeton.cs.algs4

Class GlobalMincut

java.lang.Object

edu.princeton.cs.algs4.GlobalMincut

public class GlobalMincut
extends java.lang.Object

The GlobalMincut class represents a data type for computing a global minimum cut in an edge-weighted 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 union-find 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² 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

• M. Stoer and F. Wagner (1997). A simple min-cut algorithm. Journal of the ACM , 44(4):585-591.

Constructor Summary

Constructors

Constructor and Description
GlobalMincut(EdgeWeightedGraph G) Computes a minimum cut of an edge-weighted graph.

Method Summary

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(java.lang.String[] args) Unit tests the GlobalMincut data type.
double	weight() Returns the weight of the minimum cut.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GlobalMincut

public GlobalMincut(EdgeWeightedGraph G)

Computes a minimum cut of an edge-weighted graph.

Parameters:

G - the edge-weighted graph

Throws:

java.lang.IllegalArgumentException - if the number of vertices of G is less than 2 or if anny 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 on the first subset of vertices of the minimum cut; or false if the vertex v is on the second subset.

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:

java.lang.IllegalArgumentException - unless vertex v is between 0 and (G.V() - 1)

main

public static void main(java.lang.String[] args)

Unit tests the GlobalMincut data type.

Parameters:

args - the command-line arguments