Package org.graph4j.flow

Class DinicMaximumFlow

java.lang.Object

org.graph4j.flow.MaximumFlowBase

org.graph4j.flow.DinicMaximumFlow

All Implemented Interfaces:

MaximumFlowAlgorithm

public class DinicMaximumFlow
extends MaximumFlowBase

/** Implements the Dinic algorithm for finding the maximum flow in a network. The algorithm works by repeatedly finding blocking flows in level graphs and augmenting the flow along these paths. Dinic's algorithm is an efficient maximum flow algorithm with a time complexity of O(n^2 * m) for general graphs and O(m * sqrt(n)) for unit capacity graphs, where n is the number of vertices and m is the number of edges.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.flow.MaximumFlowBase

computed, cutEdges, ekAlg, graph, initialFlow, numVertices, sink, sinkIndex, sinkPart, source, sourceIndex, sourcePart

Constructor Summary

Constructors

Constructor	Description
DinicMaximumFlow(Network graph)
DinicMaximumFlow(Network graph, FlowData flow)

Method Summary

Modifier and Type	Method	Description
void	computeMaximumFlow()

Methods inherited from class org.graph4j.flow.MaximumFlowBase

getFlowValue, getMaximumFlowData, getMaximumFlowValue, getMinimumCutEdges, getSinkPart, getSourcePart, initFlow

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.graph4j.flow.MaximumFlowAlgorithm

getFlowValue

Constructor Details

DinicMaximumFlow

public DinicMaximumFlow(Network graph)

DinicMaximumFlow

public DinicMaximumFlow(Network graph,
 FlowData flow)

Method Details

computeMaximumFlow

public void computeMaximumFlow()

Specified by:

computeMaximumFlow in class MaximumFlowBase