Maximisez un flot dans un réseau

Un centre de données doit envoyer le plus de données possible vers un bureau distant, à travers un réseau de routeurs dont chaque liaison a un débit maximal. Combien de gigabits par seconde peut-on faire passer au total ? Et si le débit est insuffisant, quelle liaison faut-il améliorer en priorité ?

Ce problème de flot maximal apparaît partout : réseaux informatiques, réseaux d’eau ou d’électricité, logistique, mais aussi, de façon plus surprenante, affectation de tâches ou segmentation d’images. Ce chapitre présente le résultat central du domaine, le théorème de Ford-Fulkerson, et l’algorithme qui va avec.

Le fil rouge : un réseau de transfert de données

Le centre de données est l’entrée $e$ (la source), le bureau est la sortie $s$ (le puits). Entre les deux, quatre routeurs a, b, c, d. Chaque liaison est orientée et a une capacité, en Gb/s :

Liaison	e→a	e→b	a→b	a→c	b→d	c→d	c→s	d→s
Capacité	8	5	4	5	7	3	6	8

Flots et coupes

Un flot compatible

Un réseau de transport est un graphe orienté avec une entrée $e$ , une sortie $s$ et une capacité $c(u) \geq 0$ sur chaque arc $u$ . Un flot attribue à chaque arc une quantité $\varphi(u)$ (lisez « phi de u ») qui y circule. Il est compatible si :

il respecte les capacités : $0 \leq \varphi(u) \leq c(u)$ pour tout arc $u$ ;
il respecte la conservation (loi de Kirchhoff) en tout sommet $x$ autre que $e$ et $s$ : ce qui entre est égal à ce qui sort,

\sum_{u \in \omega^-(x)} \varphi(u) = \sum_{u \in \omega^+(x)} \varphi(u)

où $\omega^-(x)$ désigne les arcs qui arrivent en $x$ et $\omega^+(x)$ ceux qui en partent. Un routeur ne crée ni ne détruit de données.

La valeur du flot, $v(\varphi)$ , est la quantité totale qui sort de $e$ (c’est aussi celle qui arrive en $s$ ). On ajoute souvent un arc fictif de retour $s \to e$ , de capacité infinie, qui ramène la valeur du flot : la conservation vaut alors en tout sommet. Un arc est saturé si $\varphi(u) = c(u)$ .

Les coupes : des goulots d’étranglement

Coupez le réseau en deux : d’un côté un ensemble $A$ de sommets contenant $e$ , de l’autre le reste, contenant $s$ . Toutes les données doivent traverser cette frontière. La coupe associée est l’ensemble $\omega^+(A)$ des arcs qui vont de $A$ vers l’extérieur, et sa capacité $c(A)$ est la somme de leurs capacités.

Quel que soit le flot et quelle que soit la coupe, on a toujours $v(\varphi) \leq c(A)$ : tout ce qui va de $e$ à $s$ doit franchir la coupe, et la coupe ne peut pas laisser passer plus que sa capacité. Donc aucun flot ne dépasse 12 Gb/s dans notre réseau. Peut-on atteindre 12 ? C’est tout l’enjeu.

Toutes les données traversent chaque frontière : le flot ne peut dépasser la plus étroite, ici 12.

Ce théorème est remarquable : il relie un problème de maximisation (faire passer le plus possible) à un problème de minimisation (trouver le goulot le plus étroit). Et il est constructif : l’algorithme qui trouve le flot maximal trouve aussi la coupe minimale.

Pourquoi il faut savoir revenir en arrière

Un flot complet n’est pas forcément maximal

Première idée, gloutonne : tant qu’il existe un chemin de $e$ à $s$ dont aucun arc n’est saturé, on y pousse autant que possible.

Le chemin e → a → b → d → s peut porter 4 (a→b sature) ;
le chemin e → a → c → s peut porter 4 (e→a sature à 8) ;
le chemin e → b → d → s peut porter 3 (b→d sature à 7).

