Algorithme de poussage/réétiquetage

L'algorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau. Il a été publié par Goldberg et Tarjan en 1986. L'algorithme général a une complexité en temps en $O(|V|^{2}|E|)$ (ici $V$ est l'ensemble des sommets, et $E$ l'ensemble des arcs du graphe) ; une implémentation plus sophistiquée, utilisant une règle de sélection de sommets par pile a un temps d'exécution en $O(|V|^{3})$; une autre règle, celle qui sélectionne le sommet actif le plus élevé (dans un sens précisé plus loin) permet d'obtenir la complexité $O(|V|^{2}{\sqrt {|E|}})$. Enfin l'implémentation avec une structure de données introduite par Daniel Sleator et Robert E. Tarjan et appelée arbre dynamique, et notamment avec un link/cut tree (en) donne un temps d'exécution majoré par $O(|V||E|\log(|V|^{2}/|E|))$. Tous ces temps sont meilleurs que la majoration en $O(|V||E|^{2})$ qui est celle de l'algorithme d'Edmonds-Karp.

Présentation générale

Sur chaque arc, la valeur du flot et la capacité. La capacité de l'arc opposé est nulle (sauf s'il existe déjà^[pas clair]), la valeur du flot son opposée.

Réseau résiduel. La capacité résiduelle est la différence entre la capacité et le flot.

Dans un réseau, le flot entrant dans un sommet doit être égal à celui qui en sort (à l'exception des deux sommets qui sont la source et le puits). C'est le principe de conservation de flot, aussi appelé loi de Kirchhoff. On ne peut donc pas « accumuler » des valeurs à l'intérieur du réseau. Un préflot est une notion dans laquelle cette condition de conservation est affaiblie, en autorisant les sommets à avoir une valeur de flot entrant plus importante que celle du flot sortant. La différence est appelée l'excédent du sommet. Un sommet à excédent positif est dit actif. L'excédent de flot peut être diminué par transfert sur les arcs du graphe résiduel. Le flot est « poussé » (pushed) à travers le réseau en respectant une valeur appelée hauteur des sommets. Les hauteurs sont une approximation de la distance au puits; le flot n'est poussé que vers des distances au puits plus courtes. Un étiquetage est dit valide s'il respecte la propriété $h(u)\leq h(v)+1$, avec $h(u)$ la hauteur du sommet $u$, et où $v$ est dans l'ensemble des voisins de u dans le graphe résiduel. Autrement dit, un sommet $u$ doit avoir une hauteur inférieure à la hauteur augmentée de 1 de n'importe lequel de ses voisins.

L'action de « pousser » consiste à transférer un peu du flot sur un arc résiduel d'un sommet $u$ vers un voisin $v$ pour lequel $h(u)=h(v)+1$. Une poussée est dite saturante si elle épuise toute la capacité de l'arc résiduel $(u,v)$ qui est alors ôté du graphe résiduel. Dans le cas contraire, la poussée est dite non saturante et vide la totalité de l'excédent du sommet $u$. Si plus aucune poussée n'est possible, on tente d'augmenter la hauteur des sommets par une opération appelée « réétiquetage ».

Définitions

Soit $G=((V,E),c,s,t)$ un réseau où $V$ est l'ensemble des sommets, $E$ est l'ensemble des arcs, $c(u,v)$ est la capacité sur un arc $(u,v)$, $s$ est le sommet source et $t$ est le sommet puits. On note $f(u,v)$ le flot qui passe sur un arc $(u,v)$. Le flot respecte les contraintes suivantes :

• contrainte de capacité : $\ f(u,v)\leq c(u,v)$. Le flot sur un arc est toujours inférieur à sa capacité.
• antisymétrie : $\ f(u,v)=-f(v,u)$. Le flot de $u$ à $v$ est l'opposé du flot de $v$ à $u$.
• conservation du flot : $\ \sum _{w\in V}f(u,w)=0$, sauf pour $u=s$ ou $\ u=t$. Le flot pour un sommet est nul, sauf pour la source qui « produit » le flot et le puits qui le « consomme ».

Un préflot satisfait les deux premières conditions, mais la troisième seulement sous une forme affaiblie durant l'exécution de l'algorithme ; à la fin de la procédure, la règle de conservation du flot est à nouveau respectée.

L'excédent d'une fonction $f$ quelconque sur $V\times V$ est la fonction $\operatorname {ex} _{f}$ ou plus simplement $\operatorname {ex}$ définie sur $V$ par :

$\operatorname {ex} _{f}(u)=\sum _{w\in V}f(u,w)$.

Si $f$ est un flot, l'excédent en tout sommet autre que la source et le puits est nul. Un sommet est actif si son excédent est strictement positif. Pour un préflot $f$, la condition de conservation du flot est remplacée par l'inégalité

$\operatorname {ex} _{f}(u)\geq 0$ pour tout sommet $u\neq s$.

Cela signifie qu'il y a plus de flot (au sens large) qui entre dans un sommet qu'il n'en ressort.

La capacité résiduelle d'un arc, notée $r(u,v)$ est définie par $r(u,v)=c(u,v)-f(u,v)>0$ si $(u,v)$ est un arc, et par $r(u,v)=f(v,u)$ sinon. Un arc résiduel est un arc dont la capacité résiduelle est positive. Le graphe résiduel est le graphe des arcs résiduels.

Une hauteur est une fonction $h$ sur les sommets qui vérifie : $h(s)=n,h(t)=0$ (où $n$ est le nombre de sommets) et

$h(u)\leq h(v)+1$ pour tout arc résiduel $(u,v)$.

Une hauteur est une estimation de la distance d'un sommet au puits dans le graphe résiduel. On dit aussi que cette fonction est un étiquetage admissible.

L'algorithme de poussage/réétiquetage

Poussage

L'opération de poussage peut s'appliquer à un arc $(u,v)$ pourvu que $h(u)=h(v)+1$, et si de plus $\operatorname {ex} (u)>0$ ($u$ est actif) et $r(u,v)>0$. Dans ces conditions, on peut décharger une quantité de flot le long de cet arc $(u,v)$. Cette quantité est le minimum $m$ entre ce qui est disponible en $u$, à savoir l'excédent $\operatorname {ex} (u)$ et ce que l'arc peut absorber, à savoir $r(u,v)=c(u,v)-f(u,v)$. Formellement on obtient :

fonction pousser(u,v)
   m = min(ex(u), r(u,v));
   ex(u) = ex(u) - m;                   diminuer l'excédent du sommet courant de $m$
   ex(v) = ex(v) + m;                   augmenter l'excédent du sommet destination
   f(u,v) = f(u,v) + m;                 augmenter le flot de l'arc $(u,v)$
   f(v,u) = f(v,u) - m;                 diminuer le flot sur l'arc opposé

La fonction ci-dessus met à jour l'excédent en $u$ qui diminue de $m$, l'excédent en $v$ qui augmente de $m$. Le flot à travers l'arc $(u,v)$ augmente de $m$ ; de ce fait, comme par convention $f(v,u)=-f(u,v)$, on fait diminuer de $m$ la valeur $f(v,u)$.

Réétiquetage

Réétiqueter un sommet $u$ consiste à augmenter sa hauteur d'une quantité qui la rend d'une unité plus grande que la plus petite des hauteurs de ses voisins dans le graphe résiduel. Après réétiquetage, $h(u)$ atteint la plus grande valeur pour laquelle la condition d'admissibilité, à savoir $h(u)\leq h(v)+1$ est satisfaite. Pour appliquer un réétiquetage, on demande en plus que le sommet $u$ soit actif. Formellement on obtient :

fonction réétiqueter(u)
   h(u) = 1 + min{h(v) | v voisin de u, r(u,v) > 0};

Poussage/réétiquetage

L’algorithme générique de poussage/réétiquetage commence par une initialisation. Au début, la hauteur de tout sommet autre que la source est nulle, et pour la source $s$, on définit $h(s)=|V|$. Le préflot initial est défini ainsi : il est nul sur tous les arcs sauf ceux sortant de la source, où on pose :$f(s,v)=c(s,v)$ pour tout arc $(s,v)$. L'algorithme a la structure suivante :

algorithme pousser-réétiqueter(G(V,E),s,t) 
   Initialisation();
   tant qu'il existe des sommets actifs 
       pousser ou réétiqueter;

Si l'on exécute les fonctions de poussage e réétiquetage aussi longtemps qu'il y a des sommets actifs, et dans n'importe quel ordre, on obtient, à la fin, un flot qui est maximum. On peut montrer que pour tout ordre d'exécution, le temps d'exécution est en $O(|V|^{2}|E|)$^{[réf. nécessaire]}. Un examen plus approfondi montre que l’algorithme est ralenti par les poussages non saturants.

Algorithme de « réétiquetage vers l'avant »

L'algorithme de « réétiquetage vers l’avant » est une spécialisation de l'algorithme générique de poussage/réétiquetage qui améliore le temps d'exécution en le faisant passer de $O(|V|^{2}|E|)$ à$O(|V|^{3})$^{[réf. nécessaire]}. Pour cela, les opérations de poussage et réétiquetage sont exécutées dans un ordre particulier. La différence principale est que le poussage/ réétiquetage est répétitivement appliqué à un même sommet jusqu'à ce que son excédent ait disparu. Ceci diminue le nombre de poussages non saturants qui constituent le goulot d'étranglement de cet algorithme.

L’algorithme réétiqueter-vers-l’avant gère une liste des sommets du réseau autres que la source et le puits. L’algorithme parcourt la liste depuis son début, choisit un sommet actif $u$ puis le « décharge », c’est-à-dire effectue des opérations de poussage et de réétiquetage jusqu’à ce que le sommet n’ait plus d’excédent. Chaque fois qu’un sommet est réétiqueté, il est replacé en début de liste (d’où le nom « réétiquetage-vers-l’avant ») et l’algorithme commence un nouveau parcours de la liste.

Décharge

La décharge d'un sommet u est décrite dans la fonction que voici :

fonction décharger(u):
    tant que ex(u) > 0:
       pour tout voisin v de u 
          pousser(u, v);
       réétiqueter(u);

Réétiqueter vers l’avant

L'algorithme commence par un poussage de la source vers se voisins, puis décharge les sommets actifs, en prenant soin de mettre en tête les sommets dont la hauteur augmente.

algorithme réétiqueter-vers-l’avant(G(V,E),s,t):
   pour tout voisin v  de s
      pousser(s,v);              ceci sature les arcs $(s,v)$ puisque le flot partant de $s$ n'est pas limité 
   L = Liste(V - {s,t});           créer une liste des sommets
   u = L.tête;
   tant que (u != NIL):
      H = h(u);
      décharger(u);
      si h(u) > H
         placer u en tête de L
      sinon
         u = u.suivant;

On peut montrer que cet algorithme est en $O(|V|^{3})$.

Améliorations

Si l'on choisit toujours un sommet actif $v$ de hauteur maximale, on peut réduire, moyennant une gestion appropriée des sommets, le temps à ${\mathcal {O}}(n^{2}{\sqrt {m}})$. Ici, $n=|V|$ est le nombre de sommets et $m=|E|$ est le nombre d'arcs. Avec des structures de données plus élaborées, réduire le temps à

$O(n\,m\,\log _{2+{\frac {m}{n\log m}}}n)$,

et

${\mathcal {O}}(k\,m\,\log {\bigl (}{\frac {n^{2}}{m}}{\bigr )}\ \log(c_{\max }))$,

où $k=\min\{{\sqrt {m}},{\sqrt[{3}]{n^{2}}}\}$ et $c_{\max }$ et le maximum des capacités des arcs.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Push–relabel maximum flow algorithm » (voir la liste des auteurs).

Bibliographie

• (en) Bernard H. Korte et Jens Vygen, Combinatorial Optimization : Theory and Algorithms, Springer, coll. « Algorithms and Combinatorics » (n^o 21), 2008, 627 p. (ISBN 978-3-540-71844-4), « 8.4 Blocking Flows and Fujishige's Algorithm », p. 174–176. Traduction française: Bernard Korte, Jens Vygen (auteurs), Jean Fonlupt et Alexandre Skoda (traducteurs), Optimisation combinatoire : théorie et algorithmes, Springer-France, coll. « IRIS », 2010 (ISBN 978-2-287-99036-6), « 8.5 Algorithme de Goldberg-Tarjan », p. 182–187.
• (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge, MIT Press and McGraw-Hill, 2001, 2^e éd., 1180 p. (ISBN 978-0-262-53196-2, LCCN 2001031277), chap. 26 (« Chap. 26 Flows »), p. 643–700. Traduction française : Introduction à l'algorithmique, 2^e éd., Dunod 2002, « chapitre 26. Flot Maximum ».
• Andrew V. Goldberg et Robert E. Tarjan, « A new approach to the maximum flow problem », Proceedings of the eighteenth annual ACM symposium on Theory of computing,‎ 1986, p. 136–146 (ISBN 0-89791-193-8, DOI 10.1145/12130.12144).