Source code for tryalgo.ford_fulkerson

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Maximum flow by Ford-Fulkerson

jill-jenn vie et christoph durr - 2014-2018
"""


from tryalgo.graph import add_reverse_arcs


# snip{
# pylint: disable=too-many-arguments
def _augment(graph, capacity, flow, val, u, target, visit, timestamp):
    """Find an augmenting path from u to target with value at most val"""
    visit[u] = timestamp
    if u == target:
        return val
    for v in graph[u]:
        cuv = capacity[u][v]
        if visit[v] < timestamp and cuv > flow[u][v]:  # reachable arc
            res = min(val, cuv - flow[u][v])
            delta = _augment(graph, capacity, flow, res, v, target, visit, timestamp)
            if delta > 0:
                flow[u][v] += delta            # augment flow
                flow[v][u] -= delta
                return delta
    return 0


[docs] def ford_fulkerson(graph, capacity, s, t): """Maximum flow by Ford-Fulkerson :param graph: directed graph in listlist or listdict format :param capacity: in matrix format or same listdict graph :param int s: source vertex :param int t: target vertex :returns: flow matrix, flow value :complexity: `O(|V|*|E|*max_capacity)` """ add_reverse_arcs(graph, capacity) n = len(graph) flow = [[0] * n for _ in range(n)] INF = float('inf') visit = [-1] * n timestamp = 0 while _augment(graph, capacity, flow, INF, s, t, visit, timestamp) > 0: timestamp += 1 return (flow, sum(flow[s])) # flow network, amount of flow
# snip}