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
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,
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$.
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.
source - source of the flow inside the network
sink - sink of the flow inside the network
public double dfs(org.jgrapht.alg.flow.DinicMFImpl.VertexExtension v,
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
v - current vertex.
flow - we can push through.
value of the flow we can push.
public void dinic()
Runs Dinic algorithm with scaling. Construct a level graph, then find blocking flow and
finally increase the flow.