On obtient un flot de valeur 11 : e→a 8, e→b 3, a→b 4, a→c 4, b→d 7, c→s 4, d→s 7, c→d 0. Tout chemin de $e$ à $s$ contient maintenant un arc saturé : e→a est plein, et le seul autre départ, e→b, mène à b→d, plein lui aussi. Un tel flot est dit complet. Et pourtant, la coupe minimale autorise 12.

Les chaînes augmentantes

La solution est de chercher des chaînes (au sens non orienté du chapitre 1) de $e$ à $s$ , qui peuvent emprunter un arc :

dans le sens direct, s’il n’est pas saturé (on peut y ajouter du flot) ;
à contre-sens, s’il porte un flot strictement positif (on peut en retirer).

Une telle chaîne s’appelle une chaîne augmentante. Dans notre flot de valeur 11 : e → b (arc direct, 3 sur 5), puis b ← a (arc a→b parcouru à l’envers, il porte 4), puis a → c (4 sur 5), puis c → s (4 sur 6).

Pousser $\delta$ unités le long de cette chaîne, c’est ajouter $\delta$ sur e→b, a→c et c→s, et retirer $\delta$ sur a→b. Concrètement : une unité qui passait par a→b→d emprunte désormais a→c, ce qui libère une place sur b→d pour une unité venue directement par e→b. La conservation reste vraie en chaque sommet. La quantité $\delta$ est limitée par la plus petite marge :

\delta = \min\big(\underbrace{5 - 3}_{e \to b},\; \underbrace{4}_{a \to b \text{ (arrière)}},\; \underbrace{5 - 4}_{a \to c},\; \underbrace{6 - 4}_{c \to s}\big) = 1

Le nouveau flot vaut $11 + 1 = 12$ . Il égale la capacité de la coupe $\lbrace e, a, b \rbrace$ : il est donc maximal.

Aucun chemin en avant n'est libre, mais la chaîne e → b ← a → c → s l'est : elle déplace une unité de a → b vers a → c et libère de la place sur b → d.

L’algorithme de marquage de Ford-Fulkerson

Le principe

L’algorithme cherche systématiquement une chaîne augmentante par un marquage :

Marquer $e$ .
Depuis un sommet marqué $x$ $x$ :
- marquer $y$ avec « $+x$ » si l’arc $(x, y)$ n’est pas saturé ;
- marquer $y$ avec « $-x$ » si l’arc $(y, x)$ porte un flot positif.
Si $s$ est marqué, on remonte les marques depuis $s$ pour obtenir une chaîne augmentante, on calcule $\delta$ (minimum des capacités résiduelles sur les arcs « $+$ » et des flots sur les arcs « $-$ »), on augmente, et on recommence.
Si l’on ne peut plus marquer $s$ , le flot est maximal, et l’ensemble $A$ des sommets marqués définit une coupe minimale.

Le marquage s'arrête à {e, a, b} : les arcs qui en sortent sont saturés, donc le flot de 12 égale la capacité de la coupe et il est maximal.

Pourquoi l’ensemble marqué donne-t-il une coupe minimale ? Tous les arcs qui sortent de $A$ sont saturés (sinon on aurait marqué leur extrémité), et tous les arcs qui y entrent portent un flot nul (même raison). Le flot qui traverse la frontière est donc exactement $c(A)$ : flot et coupe sont tous deux optimaux, ce qui démontre au passage le théorème.

Terminaison et complexité

Si les capacités sont entières, chaque augmentation ajoute au moins 1, donc l’algorithme termine, et le flot maximal obtenu est entier (une propriété très utile, on va le voir). Mais le nombre d’itérations peut être proportionnel à la valeur du flot, ce qui est lent pour de grandes capacités. La variante d’Edmonds-Karp (complément standard) choisit toujours la chaîne augmentante la plus courte en nombre d’arcs, par un BFS : elle termine en $O(nm^2)$ , quelles que soient les capacités.

from collections import deque

