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)[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
  • 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