- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
FlowAlgorithm<V,
,E> MaximumFlowAlgorithm<V,
,E> MinimumSTCutAlgorithm<V,
E>
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 ClassesModifier and TypeClassDescriptionprivate class
Network vertex extension used to store auxiliary vertex information.private static enum
Enum specifying vertex tree statusNested 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
FieldsModifier and TypeFieldDescriptionprivate final Deque
<BoykovKolmogorovMFImpl<V, E>.VertexExtension> The queue of active vertices.private final Deque
<BoykovKolmogorovMFImpl<V, E>.VertexExtension> A queue of child orphans.private BoykovKolmogorovMFImpl<V,
E>.VertexExtension The network sink of the current algorithm invocation.private BoykovKolmogorovMFImpl<V,
E>.VertexExtension The network source of the current algorithm invocation.private long
The value of the current iteration timestamp.private static final boolean
Whether to print debug related messages.private final ExtensionFactory
<MaximumFlowAlgorithmBase<V, E>.AnnotatedFlowEdge> Edge extension factory used during initialization.private static final long
The timestamp used for free nodes.private static final long
A timestamp for the first algorithm loop iteration.private final List
<BoykovKolmogorovMFImpl<V, E>.VertexExtension> A list of orphans emerged after an s-t path augmentation.private final ExtensionFactory
<BoykovKolmogorovMFImpl<V, E>.VertexExtension> 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
ConstructorsConstructorDescriptionBoykovKolmogorovMFImpl
(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
Modifier and TypeMethodDescriptionprivate void
adopt()
Adopts all orphans.private void
augment
(MaximumFlowAlgorithmBase<V, E>.AnnotatedFlowEdge boundingEdge) Augments an s-t path specified using theboundingEdge
and computes the set of tree orphans emerged after augmentation.private void
augmentShortPaths
(BoykovKolmogorovMFImpl<V, E>.VertexExtension source, BoykovKolmogorovMFImpl<V, E>.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<V, E>.AnnotatedFlowEdge boundingEdge) Finds augmenting path bottleneck by traversing the path edges.private void
finishVertex
(BoykovKolmogorovMFImpl<V, E>.VertexExtension vertex) Makes thevertex
inactive.getMaximumFlow
(V source, V sink) Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.private BoykovKolmogorovMFImpl<V,
E>.VertexExtension getVertexExtension
(V vertex) Returns a vertex extension which corresponds to the networkvertex
.private MaximumFlowAlgorithmBase<V,
E>.AnnotatedFlowEdge grow()
Performs an algorithm grow phase.private boolean
Checks if thevertex
is connected to a terminal vertex (source or sink).private boolean
isCloserToTerminal
(BoykovKolmogorovMFImpl<V, E>.VertexExtension p, BoykovKolmogorovMFImpl<V, E>.VertexExtension t) Checks if the vertexp
is closer to terminal than the vertext
using the distance heuristic.private void
makeActive
(BoykovKolmogorovMFImpl<V, E>.VertexExtension vertex) Makes thevertex
an active vertex.private void
Sets the timestamp of thevertex
equal to thecurrentTimestamp
.private BoykovKolmogorovMFImpl<V,
E>.VertexExtension Returns the next active vertex to be processed.private void
Initializes a new algorithm iteration.private boolean
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 Details
-
DEBUG
private static final boolean DEBUGWhether to print debug related messages.- See Also:
-
FREE_NODE_TIMESTAMP
private static final long FREE_NODE_TIMESTAMPThe 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_TIMESTAMPA timestamp for the first algorithm loop iteration.- See Also:
-
currentTimestamp
private long currentTimestampThe value of the current iteration timestamp. After each iteration, the current timestamp is incremented. -
vertexExtensionsFactory
Vertex extension factory used during initialization. -
edgeExtensionsFactory
private final ExtensionFactory<MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge> edgeExtensionsFactoryEdge extension factory used during initialization. -
currentSource
The network source of the current algorithm invocation. -
currentSink
The network sink of the current algorithm invocation. -
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
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
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
Creates a new algorithm instance with the specifiednetwork
. The created algorithm uses default epsilon.- Parameters:
network
- flow network.
-
BoykovKolmogorovMFImpl
Construct a new algorithm instance with the specifiesnetwork
andepsilon
.- Parameters:
network
- flow networkepsilon
- tolerance for the comparison of floating point values
-
-
Method Details
-
getMaximumFlow
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
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<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
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
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
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
Makes thevertex
an active vertex.- Parameters:
vertex
- network vertex.
-
nextActiveVertex
Returns the next active vertex to be processed.- Returns:
- the next active vertex to be processed.
-
finishVertex
Makes thevertex
inactive.- Parameters:
vertex
- network vertex.
-
makeCheckedInThisIteration
Sets the timestamp of thevertex
equal to thecurrentTimestamp
.- Parameters:
vertex
- network vertex.
-
wasCheckedInThisIteration
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
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<V, E>.VertexExtension p, BoykovKolmogorovMFImpl<V, E>.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
Returns a vertex extension which corresponds to the networkvertex
.- Parameters:
vertex
- network vertex.- Returns:
- a vertex extension which corresponds to the network
vertex
.
-