- java.lang.Object
-
- org.jgrapht.alg.flow.MaximumFlowAlgorithmBase<V,E>
-
- org.jgrapht.alg.flow.BoykovKolmogorovMFImpl<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
BoykovKolmogorovMFImpl.VertexExtension
Network vertex extension used to store auxiliary vertex information.private static class
BoykovKolmogorovMFImpl.VertexTreeStatus
Enum specifying vertex tree status-
Nested classes/interfaces inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase
MaximumFlowAlgorithmBase.AnnotatedFlowEdge, MaximumFlowAlgorithmBase.VertexExtensionBase
-
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>
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.Deque<BoykovKolmogorovMFImpl.VertexExtension>
activeVertices
The queue of active vertices.private java.util.Deque<BoykovKolmogorovMFImpl.VertexExtension>
childOrphans
A queue of child orphans.private BoykovKolmogorovMFImpl.VertexExtension
currentSink
The network sink of the current algorithm invocation.private BoykovKolmogorovMFImpl.VertexExtension
currentSource
The network source of the current algorithm invocation.private long
currentTimestamp
The value of the current iteration timestamp.private static boolean
DEBUG
Whether to print debug related messages.private ExtensionFactory<MaximumFlowAlgorithmBase.AnnotatedFlowEdge>
edgeExtensionsFactory
Edge extension factory used during initialization.private static long
FREE_NODE_TIMESTAMP
The timestamp used for free nodes.private static long
INITIAL_TIMESTAMP
A timestamp for the first algorithm loop iteration.private java.util.List<BoykovKolmogorovMFImpl.VertexExtension>
orphans
A list of orphans emerged after an s-t path augmentation.private ExtensionFactory<BoykovKolmogorovMFImpl.VertexExtension>
vertexExtensionsFactory
Vertex extension factory used during initialization.-
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 specifiednetwork
.BoykovKolmogorovMFImpl(Graph<V,E> network, double epsilon)
Construct a new algorithm instance with the specifiesnetwork
andepsilon
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
adopt()
Adopts all orphans.private void
augment(MaximumFlowAlgorithmBase.AnnotatedFlowEdge boundingEdge)
Augments an s-t path specified using theboundingEdge
and computes the set of tree orphans emerged after augmentation.private void
augmentShortPaths(BoykovKolmogorovMFImpl.VertexExtension source, BoykovKolmogorovMFImpl.VertexExtension sink)
Augments all source-sink and source-node-sink paths.private void
calculateMaximumFlow(V source, V sink)
Computes the maximum flow value.private double
findBottleneck(MaximumFlowAlgorithmBase.AnnotatedFlowEdge boundingEdge)
Finds augmenting path bottleneck by traversing the path edges.private void
finishVertex(BoykovKolmogorovMFImpl.VertexExtension vertex)
Makes thevertex
inactive.MaximumFlowAlgorithm.MaximumFlow<E>
getMaximumFlow(V source, V sink)
Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.private BoykovKolmogorovMFImpl.VertexExtension
getVertexExtension(V vertex)
Returns a vertex extension which corresponds to the networkvertex
.private MaximumFlowAlgorithmBase.AnnotatedFlowEdge
grow()
Performs an algorithm grow phase.private boolean
hasConnectionToTerminal(BoykovKolmogorovMFImpl.VertexExtension vertex)
Checks if thevertex
is connected to a terminal vertex (source or sink).private boolean
isCloserToTerminal(BoykovKolmogorovMFImpl.VertexExtension p, BoykovKolmogorovMFImpl.VertexExtension t)
Checks if the vertexp
is closer to terminal than the vertext
using the distance heuristic.private void
makeActive(BoykovKolmogorovMFImpl.VertexExtension vertex)
Makes thevertex
an active vertex.private void
makeCheckedInThisIteration(BoykovKolmogorovMFImpl.VertexExtension vertex)
Sets the timestamp of thevertex
equal to thecurrentTimestamp
.private BoykovKolmogorovMFImpl.VertexExtension
nextActiveVertex()
Returns the next active vertex to be processed.private void
nextIteration()
Initializes a new algorithm iteration.private boolean
wasCheckedInThisIteration(BoykovKolmogorovMFImpl.VertexExtension vertex)
Checks if the distance of thevertex
was updated during this iteration.-
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
-
-
-
-
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.
-
vertexExtensionsFactory
private final ExtensionFactory<BoykovKolmogorovMFImpl.VertexExtension> vertexExtensionsFactory
Vertex extension factory used during initialization.
-
edgeExtensionsFactory
private final ExtensionFactory<MaximumFlowAlgorithmBase.AnnotatedFlowEdge> edgeExtensionsFactory
Edge extension factory used during initialization.
-
currentSource
private BoykovKolmogorovMFImpl.VertexExtension currentSource
The network source of the current algorithm invocation.
-
currentSink
private BoykovKolmogorovMFImpl.VertexExtension currentSink
The network sink of the current algorithm invocation.
-
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.
-
-
Method Detail
-
getMaximumFlow
public MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(V source, V sink)
Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
. Returns an object containing detailed information about the flow.- Parameters:
source
- source of the flow inside the networksink
- 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 sourcesink
- network sink.
-
augmentShortPaths
private void augmentShortPaths(BoykovKolmogorovMFImpl.VertexExtension source, BoykovKolmogorovMFImpl.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.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
. Thenull
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 theboundingEdge
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.
-
makeActive
private void makeActive(BoykovKolmogorovMFImpl.VertexExtension vertex)
Makes thevertex
an active vertex.- Parameters:
vertex
- network vertex.
-
nextActiveVertex
private BoykovKolmogorovMFImpl.VertexExtension nextActiveVertex()
Returns the next active vertex to be processed.- Returns:
- the next active vertex to be processed.
-
finishVertex
private void finishVertex(BoykovKolmogorovMFImpl.VertexExtension vertex)
Makes thevertex
inactive.- Parameters:
vertex
- network vertex.
-
makeCheckedInThisIteration
private void makeCheckedInThisIteration(BoykovKolmogorovMFImpl.VertexExtension vertex)
Sets the timestamp of thevertex
equal to thecurrentTimestamp
.- Parameters:
vertex
- network vertex.
-
wasCheckedInThisIteration
private boolean wasCheckedInThisIteration(BoykovKolmogorovMFImpl.VertexExtension vertex)
Checks if the distance of thevertex
was updated during this iteration.- Parameters:
vertex
- network vertex.- Returns:
true
if the distance of thevertex
was updated in this iteration,false
otherwise.
-
hasConnectionToTerminal
private boolean hasConnectionToTerminal(BoykovKolmogorovMFImpl.VertexExtension vertex)
Checks if thevertex
is connected to a terminal vertex (source or sink).- Parameters:
vertex
- network vertex.- Returns:
true
if thevertex
is connected to a terminal vertex,false
otherwise.
-
isCloserToTerminal
private boolean isCloserToTerminal(BoykovKolmogorovMFImpl.VertexExtension p, BoykovKolmogorovMFImpl.VertexExtension t)
Checks if the vertexp
is closer to terminal than the vertext
using the distance heuristic.- Parameters:
p
- network vertex.t
- network vertex.- Returns:
true
isp
is closer to terminal thant
,false
otherwise.
-
getVertexExtension
private BoykovKolmogorovMFImpl.VertexExtension getVertexExtension(V vertex)
Returns a vertex extension which corresponds to the networkvertex
.- Parameters:
vertex
- network vertex.- Returns:
- a vertex extension which corresponds to the network
vertex
.
-
-