def flot_maximal(capacite, e, s):
    """capacite : dictionnaire (x, y) -> capacité. Algorithme de marquage (Edmonds-Karp)."""
    flot = {arc: 0 for arc in capacite}
    while True:
        marque = {e: None}
        file = deque([e])
        while file and s not in marque:              # marquage en largeur
            x = file.popleft()
            for (u, v), c in capacite.items():
                if u == x and v not in marque and flot[u, v] < c:     # arc direct non saturé
                    marque[v] = (x, +1); file.append(v)
                elif v == x and u not in marque and flot[u, v] > 0:   # arc arrière à flot positif
                    marque[u] = (x, -1); file.append(u)
        if s not in marque:                          # plus de chaîne augmentante
            valeur = sum(f for (u, v), f in flot.items() if u == e)
            return valeur, flot, set(marque)         # set(marque) : côté e de la coupe minimale
        chaine, y = [], s
        while y != e:                                # on remonte les marques
            x, sens = marque[y]
            chaine.append((x, y, sens)); y = x
        delta = min(capacite[x, y] - flot[x, y] if sens > 0 else flot[y, x]
                    for x, y, sens in chaine)
        for x, y, sens in chaine:
            if sens > 0: flot[x, y] += delta
            else:        flot[y, x] -= delta

reseau = {("e", "a"): 8, ("e", "b"): 5, ("a", "b"): 4, ("a", "c"): 5,
          ("b", "d"): 7, ("c", "d"): 3, ("c", "s"): 6, ("d", "s"): 8}
valeur, flot, A = flot_maximal(reseau, "e", "s")
print(valeur, sorted(A))                              # 12 ['a', 'b', 'e']

import networkx as nx

G = nx.DiGraph()
for (u, v), c in reseau.items():
    G.add_edge(u, v, capacity=c)
valeur, flot = nx.maximum_flow(G, "e", "s")
coupe, (cote_e, cote_s) = nx.minimum_cut(G, "e", "s")
print(valeur, coupe, sorted(cote_e))                  # 12 12 ['a', 'b', 'e']

Au-delà des tuyaux : les applications

La force des flots est qu’un grand nombre de problèmes s’y ramènent.

Affectation et couplage (complément) : on veut affecter des stagiaires à des projets, chacun ne pouvant prendre que certains projets. On crée un sommet par stagiaire et par projet, un arc de capacité 1 de l’entrée vers chaque stagiaire, de chaque stagiaire vers ses projets possibles, et de chaque projet vers la sortie. Un flot maximal entier donne le plus grand nombre d’affectations possibles : c’est un couplage maximum dans un graphe biparti.
Robustesse d’un réseau : avec des capacités toutes égales à 1, la coupe minimale donne le nombre minimal de liaisons à couper pour séparer deux machines (et, par le théorème de Menger, le nombre de chemins disjoints qui les relient).
Vision par ordinateur : la segmentation d’une image en « objet » et « fond » peut s’écrire comme une coupe minimale dans un graphe de pixels (méthode des graph cuts).

En résumé

Un flot compatible respecte les capacités ( $0 \leq \varphi \leq c$ ) et la conservation en chaque sommet intermédiaire ; sa valeur est ce qui sort de l’entrée.
Une coupe $\omega^+(A)$ , avec $e \in A$ et $s \notin A$ , borne tout flot : $v(\varphi) \leq c(A)$ .
Ford-Fulkerson : flot maximal = coupe minimale.
Un flot complet (chaque chemin a un arc saturé) n’est pas forcément maximal : il faut des chaînes augmentantes, qui peuvent parcourir des arcs à contre-sens pour annuler du flot.
L’algorithme de marquage cherche ces chaînes ; quand il échoue, les sommets marqués donnent la coupe minimale. Avec des capacités entières, le flot maximal est entier ; Edmonds-Karp garantit $O(nm^2)$ .

Exercices

Exercice · Vérifier un flot

facile

Dans le réseau du fil rouge, on propose le flot suivant : e→a 6, e→b 5, a→b 1, a→c 5, b→d 6, c→d 0, c→s 5, d→s 6. Est-il compatible ? Quelle est sa valeur ? Est-il maximal ?

Voir la solution

Capacités : toutes les valeurs sont entre 0 et la capacité (e→a 6 sur 8, e→b 5 sur 5, a→b 1 sur 4, a→c 5 sur 5, b→d 6 sur 7, c→s 5 sur 6, d→s 6 sur 8).

