Package org.graph4j.flow

Class EdmondsKarpMaximumFlow

java.lang.Object

org.graph4j.flow.MaximumFlowBase

org.graph4j.flow.EdmondsKarpMaximumFlow

All Implemented Interfaces:

MaximumFlowAlgorithm

public class EdmondsKarpMaximumFlow
extends MaximumFlowBase

The Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a network. The algorithm finds shortest augmenting paths (in terms of the number of edges) using Breadth-First Search (BFS). The time complexity of the algorithm is min(O(nmU),O(n m²), where n is the number of vertices, m is the number of edges and U is an upper bound of edge capacities.

Author:

Cristian Frăsinaru

Field Summary

Fields

Modifier and Type	Field	Description
protected boolean[]	forward
protected int[]	parent
protected VertexQueue	queue
protected double[]	residual
protected boolean[]	visited

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
EdmondsKarpMaximumFlow(Network graph)
EdmondsKarpMaximumFlow(Network graph, FlowData initialFlow)

Method Summary

Modifier and Type	Method	Description
void	computeMaximumFlow()
VertexSet	getSinkPart()
VertexSet	getSourcePart()

Methods inherited from class org.graph4j.flow.MaximumFlowBase

getFlowValue, getMaximumFlowData, getMaximumFlowValue, getMinimumCutEdges, 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

Field Details

visited

protected boolean[] visited

forward

protected boolean[] forward

parent

protected int[] parent

residual

protected double[] residual

queue

protected VertexQueue queue

Constructor Details

EdmondsKarpMaximumFlow

public EdmondsKarpMaximumFlow(Network graph)

EdmondsKarpMaximumFlow

public EdmondsKarpMaximumFlow(Network graph,
 FlowData initialFlow)

Method Details

computeMaximumFlow

public void computeMaximumFlow()

Specified by:

computeMaximumFlow in class MaximumFlowBase

getSourcePart

public VertexSet getSourcePart()

Specified by:

getSourcePart in interface MaximumFlowAlgorithm

Overrides:

getSourcePart in class MaximumFlowBase

Returns:

the partition set of a minimum cut containing the source vertex.

getSinkPart

public VertexSet getSinkPart()

Specified by:

getSinkPart in interface MaximumFlowAlgorithm

Overrides:

getSinkPart in class MaximumFlowBase

Returns:

the partition set of a minimum cut containing the sink vertex.