# 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)[source]

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)[source]

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)[source]

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)[source]

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