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