# module td_2a.edmonds_karp#

## Short summary#

module ensae_teaching_cs.td_2a.edmonds_karp

Implements the Edmonds-Karp algorithm inspired from Wikipedia (same page).

source on GitHub

## Classes#

class

truncated documentation

EdmondsKarpGraph

This class represents a directed graph using adjacency matrix representation.

## Methods#

method

truncated documentation

__init__

The graph is defined as a list of tuple (n1, n2, capacity). is the capacity of the graph.

bfs

Returns True if there is a path from source s to sink t in residual graph. Also fills parent to store the …

edmonds_karp

Returns the maximum flow from s to t in the given graph.

## Documentation#

Implements the Edmonds-Karp algorithm inspired from Wikipedia (same page).

source on GitHub

class ensae_teaching_cs.td_2a.edmonds_karp.EdmondsKarpGraph(edges)#

Bases : object

This class represents a directed graph using adjacency matrix representation.

source on GitHub

The graph is defined as a list of tuple (n1, n2, capacity). is the capacity of the graph.

Paramètres:

edges – list of tuple (n1, n2, capacity)

source on GitHub

__init__(edges)#

The graph is defined as a list of tuple (n1, n2, capacity). is the capacity of the graph.

Paramètres:

edges – list of tuple (n1, n2, capacity)

source on GitHub

bfs(graph, s, t, parent)#

Returns True if there is a path from source s to sink t in residual graph. Also fills parent to store the path.

Paramètres:
• graph – graph

• s – node 1

• t – node 2

• parent – stores the path

Renvoie:

boolean

source on GitHub

edmonds_karp(source, sink, fLOG=<function noLOG>, verbose=False, update=None)#

Returns the maximum flow from s to t in the given graph.

Paramètres:
• source – source of the flow

• sink – destination of the flow

• fLOG – logging function

• update – custom update function

Renvoie:

maximum flow

The update function can take into account linked edges. the default version is:

def update_default(graph, u, v, path_flow):
graph[u][v] -= path_flow
graph[v][u] += path_flow

source on GitHub