Package 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

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