Conservation : en a, il entre 6 et il sort $1 + 5 = 6$ ; en b, il entre $5 + 1 = 6$ et il sort 6 ; en c, il entre 5 et il sort $0 + 5 = 5$ ; en d, il entre $6 + 0 = 6$ et il sort 6. Le flot est compatible.

Sa valeur est $6 + 5 = 11$ . Il n’est pas maximal, puisque le maximum vaut 12. On le voit par le marquage : e→a n’est pas saturé, donc a est marqué ; a→b non plus, donc b ; b→d non plus (6 sur 7), donc d ; d→s non plus, donc s. La chaîne e, a, b, d, s permet d’ajouter $\delta = \min(2, 3, 1, 2) = 1$ , ce qui donne 12.

En code

Python
R

from collections import deque

capacite = {("e", "a"): 8, ("e", "b"): 5, ("a", "b"): 4, ("a", "c"): 5,
            ("b", "d"): 7, ("c", "d"): 3, ("c", "s"): 6, ("d", "s"): 8}
flot = {("e", "a"): 6, ("e", "b"): 5, ("a", "b"): 1, ("a", "c"): 5,
        ("b", "d"): 6, ("c", "d"): 0, ("c", "s"): 5, ("d", "s"): 6}

print(all(0 <= flot[u] <= capacite[u] for u in capacite))          # True : capacités respectées
for x in "abcd":                                                    # conservation : entrant - sortant
    print(x, sum(f for (u, v), f in flot.items() if v == x) - sum(f for (u, v), f in flot.items() if u == x))
print(sum(f for (u, v), f in flot.items() if u == "e"))             # 11 : valeur du flot

# Marquage : arcs directs non saturés (+) et arcs arrière à flot positif (-)
marque, file = {"e": None}, deque(["e"])
while file:
    x = file.popleft()
    for (u, v), c in capacite.items():
        if u == x and v not in marque and flot[u, v] < c:
            marque[v] = (x, c - flot[u, v]); file.append(v)
        elif v == x and u not in marque and flot[u, v] > 0:
            marque[u] = (x, flot[u, v]); file.append(u)
chaine, marges, y = ["s"], [], "s"
while marque[y]:                                                    # on remonte depuis s
    y, marge = marque[y]
    chaine.append(y); marges.append(marge)
print(chaine[::-1], min(marges))   # ['e', 'a', 'b', 'd', 's'] 1 : on passe à 12

reseau <- data.frame(u = c("e", "e", "a", "a", "b", "c", "c", "d"),
                     v = c("a", "b", "b", "c", "d", "d", "s", "s"),
                     cap = c(8, 5, 4, 5, 7, 3, 6, 8),
                     flot = c(6, 5, 1, 5, 6, 0, 5, 6))

all(reseau$flot >= 0 & reseau$flot <= reseau$cap)             # TRUE : capacités respectées
sapply(c("a", "b", "c", "d"), function(x)                      # conservation : entrant - sortant
  sum(reseau$flot[reseau$v == x]) - sum(reseau$flot[reseau$u == x]))   # 0 0 0 0
sum(reseau$flot[reseau$u == "e"])                              # 11 : valeur du flot

# Marquage : arcs directs non saturés (+) et arcs arrière à flot positif (-)
pere <- c(e = "e"); marge <- c(e = Inf); file <- "e"
while (length(file) > 0) {
  x <- file[1]; file <- file[-1]
  for (k in 1:nrow(reseau)) {
    u <- reseau$u[k]; v <- reseau$v[k]
    if (u == x && is.na(pere[v]) && reseau$flot[k] < reseau$cap[k]) {
      pere[v] <- x; marge[v] <- reseau$cap[k] - reseau$flot[k]; file <- c(file, v)
    } else if (v == x && is.na(pere[u]) && reseau$flot[k] > 0) {
      pere[u] <- x; marge[u] <- reseau$flot[k]; file <- c(file, u)
    }
  }
}
chaine <- "s"; while (chaine[1] != "e") chaine <- c(pere[[chaine[1]]], chaine)
chaine                  # "e" "a" "b" "d" "s"
min(marge[chaine])      # 1 : on passe à 12

