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 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.

Author:

Robby McKilliam, Ernst de Ridder

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	StoerWagnerMinimumCut.VertexAndWeight Class for weighted vertices

Field Summary

Fields

Modifier and Type	Field and Description
protected Set<V>	bestCut
protected double	bestCutWeight

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
protected StoerWagnerMinimumCut.VertexAndWeight	mergeVertices(Set<V> s, Set<V> t) Merges vertex $t$ into vertex $s$, summing the weights as required.
Set<V>	minCut() Return a set of vertices on one side of the cut
double	minCutWeight() Return the weight of the minimum cut
protected void	minimumCutPhase(Set<V> a) Implements the MinimumCutPhase function of Stoer and Wagner.
double	vertexWeight(Set<V> v) Compute the sum of the weights entering a vertex

Methods inherited from class java.lang.Object

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

Field Detail

bestCutWeight

protected double bestCutWeight

bestCut

protected Set<V> bestCut

Constructor Detail

StoerWagnerMinimumCut

public StoerWagnerMinimumCut(Graph<V,E> graph)

Will compute the minimum cut in graph.

Parameters:

graph - graph over which to run algorithm

Throws:

IllegalArgumentException - if a negative weight edge is found

IllegalArgumentException - if graph has less than 2 vertices

Method Detail

minimumCutPhase

protected void minimumCutPhase(Set<V> a)

Implements the MinimumCutPhase function of Stoer and Wagner.

Parameters:

a - the vertex

minCutWeight

public double minCutWeight()

Return the weight of the minimum cut

Returns:

the weight of the minimum cut

minCut

public 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

mergeVertices

protected StoerWagnerMinimumCut.VertexAndWeight mergeVertices(Set<V> s,
                                                              Set<V> t)

Merges vertex $t$ into vertex $s$, summing the weights as required. Returns the merged vertex and the sum of its weights

Parameters:

s - the first vertex

t - the second vertex

Returns:

the merged vertex and its weight

vertexWeight

public double vertexWeight(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