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

Class BoykovKolmogorovMFImpl<V,E>

java.lang.Object
org.jgrapht.alg.flow.MaximumFlowAlgorithmBase<V,E>
org.jgrapht.alg.flow.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 Details

    • DEBUG

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

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

    • INITIAL_TIMESTAMP

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

    • currentTimestamp

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

    • vertexExtensionsFactory

      private final ExtensionFactory<BoykovKolmogorovMFImpl<V,E>.VertexExtension> vertexExtensionsFactory
      Vertex extension factory used during initialization.

    • edgeExtensionsFactory

      private final ExtensionFactory<MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge> edgeExtensionsFactory
      Edge extension factory used during initialization.

    • currentSource

      private BoykovKolmogorovMFImpl<V,E>.VertexExtension currentSource
      The network source of the current algorithm invocation.

    • currentSink

      private BoykovKolmogorovMFImpl<V,E>.VertexExtension currentSink
      The network sink of the current algorithm invocation.

    • activeVertices

      private final Deque<BoykovKolmogorovMFImpl<V,E>.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 List<BoykovKolmogorovMFImpl<V,E>.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 Deque<BoykovKolmogorovMFImpl<V,E>.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 Details

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

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

    • augmentShortPaths

      private void augmentShortPaths(BoykovKolmogorovMFImpl<V,E>.VertexExtension source, BoykovKolmogorovMFImpl<V,E>.VertexExtension sink)
      Augments all source-sink and source-node-sink paths. This improved performance on the computer vision maximum flow networks.
      Parameters:
      source - network source.
      sink - network sink.

    • grow

      private MaximumFlowAlgorithmBase<V,E>.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<V,E>.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<V,E>.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.

    • makeActive

      private void makeActive(BoykovKolmogorovMFImpl<V,E>.VertexExtension vertex)
      Makes the vertex an active vertex.
      Parameters:
      vertex - network vertex.

    • nextActiveVertex

      private BoykovKolmogorovMFImpl<V,E>.VertexExtension nextActiveVertex()
      Returns the next active vertex to be processed.
      Returns:
      the next active vertex to be processed.

    • finishVertex

      private void finishVertex(BoykovKolmogorovMFImpl<V,E>.VertexExtension vertex)
      Makes the vertex inactive.
      Parameters:
      vertex - network vertex.

    • makeCheckedInThisIteration

      private void makeCheckedInThisIteration(BoykovKolmogorovMFImpl<V,E>.VertexExtension vertex)
      Sets the timestamp of the vertex equal to the currentTimestamp.
      Parameters:
      vertex - network vertex.

    • wasCheckedInThisIteration

      private boolean wasCheckedInThisIteration(BoykovKolmogorovMFImpl<V,E>.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<V,E>.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.

    • isCloserToTerminal

      private boolean isCloserToTerminal(BoykovKolmogorovMFImpl<V,E>.VertexExtension p, BoykovKolmogorovMFImpl<V,E>.VertexExtension t)
      Checks if the vertex p is closer to terminal than the vertex t using the distance heuristic.
      Parameters:
      p - network vertex.
      t - network vertex.
      Returns:
      true is p is closer to terminal than t, false otherwise.

    • getVertexExtension

      private BoykovKolmogorovMFImpl<V,E>.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.