networkit.flow¶

class networkit.flow.Dinic(graph, source, sink)¶

Bases: Algorithm

Computes maximum flow in a directed, weighted graph using Dinic’s blocking-flow algorithm.

Parameters:

• graph (networkit.Graph) – Directed, weighted input graph.

• source (int) – Source node identifier.

• sink (int) – Target node identifier.

getMaxFlow()¶

Returns the computed maximum flow from source to sink.

Returns:

The maximum flow value.

Return type:

float

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

Bases: 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)