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).
Classes#
class |
truncated documentation |
---|---|
This class represents a directed graph using adjacency matrix representation. |
Methods#
method |
truncated documentation |
---|---|
The graph is defined as a list of tuple (n1, n2, capacity). is the capacity of the graph. |
|
Returns True if there is a path from source s to sink t in residual graph. Also fills parent to store the … |
|
Returns the maximum flow from s to t in the given graph. |
Documentation#
Implements the Edmonds-Karp algorithm inspired from Wikipedia (same page).
- class ensae_teaching_cs.td_2a.edmonds_karp.EdmondsKarpGraph(edges)#
Bases :
object
This class represents a directed graph using adjacency matrix representation.
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)
- __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)
- 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
- 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