org.jgrapht.alg

Class StoerWagnerMinimumCut<V,E>

java.lang.Object

org.jgrapht.alg.StoerWagnerMinimumCut<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

public class StoerWagnerMinimumCut<V,E>
extends java.lang.Object

Implements the Stoer and Wagner minimum cut algorithm. Deterministically computes the minimum cut in O(|V||E| + |V|log|V|) time. This implementation uses Java's PriorityQueue and requires O(|V||E|log|E|) time. M. Stoer and F. Wagner, "A Simple Min-Cut Algorithm", Journal of the ACM, volume 44, number 4. pp 585-591, 1997.

Constructor Summary

Constructors

Constructor and Description
StoerWagnerMinimumCut(UndirectedGraph<V,E> graph) Will compute the minimum cut in graph.

Method Summary

Modifier and Type	Method and Description
java.util.Set<V>	minCut() Return a set of vertices on one side of the cut
double	minCutWeight() Return the weight of the minimum cut
double	vertexWeight(java.util.Set<V> v) Compute the sum of the weights entering a vertex

Methods inherited from class java.lang.Object

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

Constructor Detail

StoerWagnerMinimumCut

public StoerWagnerMinimumCut(UndirectedGraph<V,E> graph)

Will compute the minimum cut in graph.

Parameters:

graph - graph over which to run algorithm

Throws:

java.lang.IllegalArgumentException - if a negative weight edge is found

java.lang.IllegalArgumentException - if graph has less than 2 vertices

Method Detail

minCutWeight

public double minCutWeight()

Return the weight of the minimum cut

Returns:

the weight of the minimum cut

minCut

public java.util.Set<V> minCut()

Return a set of vertices on one side of the cut

Returns:

a set of vertices on one side of the cut

vertexWeight

public double vertexWeight(java.util.Set<V> v)

Compute the sum of the weights entering a vertex

Parameters:

v - the vertex

Returns:

the sum of the weights entering a vertex