Exercice · Quelle liaison améliorer ?

moyen

Le budget permet d’augmenter d’une unité la capacité d’une seule liaison. Laquelle choisir parmi c→s, a→c et b→d ? Justifiez à l’aide des coupes.

Voir la solution

Le flot maximal est limité par la coupe minimale $\lbrace$ a→c, b→d $\rbrace$ de capacité 12.

c→s (6 → 7) : cet arc ne fait pas partie de la coupe minimale, qui reste à 12. Aucun gain.
a→c (5 → 6) : la coupe $\lbrace e, a, b \rbrace$ passe à 13. Mais d’autres coupes valent déjà 13, comme $\lbrace e \rbrace$ (e→a et e→b, $8 + 5$ ). Le nouveau maximum est 13.
b→d (7 → 8) : même raisonnement, la coupe $\lbrace e, a, b \rbrace$ passe à 13, et le maximum devient 13.

Il faut donc améliorer a→c ou b→d. La leçon est générale : pour augmenter le débit, il faut élargir toutes les coupes minimales, et le gain est plafonné par la coupe suivante (ici 13, atteinte par plusieurs coupes). Améliorer un arc hors de la coupe minimale est de l’argent perdu.

En code

Python
R

from itertools import combinations

def coupe_minimale(capacite):
    """Capacité minimale d'une coupe, en essayant tous les ensembles A contenant e mais pas s."""
    routeurs = ["a", "b", "c", "d"]
    meilleure = float("inf")
    for k in range(len(routeurs) + 1):
        for choix in combinations(routeurs, k):
            A = {"e", *choix}
            c = sum(cap for (u, v), cap in capacite.items() if u in A and v not in A)
            meilleure = min(meilleure, c)
    return meilleure

reseau = {("e", "a"): 8, ("e", "b"): 5, ("a", "b"): 4, ("a", "c"): 5,
          ("b", "d"): 7, ("c", "d"): 3, ("c", "s"): 6, ("d", "s"): 8}
print(coupe_minimale(reseau))                  # 12
for arc in [("c", "s"), ("a", "c"), ("b", "d")]:
    ameliore = {**reseau, arc: reseau[arc] + 1}   # une unité de plus sur cette liaison
    print(arc, coupe_minimale(ameliore))
# ('c', 's') 12
# ('a', 'c') 13
# ('b', 'd') 13

reseau <- data.frame(u = c("e", "e", "a", "a", "b", "c", "c", "d"),
                     v = c("a", "b", "b", "c", "d", "d", "s", "s"),
                     cap = c(8, 5, 4, 5, 7, 3, 6, 8))

coupe_minimale <- function(reseau) {
  # tous les ensembles A contenant e mais pas s : chaque routeur est dedans ou dehors
  choix <- expand.grid(a = c(TRUE, FALSE), b = c(TRUE, FALSE), c = c(TRUE, FALSE), d = c(TRUE, FALSE))
  capacites <- apply(choix, 1, function(ch) {
    A <- c("e", names(ch)[ch])
    sum(reseau$cap[reseau$u %in% A & !(reseau$v %in% A)])
  })
  min(capacites)
}

coupe_minimale(reseau)                           # 12
for (arc in c("c-s", "a-c", "b-d")) {
  ameliore <- reseau
  k <- paste(reseau$u, reseau$v, sep = "-") == arc
  ameliore$cap[k] <- ameliore$cap[k] + 1         # une unité de plus sur cette liaison
  cat(arc, coupe_minimale(ameliore), "\n")       # c-s 12 ; a-c 13 ; b-d 13
}

Exercice · Affecter des stagiaires

difficile

Quatre stagiaires (S1 à S4) peuvent être affectés à quatre projets (P1 à P4), chacun ne prenant qu’un stagiaire. S1 peut faire P1 ou P2 ; S2 seulement P1 ; S3 P2 ou P3 ; S4 seulement P2. Modélisez le problème par un flot et trouvez le nombre maximal d’affectations. Exhibez une coupe qui prouve que l’on ne peut pas faire mieux.

