timdumol / FordFulkersonMaxFlow / 0.1.0


Ford-Fulkerson (BFS-based aka Edmonds-Karp)

Computes a maximum flow given a weighted directed graph. Uses the scaling variant of Edmonds-Karp for stronger polynomial bounds (c.f. Network Flows by Ahuja, et al.).

Takes as input a list of node IDs, a list of edges, the source ID, and the sink ID. The edges should be input as a dictionary of the form:
{"start": <start ID>, "end":  <end ID>, "capacity": <integer>}

Returns as output a dictionary with keys "flow", an integer denoting the total flow, and "edges", a list of edges in the form:

{"start": <start ID>, "end":  <end ID>, "flow": <integer>}