java.lang.Object
org.jgrapht.alg.flow.MaximumFlowAlgorithmBase<V,E>
org.jgrapht.alg.flow.DinicMFImpl<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>
Implementation of <a href = "https://en.wikipedia.org/wiki/Dinic%27s_algorithm">Dinic
algorithm</a> with scaling for
<a href = "https://en.wikipedia.org/wiki/Maximum_flow_problem"maximum"maximum flow
problem</a>.
The running time of the algorithm is $O(n^2m)$.
Dinic algorithm firstly was mentioned in <i>DINIC, E. A. 1970. Algorithm for Solution
of a Problem of Maximum Flow in Networks With Power Estimation. Soviet Math. Dokl. 11,
1277-1280.</>
Scheme of the algorithm:
1). Create a level graph. If we can't reach the sink return flow value.
2). Find a blocking flow $f'$ in the level graph.
3). Add $f'$ to the flow $f$. Move to the step $1$.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) class
Extension for vertex class.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
FieldsModifier and TypeFieldDescriptionprivate DinicMFImpl<V,
E>.VertexExtension Current sink vertex.private DinicMFImpl<V,
E>.VertexExtension Current source vertex.private final ExtensionFactory
<MaximumFlowAlgorithmBase<V, E>.AnnotatedFlowEdge> private final ExtensionFactory
<DinicMFImpl<V, E>.VertexExtension> 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
ConstructorsConstructorDescriptionDinicMFImpl
(Graph<V, E> network) Constructor.DinicMFImpl
(Graph<V, E> network, double epsilon) Constructor. -
Method Summary
Modifier and TypeMethodDescriptionprivate boolean
bfs()
Creates a level graph.private double
calculateMaxFlow
(V source, V sink) Assigns source to currentSource and sink to currentSink.double
dfs
(DinicMFImpl<V, E>.VertexExtension v, double flow) Finds a blocking flow in the network.void
dinic()
Runs Dinic algorithm with scaling.getMaximumFlow
(V source, V sink) Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.private DinicMFImpl<V,
E>.VertexExtension 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
-
currentSource
Current source vertex. -
currentSink
Current sink vertex. -
vertexExtensionsFactory
-
edgeExtensionsFactory
private final ExtensionFactory<MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge> edgeExtensionsFactory
-
-
Constructor Details
-
DinicMFImpl
Constructor. Constructs a new network on which we will calculate the maximum flow, using Dinic algorithm.- Parameters:
network
- the network on which we calculate the maximum flow.epsilon
- the tolerance for the comparison of floating point values.
-
DinicMFImpl
Constructor. Constructs a new network on which we will calculate the maximum flow.- Parameters:
network
- the network on which we calculate the maximum flow.
-
-
Method Details
-
getMaximumFlow
Description copied from interface:MaximumFlowAlgorithm
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
-
calculateMaxFlow
Assigns source to currentSource and sink to currentSink. Afterwards invokes dinic() method to calculate the maximum flow in the network using Dinic algorithm with scaling.- Parameters:
source
- source vertex.sink
- sink vertex.- Returns:
- the value of the maximum flow in the network.
-
bfs
private boolean bfs()Creates a level graph. We can split all vertices of the graph in disjoint sets. In the same set will lie vertices with equal distance from the source. It's obvious that level network cannot contain edges $i \to j$, where $i$ and $j$ are two vertices for which holds: $|i.level - j.level| > 1$. It follows from a property of the shortest paths. Level graph contains only edges that lead from level $i$ to the level $i + 1$. Thus level graph does not contain backward edges or edges that lead from $i$-th level to $i$-th.- Returns:
- true, if level graph has been constructed(i.e we reached the sink), otherwise false.
-
dfs
Finds a blocking flow in the network. For each vertex we have a pointer on the first edge which we can use to reach the sink. If we can't reach the sink using current edge, we increment the pointer. So on each iteration we either saturate at least one edge or we increment pointer.- Parameters:
v
- current vertex.flow
- we can push through.- Returns:
- value of the flow we can push.
-
dinic
public void dinic()Runs Dinic algorithm with scaling. Construct a level graph, then find blocking flow and finally increase the flow. -
getVertexExtension
-