org.jgrapht.alg.flow

Class EdmondsKarpMFImpl<V,E>

java.lang.Object

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

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MaximumFlowAlgorithm<V,E>, MinimumSTCutAlgorithm<V,E>

public final class EdmondsKarpMFImpl<V,E>
extends MaximumFlowAlgorithmBase<V,E>

A flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge can not exceed the capacity of the edge (note, that all capacities must be non-negative). A flow must satisfy the restriction that the amount of flow into a vertex equals the amount of flow out of it, except when it is a source, which "produces" flow, or sink, which "consumes" flow.

This class computes maximum flow in a network using Edmonds-Karp algorithm. Be careful: for large networks this algorithm may consume significant amount of time (its upper-bound complexity is O(VE^2), where V - amount of vertices, E - amount of edges in the network).

This class can also computes minimum s-t cuts. Effectively, to compute a minimum s-t cut, the implementation first computes a minimum s-t flow, after which a BFS is run on the residual graph.

For more details see Andrew V. Goldberg's Combinatorial Optimization (Lecture Notes). Note: even though the algorithm accepts any kind of graph, currently only Simple directed and undirected graphs are supported (and tested!).

Author:

Ilya Razensteyn

Nested Class Summary

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

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

Field Summary

Fields inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase

cutEdges, DEFAULT_EPSILON, directed_graph, edgeExtensionManager, epsilon, maxFlow, maxFlowValue, network, sink, sinkPartition, source, sourcePartition, vertexExtensionManager

Constructor Summary

Constructors

Constructor and Description
EdmondsKarpMFImpl(Graph<V,E> network) Constructs MaximumFlow instance to work with a copy of network.
EdmondsKarpMFImpl(Graph<V,E> network, double epsilon) Constructs MaximumFlow instance to work with a copy of network.

Method Summary

Modifier and Type	Method and Description
MaximumFlowAlgorithm.MaximumFlow<E>	buildMaximumFlow(V source, V sink) Sets current source to source, current sink to sink, then calculates maximum flow from source to sink.
double	calculateMaximumFlow(V source, V sink) Sets current source to source, current sink to sink, then calculates maximum flow from source to sink.

Methods inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase

calculateMinCut, calculateSourcePartition, compareFlowTo, composeFlow, getCurrentSink, getCurrentSource, getCutCapacity, getCutEdges, getFlowDirection, getFlowMap, getMaximumFlowValue, getSinkPartition, getSourcePartition, init, pushFlowThrough

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.MaximumFlowAlgorithm

getMaximumFlow

Constructor Detail

EdmondsKarpMFImpl

public EdmondsKarpMFImpl(Graph<V,E> network)

Constructs MaximumFlow instance to work with a copy of network. Current source and sink are set to null. If network is weighted, then capacities are weights, otherwise all capacities are equal to one. Doubles are compared using DEFAULT_EPSILON tolerance.

Parameters:

network - network, where maximum flow will be calculated

EdmondsKarpMFImpl

public EdmondsKarpMFImpl(Graph<V,E> network,
                         double epsilon)

Constructs MaximumFlow instance to work with a copy of network. Current source and sink are set to null. If network is weighted, then capacities are weights, otherwise all capacities are equal to one.

Parameters:

network - network, where maximum flow will be calculated

epsilon - tolerance for comparing doubles

Method Detail

buildMaximumFlow

public MaximumFlowAlgorithm.MaximumFlow<E> buildMaximumFlow(V source,
                                                            V sink)

Sets current source to source, current sink to sink, then calculates maximum flow from source to sink. Note, that source and sink must be vertices of the network passed to the constructor, and they must be different.

Parameters:

source - source vertex

sink - sink vertex

Returns:

a maximum flow

calculateMaximumFlow

public double calculateMaximumFlow(V source,
                                   V sink)

Sets current source to source, current sink to sink, then calculates maximum flow from source to sink. Note, that source and sink must be vertices of the network passed to the constructor, and they must be different. If desired, a flow map can be queried afterwards; this will not require a new invocation of the algorithm.

Parameters:

source - source vertex

sink - sink vertex

Returns:

the value of the maximum flow