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.

Author:
Timofey Chudakov

  • 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