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