Module org.jgrapht.core
Package 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

  • Constructor Details

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

    • 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(DinicMFImpl<V,E>.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.