Class EdmondsKarp¶

Inheritance Relationships¶

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

Parameters:

• 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.

Returns:

The maximum flow value

std::vector<node> getSourceSet() const¶

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

Returns:

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.

Warning

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

Parameters:

• u – The first node

• v – The second node

Returns:

The flow between node u and v.

inline edgeweight getFlow(edgeid eid) const¶

Get the flow value of an edge.

Parameters:

eid – The id of the edge

Returns:

The flow on the edge identified by eid

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

Return a copy of the flow values of all edges.

Note

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

Returns:

The flow values of all edges