Class EdmondsKarp

Inheritance Relationships

Base Type

Class Documentation

class EdmondsKarp : public NetworKit::Algorithm

The EdmondsKarp class implements the maximum flow algorithm by Edmonds and Karp.

Public Functions

EdmondsKarp(const Graph &graph, node source, node sink)

Constructs an instance of the EdmondsKarp algorithm for the given graph, source and sink

  • graph – The graph.

  • source – The source node.

  • sink – The sink node.

virtual void run() override

Computes the maximum flow, executes the EdmondsKarp algorithm.

edgeweight getMaxFlow() const

Returns the value of the maximum flow from source to sink.


The maximum flow value

std::vector<node> getSourceSet() const

Returns the set of the nodes on the source side of the flow/minimum cut.


The set of nodes that form the (smallest) source side of the flow/minimum cut.

edgeweight getFlow(node u, node v) const

Get the flow value between two nodes u and v.


The running time of this function is linear in the degree of u.

  • u – The first node

  • v – The second node


The flow between node u and v.

inline edgeweight getFlow(edgeid eid) const

Get the flow value of an edge.


eid – The id of the edge


The flow on the edge identified by eid

const std::vector<edgeweight> &getFlowVector() const

Return a copy of the flow values of all edges.


Instead of copying all values you can also use the inline function “getFlow(edgeid)” in order to access the values efficiently.


The flow values of all edges