org.jgrapht.alg.flow

Class GusfieldEquivalentFlowTree<V,E>

java.lang.Object

org.jgrapht.alg.flow.GusfieldEquivalentFlowTree<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MaximumFlowAlgorithm<V,E>

public class GusfieldEquivalentFlowTree<V,E>
extends 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 through 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.

Since:

January 2016

Author:

Joris Kinable

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm

MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>

Constructor Summary

Constructors

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.

Method Summary

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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 graph

epsilon - precision

GusfieldEquivalentFlowTree

public GusfieldEquivalentFlowTree(Graph<V,E> network,
                                  MinimumSTCutAlgorithm<V,E> minimumSTCutAlgorithm)

Constructs a new GusfieldEquivalentFlowTree instance.

Parameters:

network - input graph

minimumSTCutAlgorithm - algorithm used to compute the minimum $s-t$ cuts

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 interface MaximumFlowAlgorithm<V,E>

Parameters:

source - source of the flow inside the network

sink - sink of the flow inside the network

Returns:

nothing

calculateMaximumFlow

public double calculateMaximumFlow(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:

calculateMaximumFlow in interface MaximumFlowAlgorithm<V,E>

Parameters:

source - source vertex

sink - sink vertex

Returns:

the Maximum flow between source and sink.

getMaximumFlowValue

public double getMaximumFlowValue()

Returns maximum flow value, that was calculated during last calculateMaximumFlow call.

Specified by:

getMaximumFlowValue in interface MaximumFlowAlgorithm<V,E>

Returns:

maximum flow value

getFlowMap

public Map<E,Double> getFlowMap()

Unsupported operation

Specified by:

getFlowMap in interface MaximumFlowAlgorithm<V,E>

Returns:

nothing

getFlowDirection

public V getFlowDirection(E e)

Unsupported operation

Specified by:

getFlowDirection in interface MaximumFlowAlgorithm<V,E>

Parameters:

e - edge

Returns:

nothing