org.jgrapht.alg.flow

Class DinicMFImpl<V,E>

java.lang.Object

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

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

Type Parameters:

V - the graph vertex type.

E - the graph edge type.

All Implemented Interfaces:

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

public class DinicMFImpl<V,E>
extends MaximumFlowAlgorithmBase<V,E>

Implementation of <a href = "https://en.wikipedia.org/wiki/Dinic%27s_algorithm">Dinic algorithm</a> with scaling for <a href = "https://en.wikipedia.org/wiki/Maximum_flow_problem"maximum"maximum flow problem</a>. The running time of the algorithm is $O(n^2m)$. Dinic algorithm firstly was mentioned in <i>DINIC, E. A. 1970. Algorithm for Solution of a Problem of Maximum Flow in Networks With Power Estimation. Soviet Math. Dokl. 11, 1277-1280.</> Scheme of the algorithm: 1). Create a level graph. If we can't reach the sink return flow value. 2). Find a blocking flow $f'$ in the level graph. 3). Add $f'$ to the flow $f$. Move to the step $1$.

Author:

Kirill Vishnyakov

Nested Class Summary

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

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

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

FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>

Field Summary

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

comparator, cutEdges, DEFAULT_EPSILON, directedGraph, edgeExtensionManager, maxFlow, maxFlowValue, network, sink, sinkPartition, source, sourcePartition, vertexExtensionManager

Constructor Summary

Constructors

Constructor and Description
DinicMFImpl(Graph<V,E> network) Constructor.
DinicMFImpl(Graph<V,E> network, double epsilon) Constructor.

Method Summary

Modifier and Type	Method and Description
double	dfs(org.jgrapht.alg.flow.DinicMFImpl.VertexExtension v, double flow) Finds a blocking flow in the network.
void	dinic() Runs Dinic algorithm with scaling.
MaximumFlowAlgorithm.MaximumFlow<E>	getMaximumFlow(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, 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

getMaximumFlowValue

Methods inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm

getFlow

Constructor Detail

DinicMFImpl

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

Constructor. Constructs a new network on which we will calculate the maximum flow, using Dinic algorithm.

Parameters:

network - the network on which we calculate the maximum flow.

epsilon - the tolerance for the comparison of floating point values.

DinicMFImpl

public DinicMFImpl(Graph<V,E> network)

Constructor. Constructs a new network on which we will calculate the maximum flow.

Parameters:

network - the network on which we calculate the maximum flow.

Method Detail

getMaximumFlow

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

Description copied from interface: MaximumFlowAlgorithm

Sets current source to source, current sink to sink, then calculates maximum flow from source to sink. Returns an object containing detailed information about the flow.

Parameters:

source - source of the flow inside the network

sink - sink of the flow inside the network

Returns:

maximum flow

dfs

public double dfs(org.jgrapht.alg.flow.DinicMFImpl.VertexExtension v,
                  double flow)

Finds a blocking flow in the network. For each vertex we have a pointer on the first edge which we can use to reach the sink. If we can't reach the sink using current edge, we increment the pointer. So on each iteration we either saturate at least one edge or we increment pointer.

Parameters:

v - current vertex.

flow - we can push through.

Returns:

value of the flow we can push.

dinic

public void dinic()

Runs Dinic algorithm with scaling. Construct a level graph, then find blocking flow and finally increase the flow.