org.jgrapht.alg
public class StoerWagnerMinimumCut<V,E> extends java.lang.Object
Modifier and Type | Class and Description |
---|---|
protected class |
StoerWagnerMinimumCut.VertexAndWeight
Class for weighted vertices
|
Constructor and Description |
---|
StoerWagnerMinimumCut(WeightedGraph<V,E> graph)
Will compute the minimum cut in graph.
|
Modifier and Type | Method and Description |
---|---|
protected StoerWagnerMinimumCut.VertexAndWeight |
mergeVertices(java.util.Set<V> s,
java.util.Set<V> t)
Merges vertex t into vertex s, summing the weights as required.
|
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
|
protected void |
minimumCutPhase(java.util.Set<V> a)
Implements the MinimumCutPhase function of Stoer and Wagner
|
double |
vertexWeight(java.util.Set<V> v)
Compute the sum of the weights entering a vertex
|
public StoerWagnerMinimumCut(WeightedGraph<V,E> graph)
graph
- graph over which to run algorithmprotected void minimumCutPhase(java.util.Set<V> a)
public double minCutWeight()
public java.util.Set<V> minCut()
protected StoerWagnerMinimumCut.VertexAndWeight mergeVertices(java.util.Set<V> s, java.util.Set<V> t)
public double vertexWeight(java.util.Set<V> v)