Class GusfieldEquivalentFlowTree<V,E>
- java.lang.Object
-
- org.jgrapht.alg.flow.GusfieldEquivalentFlowTree<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
FlowAlgorithm<V,E>
,MaximumFlowAlgorithm<V,E>
public class GusfieldEquivalentFlowTree<V,E> extends java.lang.Object implements MaximumFlowAlgorithm<V,E>
This class computes an Equivalent Flow Tree (EFT) using the algorithm proposed by Dan Gusfield. EFTs can be used to efficiently calculate the maximum flow for all pairs of vertices. The algorithm is described in: Gusfield, D, Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 19(1), p142-155, 1990
In an undirected graph, there exist $frac{n(n-1)}{2}$ different vertex pairs. This class computes the maximum flow between each of these pairs efficiently by performing exactly $(n-1)$ minimum $s-t$ cut computations. If your application requires fewer than $(n-1)$ flow calculations, consider computing the maximum flows manually throughMaximumFlowAlgorithm
.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
getMaximumFlowValue(Object, Object)
orgetEquivalentFlowTree()
. 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 alternativeMaximumFlowAlgorithm
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.
- Author:
- Joris Kinable
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm
FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm
MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>
-
-
Constructor Summary
Constructors Constructor 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.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description SimpleWeightedGraph<V,DefaultWeightedEdge>
getEquivalentFlowTree()
Returns the Equivalent Flow Tree as an actual tree (graph).V
getFlowDirection(E e)
Unsupported operationjava.util.Map<E,java.lang.Double>
getFlowMap()
Unsupported operationMaximumFlowAlgorithm.MaximumFlow<E>
getMaximumFlow(V source, V sink)
Unsupported operationdouble
getMaximumFlowValue(V source, V sink)
Returns the Maximum flow between source and sink.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm
getFlow
-
-
-
-
Constructor Detail
-
GusfieldEquivalentFlowTree
public GusfieldEquivalentFlowTree(Graph<V,E> network)
Constructs a new GusfieldEquivalentFlowTree instance.- Parameters:
network
- input graph
-
GusfieldEquivalentFlowTree
public GusfieldEquivalentFlowTree(Graph<V,E> network, double epsilon)
Constructs a new GusfieldEquivalentFlowTree instance.- Parameters:
network
- input graphepsilon
- precision
-
-
Method Detail
-
getEquivalentFlowTree
public SimpleWeightedGraph<V,DefaultWeightedEdge> getEquivalentFlowTree()
Returns the Equivalent Flow Tree as an actual tree (graph). Note that this tree is not necessarily unique. The edge weights represent the flow values/cut weights. This method runs in $O(n)$ time- Returns:
- Equivalent Flow Tree
-
getMaximumFlow
public MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(V source, V sink)
Unsupported operation- Specified by:
getMaximumFlow
in interfaceMaximumFlowAlgorithm<V,E>
- Parameters:
source
- source of the flow inside the networksink
- sink of the flow inside the network- Returns:
- nothing
-
getMaximumFlowValue
public double getMaximumFlowValue(V source, V sink)
Returns the Maximum flow between source and sink. The algorithm is only executed once; successive invocations of this method will return in $O(1)$ time.- Specified by:
getMaximumFlowValue
in interfaceMaximumFlowAlgorithm<V,E>
- Parameters:
source
- source vertexsink
- sink vertex- Returns:
- the Maximum flow between source and sink.
-
getFlowMap
public java.util.Map<E,java.lang.Double> getFlowMap()
Unsupported operation- Specified by:
getFlowMap
in interfaceFlowAlgorithm<V,E>
- Returns:
- nothing
-
getFlowDirection
public V getFlowDirection(E e)
Unsupported operation- Specified by:
getFlowDirection
in interfaceFlowAlgorithm<V,E>
- Parameters:
e
- edge- Returns:
- nothing
-
-