 org.jgrapht.alg.flow

## Class 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 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>

• ### 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

All Methods
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. 