|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.jgrapht.alg.MinSourceSinkCut<V,E>
public class MinSourceSinkCut<V,E>
Given a directed, weighted graph G(V,E). This class computes a minimum s-t cut. For this, it relies on the EdmondsKarpMaximumFlow implementation. Note: it is not recommended to use this class to calculate the overall minimum cut in a graph by iteratively invoking this class for all source-sink pairs. This is computationally expensive. Instead, use the StoerWagnerMinimumCut implementation.
Constructor Summary | |
---|---|
MinSourceSinkCut(DirectedGraph<V,E> graph)
|
|
MinSourceSinkCut(DirectedGraph<V,E> graph,
double epsilon)
|
Method Summary | |
---|---|
void |
computeMinCut(V source,
V sink)
Compute a minimum s-t cut |
V |
getCurrentSink()
Returns the sink of the last call |
V |
getCurrentSource()
Returns the source of the last call |
Set<E> |
getCutEdges()
Let S be the set containing the source, and T be the set containing the sink, i.e. |
double |
getCutWeight()
Get the cut weight. |
Set<V> |
getSinkPartition()
Returns the min cut partition containing the sink |
Set<V> |
getSourcePartition()
|
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public MinSourceSinkCut(DirectedGraph<V,E> graph)
public MinSourceSinkCut(DirectedGraph<V,E> graph, double epsilon)
Method Detail |
---|
public void computeMinCut(V source, V sink)
source
- sink
- public Set<V> getSourcePartition()
public Set<V> getSinkPartition()
public double getCutWeight()
public Set<E> getCutEdges()
public V getCurrentSource()
public V getCurrentSink()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |