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

Author:
Timofey Chudakov

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm

FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>
• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm

MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>

• ### Fields inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase

comparator, cutEdges, DEFAULT_EPSILON, directedGraph, edgeExtensionManager, maxFlow, maxFlowValue, network, sink, sinkPartition, source, sourcePartition, vertexExtensionManager
• ### Constructor Summary

Constructors
Constructor Description
BoykovKolmogorovMFImpl​(Graph<V,​E> network)
Creates a new algorithm instance with the specified network.
BoykovKolmogorovMFImpl​(Graph<V,​E> network, double epsilon)
Construct a new algorithm instance with the specifies network and epsilon.
• ### Method Summary

All Methods
Modifier and Type Method Description
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.
• ### Methods inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase

calculateMinCut, calculateSourcePartition, composeFlow, getCurrentSink, getCurrentSource, getCutCapacity, getCutEdges, getFlowDirection, getFlowMap, getMaximumFlowValue, getSinkPartition, getSourcePartition, init, pushFlowThrough
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Methods inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm

getFlow
• ### Methods inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm

getMaximumFlowValue
• ### 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