V - the graph vertex typeE - the graph edge typepublic class GusfieldEquivalentFlowTree<V,E> extends Object implements MaximumFlowAlgorithm<V,E>
MaximumFlowAlgorithm.
The runtime complexity of this class is O((V-1)Q), where Q is the runtime complexity of the
algorithm used to compute s-t cuts in the graph. By default, this class uses the
PushRelabelMFImpl implementation to calculate minimum s-t cuts. This class has a runtime
complexity of O(V^3), resulting in a O(V^4) runtime complexity for the overal algorithm.
Note: this class performs calculations in a lazy manner. The EFT is not calculated until the
first invocation of calculateMaximumFlow(Object, Object) or
getEquivalentFlowTree(). Moreover, this class only
calculates the value of the maximum flow between a source-destination pair; it does not calculate
the corresponding flow per edge. If you need to know the exact flow through an edge, use one of
the alternative MaximumFlowAlgorithm implementations.
Warning: EFTs do not allow you to calculate minimum cuts for all pairs of vertex! For that,
Gomory-Hu cut trees are required! Use the GusfieldGomoryHuCutTree implementation instead.
This class does not support changes to the underlying graph. The behavior of this class is undefined when the graph is modified after instantiating this class.
MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>| Constructor and Description |
|---|
GusfieldEquivalentFlowTree(Graph<V,E> network)
Constructs a new GusfieldEquivalentFlowTree instance.
|
GusfieldEquivalentFlowTree(Graph<V,E> network,
double epsilon)
Constructs a new GusfieldEquivalentFlowTree instance.
|
GusfieldEquivalentFlowTree(Graph<V,E> network,
MinimumSTCutAlgorithm<V,E> minimumSTCutAlgorithm)
Constructs a new GusfieldEquivalentFlowTree instance.
|
| Modifier and Type | Method and Description |
|---|---|
double |
calculateMaximumFlow(V source,
V sink)
Returns the Maximum flow between source and sink.
|
SimpleWeightedGraph<V,DefaultWeightedEdge> |
getEquivalentFlowTree()
Returns the Equivalent Flow Tree as an actual tree (graph).
|
V |
getFlowDirection(E e)
Unsupported operation
|
Map<E,Double> |
getFlowMap()
Unsupported operation
|
MaximumFlowAlgorithm.MaximumFlow<E> |
getMaximumFlow(V source,
V sink)
Unsupported operation
|
double |
getMaximumFlowValue()
Returns maximum flow value, that was calculated during last
calculateMaximumFlow call.
|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitbuildMaximumFlowpublic GusfieldEquivalentFlowTree(Graph<V,E> network)
network - input graphpublic GusfieldEquivalentFlowTree(Graph<V,E> network, double epsilon)
network - input graphepsilon - precisionpublic SimpleWeightedGraph<V,DefaultWeightedEdge> getEquivalentFlowTree()
public MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(V source, V sink)
getMaximumFlow in interface MaximumFlowAlgorithm<V,E>source - source of the flow inside the networksink - sink of the flow inside the networkpublic double calculateMaximumFlow(V source, V sink)
calculateMaximumFlow in interface MaximumFlowAlgorithm<V,E>source - source vertexsink - sink vertexpublic double getMaximumFlowValue()
getMaximumFlowValue in interface MaximumFlowAlgorithm<V,E>public Map<E,Double> getFlowMap()
getFlowMap in interface MaximumFlowAlgorithm<V,E>public V getFlowDirection(E e)
getFlowDirection in interface MaximumFlowAlgorithm<V,E>e - edgeCopyright © 2017. All rights reserved.