V
- the graph vertex typeE
- the graph edge typepublic class StoerWagnerMinimumCut<V,E> extends Object
Modifier and Type | Class and Description |
---|---|
protected class |
StoerWagnerMinimumCut.VertexAndWeight
Class for weighted vertices
|
Modifier and Type | Field and Description |
---|---|
protected Set<V> |
bestCut |
protected double |
bestCutWeight |
Constructor and Description |
---|
StoerWagnerMinimumCut(Graph<V,E> graph)
Will compute the minimum cut in graph.
|
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
|
public StoerWagnerMinimumCut(Graph<V,E> graph)
graph
- graph over which to run algorithmIllegalArgumentException
- if a negative weight edge is foundIllegalArgumentException
- if graph has less than 2 verticesprotected void minimumCutPhase(Set<V> a)
a
- the vertexpublic double minCutWeight()
public Set<V> minCut()
protected StoerWagnerMinimumCut.VertexAndWeight mergeVertices(Set<V> s, Set<V> t)
s
- the first vertext
- the second vertexCopyright © 2018. All rights reserved.