module td_2a.edmonds_karp#

Inheritance diagram of ensae_teaching_cs.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