Module org.jgrapht.core
Package org.jgrapht.alg.flow

Class BoykovKolmogorovMFImpl<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 BoykovKolmogorovMFImpl<V,​E>
extends MaximumFlowAlgorithmBase<V,​E>
    This is an implementation of the Boykov-Kolmogorov maximum flow algorithm. This algorithm is a special-purpose approach to solving computer vision related maximum flow problems. The algorithm was initially described in: Y. Boykov and V. Kolmogorov, "An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, Sept. 2004, doi: 10.1109/TPAMI.2004.60.. An extended description is given in: Vladimir Kolmogorov. 2004. Graph based algorithms for scene reconstruction from two or more views. Ph.D. Dissertation. Cornell University, USA. Advisor(s) Ramin Zabih. Order Number: AAI3114475..

    This implementation uses 2 heuristics described in Vladimir Kolmogorov's original PhD thesis:

    • Timestamp heuristic.
    • Distance heuristic;

    The worse-case running time of this algorithm on a network $G = (V, E)$ with a capacity function $c: E \rightArrow R^{+}$ is $\mathcal{O}(E\times f)$, where $f$ is the maximum flow value. The reason for this is that the algorithm doesn't necessarily augments shortest $s-t$ paths in a residual network. That's why the argument about the running time complexity is the same as with the Ford-Fulkerson algorithm.

    This algorithm doesn't have the best performance on all types of networks. It's recommended to check if this algorithm gives substantial performance improvement before using it in a particular application. A good general-purpose alternative which works fast in all scenarios is the PushRelabelMFImpl.

    This algorithm works with both directed and undirected networks. The algorithm doesn't have internal synchronization, thus any concurrent network modification has undefined behaviour.

    • Field Detail

      • DEBUG

        private static final boolean DEBUG
        Whether to print debug related messages.
        See Also:
        Constant Field Values

      • FREE_NODE_TIMESTAMP

        private static final long FREE_NODE_TIMESTAMP
        The timestamp used for free nodes. This value is the smallest among all node timestamps and is assigned only to free vertices.
        See Also:
        Constant Field Values

      • INITIAL_TIMESTAMP

        private static final long INITIAL_TIMESTAMP
        A timestamp for the first algorithm loop iteration.
        See Also:
        Constant Field Values

      • currentTimestamp

        private long currentTimestamp
        The value of the current iteration timestamp. After each iteration, the current timestamp is incremented.

      • activeVertices

        private final java.util.Deque<BoykovKolmogorovMFImpl.VertexExtension> activeVertices
        The queue of active vertices. An active vertex is a network vertex which: (a) belongs to source or sink flow tree. (b) has an outgoing edge with positive capacity, which target is a free vertex. The active vertices are processed according to the FIFO principle.

      • orphans

        private final java.util.List<BoykovKolmogorovMFImpl.VertexExtension> orphans
        A list of orphans emerged after an s-t path augmentation. An orphan is a network node which parent edge in the residual network flow tree became saturated.

      • childOrphans

        private final java.util.Deque<BoykovKolmogorovMFImpl.VertexExtension> childOrphans
        A queue of child orphans. A child orphan is a descendant of an orphan, which didn't get a new parent in corresponding flow free. These child orphans have precedence over regular orphans and are processed according to the FIFO principle.

    • Constructor Detail

      • BoykovKolmogorovMFImpl

        public BoykovKolmogorovMFImpl​(Graph<V,​E> network)
        Creates a new algorithm instance with the specified network. The created algorithm uses default epsilon.
        Parameters:
        network - flow network.

      • BoykovKolmogorovMFImpl

        public BoykovKolmogorovMFImpl​(Graph<V,​E> network,
                              double epsilon)
        Construct a new algorithm instance with the specifies network and epsilon.
        Parameters:
        network - flow network
        epsilon - tolerance for the comparison of floating point values

    • Method Detail

      • getMaximumFlow

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

      • calculateMaximumFlow

        private void calculateMaximumFlow​(V source,
                                  V sink)
        Computes the maximum flow value.

        This is the main algorithm loop. First, an algorithm initialization is performed. The initialization includes augmenting all source-sink and source-node-sink paths. After that, the algorithm finds the rest of the augmenting path by iteratively:

        - growing the source and sink flow trees using active vertices - augmenting s-t paths using bounding edges between source and sink flow trees. - adopting orphan nodes emerged after s-t path augmentation.

        Parameters:
        source - network source
        sink - network sink.

      • grow

        private MaximumFlowAlgorithmBase.AnnotatedFlowEdge grow()
        Performs an algorithm grow phase.

        During the grow phase, the network active vertices are iteratively processed. The goal of this processing is to find an (outgoing for source tree / incoming for sink tree) edge with positive capacity which opposite node is either a free node or belongs to the other tree. In the first case, the tree gets one more node, in the second case, a bounding edge is found and the algorithm can proceed to the augment phase.

        Since processing logic is different for source and sink trees, the code handles there cases separately. This method returns either a bounding edge or null. The null value can be returned only after all of the active vertices are processed and no bounding edge is found. This means that the residual network is disconnected and the algorithm can terminate.

        Returns:
        a bounding edge or null if no bounding edge exists.

      • augment

        private void augment​(MaximumFlowAlgorithmBase.AnnotatedFlowEdge boundingEdge)
        Augments an s-t path specified using the boundingEdge and computes the set of tree orphans emerged after augmentation.

        First, the path flow bottleneck is found. Then the bottleneck flow value is pushed through every path edge. If some path edge gets saturated, the corresponding tree node is added to the orphan set. In the case the saturated edge connects source tree vertices, the edge target becomes an orphan, otherwise if the saturated edge connects sink tree vertices, that the edge source becomes an orphan.

        Parameters:
        boundingEdge - s-t path bounding edge between source and sink trees.

      • findBottleneck

        private double findBottleneck​(MaximumFlowAlgorithmBase.AnnotatedFlowEdge boundingEdge)
        Finds augmenting path bottleneck by traversing the path edges.
        Parameters:
        boundingEdge - s-t path bounding edge.
        Returns:
        the computed bottleneck.

      • adopt

        private void adopt()
        Adopts all orphans.

        Processing every orphan, the goal of this procedure is to either find a parent node within the same tree, or identify that no such parent can be found, make the orphan a free vertex and process all descendants of this node the same way. If multiple parents exist, the closest to terminal is selected using distance and timestamp heuristic.

      • nextIteration

        private void nextIteration()
        Initializes a new algorithm iteration.

      • makeCheckedInThisIteration

        private void makeCheckedInThisIteration​(BoykovKolmogorovMFImpl.VertexExtension vertex)
        Sets the timestamp of the vertex equal to the currentTimestamp.
        Parameters:
        vertex - network vertex.

      • wasCheckedInThisIteration

        private boolean wasCheckedInThisIteration​(BoykovKolmogorovMFImpl.VertexExtension vertex)
        Checks if the distance of the vertex was updated during this iteration.
        Parameters:
        vertex - network vertex.
        Returns:
        true if the distance of the vertex was updated in this iteration, false otherwise.

      • hasConnectionToTerminal

        private boolean hasConnectionToTerminal​(BoykovKolmogorovMFImpl.VertexExtension vertex)
        Checks if the vertex is connected to a terminal vertex (source or sink).
        Parameters:
        vertex - network vertex.
        Returns:
        true if the vertex is connected to a terminal vertex, false otherwise.

      • getVertexExtension

        private BoykovKolmogorovMFImpl.VertexExtension getVertexExtension​(V vertex)
        Returns a vertex extension which corresponds to the network vertex.
        Parameters:
        vertex - network vertex.
        Returns:
        a vertex extension which corresponds to the network vertex.