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

• verbose – more information

• 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