Table of Contents

1  ALGO1 : Introduction à l'algorithmique
2  Cours Magistral 8
2.1  Algorithme de Ford-Fulkerson
2.1.1  Etape de base : augmente un chemin
2.1.2  Etape de base : ajoute un arc retour
2.1.3  Calcul du flot maximum
2.1.4  Exemple
2.2  Conclusion

ALGO1 : Introduction à l'algorithmique

Cours Magistral 8

  • Ce cours traite du problème du flot maximal.

Algorithme de Ford-Fulkerson

Etape de base : augmente un chemin

In [14]:
def augment(graph, capacity, flow, val, u, target, visit):
    """ Find an augmenting path from u to target with value at most val."""
    visit[u] = True
    if u == target:
        return val
    for v in graph[u]:
        cuv = capacity[u][v]
        if not visit[v] and cuv > flow[u][v]:  # reachable arc
            res = min(val, cuv - flow[u][v])
            delta = augment(graph, capacity, flow, res, v, target, visit)
            if delta > 0:
                flow[u][v] += delta            # augment flow
                flow[v][u] -= delta
                return delta
    return 0

Etape de base : ajoute un arc retour

In [15]:
def add_reverse_arcs(graph, capac=None):
    """ Utility function for flow algorithms that need for every arc (u,v),
    the existence of an (v,u) arc, by default with zero capacity.
    graph can be in adjacency list, possibly with capacity matrix capac.
    or graph can be in adjacency dictionary, then capac parameter is ignored.

    :param capac: arc capacity matrix
    :param graph: in listlist representation, or in listdict representation,
    in this case capac is ignored
    :complexity: linear
    :returns: nothing, but graph is modified
    """
    for u, _ in enumerate(graph):
        for v in graph[u]:
            if u not in graph[v]:
                if type(graph[v]) is list:
                    graph[v].append(u)
                    if capac:
                        capac[v][u] = 0
                else:
                    assert type(graph[v]) is dict
                    graph[v][u] = 0

Calcul du flot maximum

In [16]:
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')
    while augment(graph, capacity, flow, INF, s, t, [False] * n) > 0:
        pass                         # work already done in _augment
    return (flow, sum(flow[s]))      # flow network, amount of flow

Exemple

Un exemple de graphe, comme celui utilisé dans la page Wikipédia :

In [17]:
A, B, C, D = 0, 1, 2, 3
graph = [
    [B, C], # A
    [C, D], # B
    [D], # C
    [], # D
]
capacity = [
    [0, 1000, 1000, 0], # A
    [0, 0, 1, 1000], # B
    [0, 0, 0, 1000], # C
    [0, 0, 0, 0], # D
]
In [18]:
ford_fulkerson(graph, capacity, A, D)
Out[18]:
([[0, 1000, 1000, 0],
  [-1000, 0, 0, 1000],
  [-1000, 0, 0, 1000],
  [0, -1000, -1000, 0]],
 2000)

On voit que le résultat est le même que celui donné dans l'exemple sur Wikipédia :

Conclusion

C'est bon pour aujourd'hui !