networkit.flow

class networkit.flow.EdmondsKarp(graph, source, sink)

Bases: networkit.base.Algorithm

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

Parameters

• graph (networkit.Graph) – The graph

• source (int) – The source node for the flow calculation

• sink (int) – The sink node for the flow calculation

getFlow(u, v=None)

Get the flow value between two nodes u and v or an edge identified by the edge id u. Warning: The variant with two edge ids is linear in the degree of u.

Parameters

• u (int) – The first node incident to the edge or the edge id.

• v (int, optional) – The second node incident to the edge (optional if edge id is specified). Default: None

Returns

The flow on the specified edge.

Return type

float

getFlowVector()

Return a copy of the flow values of all edges.

Returns

The flow values of all edges indexed by edge id.

Return type

list(float)

getMaxFlow()

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

Returns

The maximum flow value

Return type

float

getSourceSet()

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.

Return type

list(int)