Voir la solution

Modèle : une entrée $e$ , une sortie $s$ , un arc $e \to S_i$ de capacité 1 pour chaque stagiaire, un arc $S_i \to P_j$ de capacité 1 pour chaque affectation possible, et un arc $P_j \to s$ de capacité 1 pour chaque projet. Un flot entier affecte chaque stagiaire à au plus un projet, et chaque projet à au plus un stagiaire.

Flot : S2 ne peut faire que P1, S4 que P2. On affecte S2 → P1, S4 → P2, S3 → P3. S1 veut P1 ou P2, tous deux pris. Valeur : 3.

Preuve d’optimalité : S1, S2 et S4 n’ont, à eux trois, que deux projets possibles (P1 et P2). Prenons $A = \lbrace e, S_1, S_2, S_4, P_1, P_2 \rbrace$ . Les arcs qui sortent de $A$ sont $e \to S_3$ , $P_1 \to s$ et $P_2 \to s$ (les arcs des stagiaires de $A$ vont tous vers P1 ou P2, qui sont dans $A$ ). Capacité de la coupe : $1 + 1 + 1 = 3$ . Le flot de valeur 3 est donc maximal : un stagiaire restera sans projet (ou il faudra lui ouvrir un autre projet).

En code

Python
R

possibles = {"S1": ["P1", "P2"], "S2": ["P1"], "S3": ["P2", "P3"], "S4": ["P2"]}
affecte = {}                                   # projet -> stagiaire

def augmenter(stagiaire, vus):
    """Chaîne augmentante : un projet libre, ou un projet dont l'occupant peut changer."""
    for p in possibles[stagiaire]:
        if p not in vus:
            vus.add(p)
            if p not in affecte or augmenter(affecte[p], vus):
                affecte[p] = stagiaire
                return True
    return False

valeur = sum(augmenter(s, set()) for s in possibles)
print(valeur, affecte)   # 3 {'P1': 'S2', 'P2': 'S1', 'P3': 'S3'} (ici S4 reste sans projet)

# Le réseau complet (toutes capacités à 1) et la coupe A = {e, S1, S2, S4, P1, P2}
arcs = ([("e", s) for s in possibles] + [(s, p) for s in possibles for p in possibles[s]]
        + [(p, "s") for p in ["P1", "P2", "P3", "P4"]])
A = {"e", "S1", "S2", "S4", "P1", "P2"}
print([(u, v) for u, v in arcs if u in A and v not in A])
# [('e', 'S3'), ('P1', 's'), ('P2', 's')] : capacité 3, le flot de valeur 3 est maximal

possibles <- list(S1 = c("P1", "P2"), S2 = "P1", S3 = c("P2", "P3"), S4 = "P2")
affecte <- c()                                   # projet -> stagiaire

augmenter <- function(stagiaire, vus) {
  # chaîne augmentante : un projet libre, ou un projet dont l'occupant peut changer
  for (p in possibles[[stagiaire]]) if (!(p %in% vus)) {
    vus <- c(vus, p)
    occupant <- if (p %in% names(affecte)) affecte[[p]] else NA
    if (is.na(occupant) || augmenter(occupant, vus)) {
      affecte[p] <<- stagiaire
      return(TRUE)
    }
  }
  FALSE
}

sum(sapply(names(possibles), augmenter, vus = c()))   # 3
affecte                  # P1 S2, P2 S1, P3 S3 (ici S4 reste sans projet)

# Le réseau complet (toutes capacités à 1) et la coupe A = {e, S1, S2, S4, P1, P2}
arcs <- rbind(cbind("e", names(possibles)),
              cbind(rep(names(possibles), lengths(possibles)), unlist(possibles)),
              cbind(c("P1", "P2", "P3", "P4"), "s"))
A <- c("e", "S1", "S2", "S4", "P1", "P2")
arcs[arcs[, 1] %in% A & !(arcs[, 2] %in% A), ]   # e->S3, P1->s, P2->s : capacité 3