|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.jgrapht.alg.StoerWagnerMinimumCut<V,E>
public class StoerWagnerMinimumCut<V,E>
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.
Nested Class Summary | |
---|---|
protected class |
StoerWagnerMinimumCut.VertexAndWeight
Class for weighted vertices |
Field Summary | |
---|---|
protected Set<V> |
bestCut
|
protected double |
bestCutWeight
|
Constructor Summary | |
---|---|
StoerWagnerMinimumCut(UndirectedGraph<V,E> graph)
Will compute the minimum cut in graph. |
Method Summary | |
---|---|
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 |
---|
protected double bestCutWeight
protected Set<V> bestCut
Constructor Detail |
---|
public StoerWagnerMinimumCut(UndirectedGraph<V,E> graph)
graph
- graph over which to run algorithm
IllegalArgumentException
- if a negative weight edge is found
IllegalArgumentException
- if graph has less than 2 verticesMethod Detail |
---|
protected void minimumCutPhase(Set<V> a)
public double minCutWeight()
public Set<V> minCut()
protected StoerWagnerMinimumCut.VertexAndWeight mergeVertices(Set<V> s, Set<V> t)
public double vertexWeight(Set<V> v)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |