# 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

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 :
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 :

### 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 :
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|)$. 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})$. 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 :

### 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.
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.