Algoritmul de debit maxim Push – relabel - Push–relabel maximum flow algorithm

În optimizarea matematică , algoritmul push-relabel (alternativ, algoritmul preflow-push ) este un algoritm pentru calculul fluxurilor maxime într-o rețea de flux . Numele „push-relabel” provine din cele două operații de bază utilizate în algoritm. De-a lungul execuției sale, algoritmul menține o „preflow” și îl convertește treptat într-un flux maxim deplasând fluxul local între nodurile învecinate folosind operații push sub îndrumarea unei rețele admisibile menținute prin operații de reetichetare . În comparație, algoritmul Ford – Fulkerson efectuează augmentări globale care trimit fluxul urmând căi de la sursă până la chiuvetă.

Algoritmul push-relabel este considerat unul dintre cei mai eficienți algoritmi de flux maxim. Algoritmul generic are o complexitate de timp puternic polinomială $O (V 2 E)$ , care este asimptotic mai eficientă decât algoritmul $O (VE 2)$ Edmonds-Karp . Variantele specifice ale algoritmilor realizează complexități de timp și mai mici. Varianta bazată pe cea mai înaltă regulă de selecție a nodului etichetei are $o$ complexitate de timp $O$ $($ $V$ $2$ $\sqrt$ $E$ $)$ și este în general considerată ca etalon pentru algoritmi de flux maxim. Complexitatea timpului $O$ subcubic $($ $VE$ $log ($ $V$ $2$ $/$ $E$ $))$ poate fi realizată folosind arbori dinamici , deși în practică este mai puțin eficientă.

Algoritmul push-relabel a fost extins pentru a calcula fluxurile de costuri minime . Ideea etichetelor la distanță a condus la un algoritm de cale de creștere mai eficient, care la rândul său poate fi încorporat înapoi în algoritmul push-relabel pentru a crea o variantă cu performanțe empirice și mai mari.

Istorie

Conceptul de preflux a fost inițial proiectat de Alexandru V. Karzanov și a fost publicat în 1974 în Soviet Mathematical Dokladi 15. Acest algoritm de pre-flux a folosit, de asemenea, o operație de împingere; cu toate acestea, a folosit distanțe în rețeaua auxiliară pentru a determina unde să împingă fluxul în locul unui sistem de etichetare.

Algoritmul push-relabel a fost proiectat de Andrew V. Goldberg și Robert Tarjan . Algoritmul a fost prezentat inițial în noiembrie 1986 în STOC '86: Proceedings of the XVIII-lea simpozion anual ACM on Theory of computing, și apoi oficial în octombrie 1988 ca articol în Jurnalul ACM. Ambele lucrări detaliază o formă generică a algoritmului care se termină în $O (V 2 E)$ împreună cu o implementare secvențială $O (V 3)$ , o implementare $O (VE log (V 2 / E))$ folosind arbori dinamici și implementare paralelă / distribuită . A explicat în Goldberg-Tarjan a introdus etichete de distanță prin încorporarea lor în algoritmul de flux maxim paralel al lui Yossi Shiloach și Uzi Vishkin .

Concepte

Definiții și notații

Lăsa:

$G = (V, E) să$ fie o rețea cu funcția de capacitate $c : V \times V \to ℝ \infty$ ,
$F = (G, c, s, t)$ o rețea de flux , unde $s \in V$ și $t \in V$ sunt alese sursa si chiuveta noduri respectiv,
$f : V \times V \to ℝ$ denotă un pre-flux în $F$ ,
$x f : V \to ℝ$ denotă funcția în exces față de debitul $f$ , definit de $x f (u) = \sum v \in V f (v, u) - \sum v \in V f (u, v)$ ,
$c f : V \times V \to ℝ \infty$ denotă funcția de capacitate reziduală în raport cu debitul $f$ , definit de $c f (e) = c (e) - f (e)$ ,
$E f \subset E$ fiind marginile unde $f < c$ ,

și

$G f (V, E f)$ indică rețeaua reziduală a lui $G$ față de debitul $f$ .

Algoritmul push-relabel utilizează o funcție de etichetare validă în întregime care nu este negativă , care folosește etichete de distanță sau înălțimi pe noduri pentru a determina ce arce ar trebui selectate pentru operația de împingere. Această funcție de etichetare este notată cu $𝓁: V \to ℕ$ . Această funcție trebuie să îndeplinească următoarele condiții pentru a fi considerată valabilă:

Etichetare valabilă :

𝓁 (u) \leq 𝓁 (v) + 1

pentru toate

(u, v) \in E f

Starea sursei :

𝓁 (s) = | V |

Conservarea chiuvetei :

𝓁 (t) = 0

În algoritm, valorile etichetei lui $s$ și $t$ sunt fixe. $𝓁 (u)$ este o limită inferioară distanței neîncălțat de la $u$ la $t$ în $G f$ dacă $t$ este accesibil de la $u$ . Dacă $u$ a fost deconectat de la $t$ , atunci $𝓁 (u) - | V |$ este o limită inferioară a distanței neponderate de la $u$ la $s$ . Ca rezultat, dacă există o funcție de etichetare validă, nu există căi $s - t$ în $G f$ deoarece astfel de căi nu pot fi mai lungi decât $| V | - 1$ .

Un arc $(u, v) \in E f$ se numește admisibil dacă $𝓁 (u) = 𝓁 (v) + 1$ . Rețeaua admisibilă $G̃ f (V, Ẽ f)$ este compusă din setul de arce $e \in E f$ care sunt admisibile. Rețeaua admisibilă este aciclică.

Operațiuni

Inițializare

Algoritmul începe prin crearea unui grafic rezidual, inițializarea valorilor de preflow la zero și efectuarea unui set de operații de saturare push pe arcurile reziduale care ies din sursă, $( s , v ) unde v ∈ V \ { s }$ . În mod similar, etichetele sunt inițializate astfel încât eticheta de la sursă să fie numărul de noduri din grafic, $𝓁 (s) = | V |$ , și tuturor celorlalte noduri li se dă o etichetă zero. Odată ce inițializarea este finalizată, algoritmul efectuează în mod repetat fie operațiile de împingere, fie de reetichetare împotriva nodurilor active până când nu se poate efectua nicio operație aplicabilă.

Apăsați

Operația de împingere se aplică pe un arc exterior admis $(u, v)$ al unui nod activ $u$ în $G f$ . Mută $min {x f (u), c f (u, v)}$ unități de debit de la $u$ la $v$ .

push(u, v):
    assert x_f[u] > 0 and 𝓁[u] == 𝓁[v] + 1
    Δ = min(x_f[u], c[u][v] - f[u][v])
    f[u][v] += Δ
    f[v][u] -= Δ
    x_f[u] -= Δ
    x_f[v] += Δ

O operație de împingere care face ca $f (u, v)$ să ajungă la $c (u, v)$ se numește o împingere saturată, deoarece folosește toată capacitatea disponibilă a arcului rezidual. În caz contrar, tot excesul de la nod este împins peste arcul rezidual. Aceasta se numește o apăsare nesaturantă sau nesaturată .

Relabelează

Operația de reetichetare se aplică pe un nod activ $u$ fără arcuri admise admise în $G f$ . Se modifică $𝓁 (u)$ pentru a fi valoarea minimă astfel încât să se creeze un arc exterior admisibil. Rețineți că acest lucru crește întotdeauna $𝓁 (u)$ și nu creează niciodată un arc abrupt, care este un arc $(u, v)$ astfel încât $c f (u, v)> 0$ și $𝓁 (u)> 𝓁 (v) + 1$ .

relabel(u):
    assert x_f[u] > 0 and 𝓁[u] <= 𝓁[v] for all v such that c_f[u][v] > 0
    𝓁[u] = 1 + min(𝓁[v] for all v such that c_f[u][v] > 0)

Efectele push și relabel

După o operație de împingere sau reetichetare, $𝓁$ rămâne o funcție de etichetare validă față de $f$ .

Pentru o operație de împingere pe un arc admisibil $(u, v)$ , acesta poate adăuga un arc $(v, u)$ la $E f$ , unde $𝓁 (v) = 𝓁 (u) - 1 \leq 𝓁 (u) + 1$ ; poate elimina, de asemenea, arcul $(u, v)$ din $E f$ , unde elimină efectiv constrângerea $𝓁 (u) \leq 𝓁 (v) + 1$ .

Pentru a vedea că o operațiune de reetichetare pe nodul $u$ păstrează validitatea lui $𝓁 (u)$ , observați că acest lucru este banal garantat prin definiție pentru arcurile externe ale lui u în $G f$ . Pentru arcurile în $u$ din $G f$ , $𝓁 (u)$ crescut poate satisface doar constrângerile mai puțin strâns, nu le poate încălca.

Algoritmul generic push-relabel

Algoritmul generic push-relabel este folosit doar ca o dovadă a conceptului și nu conține detalii de implementare cu privire la modul de selectare a unui nod activ pentru operațiile push și relabel. Această versiune generică a algoritmului se va termina în $O (V 2 E)$ .

Deoarece $𝓁 (s) = | V |$ , $𝓁 (t) = 0$ și nu există căi mai lungi de $| V | - 1$ în $G f$ , pentru ca $𝓁 (s)$ să îndeplinească condițiile valide de etichetare $s$ trebuie să fie deconectat de la $t$ . La inițializare, algoritmul îndeplinește această cerință prin crearea unui pre-flux $f$ care saturează toate arcurile $externe$ ale $lui s$ , după care $𝓁 (v) = 0$ este trivial valid pentru toate $v ∈ V \ { s , t }$ . După inițializare, algoritmul execută în mod repetat o operație de împingere sau reetichetare aplicabilă până când nu se aplică astfel de operații, moment în care pre-fluxul a fost convertit într-un debit maxim.

generic-push-relabel(G, c, s, t):
    create a pre-flow f that saturates all out-arcs of s
    let 𝓁[s] = |V|
    let 𝓁[v] = 0 for all v ∈ V \ {s}
    while there is an applicable push or relabel operation do
        execute the operation

Corectitudine

Algoritmul menține condiția ca $𝓁 să$ fie o etichetare validă în timpul executării sale. Acest lucru poate fi dovedit adevărat examinând efectele operațiilor de împingere și reetichetare asupra funcției de etichetă $𝓁$ . Operația de reetichetare mărește valoarea etichetei cu minimul asociat plus unul care va satisface întotdeauna $constrângerea 𝓁 (u) \leq 𝓁 (v) + 1$ . Operația de împingere poate trimite flux de la $u$ la $v$ dacă $𝓁 (u) = 𝓁 (v) + 1$ . Acest lucru se poate adăuga $(v, u)$ la $G f$ și poate șterge $(u, v)$ de la $G f$ . Adăugarea lui $(v, u)$ la $G f$ nu va afecta etichetarea validă, deoarece $𝓁 (v) = 𝓁 (u) - 1$ . Ștergerea lui $(u, v)$ din $G f$ elimină constrângerea corespunzătoare, deoarece proprietatea de etichetare validă $𝓁 (u) \leq 𝓁 (v) + 1$ se aplică numai arcurilor reziduale din $G f$ .

Dacă există o prefluire $f$ și o etichetare validă $𝓁$ pentru $f$ , atunci nu există o cale de $mărire$ de la $s$ la $t$ în graficul rezidual $G f$ . Acest lucru poate fi dovedit prin contradicție bazată pe inegalități care apar în funcția de etichetare atunci când se presupune că există o cale de mărire. Dacă algoritmul se termină, atunci toate nodurile din $V \ { s , t }$ nu sunt active. Aceasta înseamnă că toate $v ∈ V \ { s , t }$ nu au un debit în exces și, fără niciun exces, prefluxul $f$ respectă constrângerea de conservare a debitului și poate fi considerat un debit normal. Acest debit este debitul maxim în conformitate cu teorema minimă a debitului maxim, deoarece nu există o cale de mărire de la $s$ la $t$ .

Prin urmare, algoritmul va returna fluxul maxim la terminare.

Complexitatea timpului

Pentru a lega complexitatea în timp a algoritmului, trebuie să analizăm numărul de operații de împingere și reetichetare care apar în bucla principală. Numărul operațiilor de reetichetare, împingere saturată și apăsare nesaturată sunt analizate separat.

În algoritm, operația de reetichetare poate fi efectuată cel mult $(2 | V | - 1) (| V | - 2) <2 | V | De 2$ ori. Acest lucru se datorează faptului că valoarea de etichetare $𝓁 (u)$ pentru orice nod u nu poate scădea niciodată, iar valoarea maximă a etichetei este de cel mult $2 | V | - 1$ pentru toate nodurile. Aceasta înseamnă că operațiunea de reetichetare ar putea fi efectuată $2 | V | - de 1$ ori pentru toate nodurile $V \ { s , t }$ (adică $| V | - 2$ ). Acest lucru are ca rezultat o limitare a $O (V 2)$ pentru operația de reetichetare.

Fiecare apăsare saturantă pe un arc admisibil $(u, v)$ elimină arcul din $G f$ . Pentru ca arcul să fie reintrodus în $G f$ pentru o altă apăsare de saturare, $v$ trebuie mai întâi reetichetat, urmat de o apăsare pe arc $(v, u)$ , apoi $u$ trebuie reetichetat. În acest proces, $𝓁 (u)$ crește cu cel puțin două. Prin urmare, există $O (V)$ apăsări saturate pe $(u, v)$ , iar numărul total de apăsări saturate este cel mult $2 | V || E |$ . Acest lucru are ca rezultat un timp limitat de $O (VE)$ pentru operațiile de împingere saturate.

Limitarea numărului de împingeri nesaturante poate fi realizată printr-un argument potențial . Folosim funcția potențială $Φ = \sum [u \in V \land x f (u)> 0] 𝓁 (u)$ (adică $Φ$ este suma etichetelor tuturor nodurilor active). Este evident că $Φ$ este $0$ inițial și rămâne negativ pe tot parcursul execuției algoritmului. Atât reetichetarea, cât și împingerea saturată pot crește $Φ$ . Cu toate acestea, valoarea lui $Φ$ trebuie să fie egală cu 0 la terminare, deoarece nu pot exista noduri active rămase la sfârșitul execuției algoritmului. Acest lucru înseamnă că peste executarea algoritmului, împingerile nonsaturating trebuie să constituie diferența dintre relabel și operațiunile de împingere satureze pentru ca $Φ$ pentru a termina cu o valoare de 0. Operațiunea reetichetat poate crește $Φ$ cu cel mult $(2 | V | - 1) (| V | - 2)$ . O apăsare saturantă pe $(u, v)$ activează $v$ dacă era inactivă înainte de apăsare, crescând $Φ$ cu cel mult $2 | V | - 1$ . Prin urmare, contribuția totală a tuturor operațiunilor de împingere saturate la $Φ$ este cel mult $(2 | V | - 1) (2 | V || E |)$ . O apăsare nesaturantă $(u, v)$ dezactivează întotdeauna $u$ , dar poate activa și $v$ ca într-o apăsare saturantă. Ca urmare, scade $Φ$ cu cel puțin $𝓁 (u) - 𝓁 (v) = 1$ . Deoarece reetichetările și apăsările saturante cresc $Φ$ , numărul total de apăsări nesaturante trebuie să facă diferența de $(2 | V | - 1) (| V | - 2) + (2 | V | - 1) (2 | V || E |) \leq 4 | V | 2 | E |$ . Acest lucru are ca rezultat un timp limitat de $O (V 2 E)$ pentru operațiile de împingere nesaturante.

În concluzie, algoritmul execută reetichetări $O (V 2)$ , împingeri saturate $O (VE)$ și împingeri nesaturante $O (V 2 E)$ . Structurile de date pot fi proiectate pentru a alege și executa o operațiune aplicabilă în timp $O (1)$ . Prin urmare, complexitatea timpului algoritmului este $O (V 2 E)$ .

Exemplu

Următoarea este o mostră de execuție a algoritmului generic push-relabel, așa cum este definit mai sus, pe următoarea diagramă simplă a graficului fluxului de rețea.

Graficul rețelei de flux inițial

Graficul rețelei de flux maxim final

În exemplu, valorile h și e denotă eticheta $𝓁$ și respectiv excesul $x f$ al nodului în timpul executării algoritmului. Fiecare grafic rezidual din exemplu conține doar arcurile reziduale cu o capacitate mai mare de zero. Fiecare grafic rezidual poate conține mai multe iterații ale buclei operației de efectuare .

Operațiunea (algoritmele) algoritmului (e)	Grafic rezidual
Inițializați graficul rezidual setând prefluxul la valorile 0 și inițializând etichetarea.
Împingerea inițială de saturare se efectuează pe toate arcurile de prefluire din sursă, $s$ .
Nodul $a$ este reetichetat pentru a-și împinge debitul în exces către chiuvetă, $t$ . Excesul la $a$ este apoi împins la $b$ apoi $d$ în două împingeri ulterioare de saturare; care încă lasă $o$ cu ceva exces.

Din nou, $a$ este reetichetat pentru a-și împinge excesul de-a lungul ultimului său reziduu pozitiv rămas (adică împingeți excesul înapoi la $s$ ). Nodul $a$ este apoi eliminat din setul de noduri active.

Reetichetați $b$ și apoi împingeți excesul său la $t$ și $c$ .
Reetichetați $c$ și apoi împingeți excesul la $d$ .
Reetichetați $d$ și apoi împingeți excesul său la $t$ .
Acest lucru lasă nodul $b$ ca singurul nod activ rămas, dar nu își poate împinge fluxul în exces către chiuvetă. Reetichetați $b$ și apoi împingeți excesul către sursă, $s$ , prin nodul $a$ .

Împingeți ultimul bit de exces , la $o$ înapoi la sursă, $s$ . Nu există noduri active rămase. Algoritmul se termină și returnează fluxul maxim al graficului (așa cum se vede mai sus).

Exemplul (dar cu fluxul inițial de 0) poate fi rulat aici interactiv.

Implementări practice

În timp ce algoritmul generic push-relabel are complexitatea timpului $O (V 2 E)$ , implementările eficiente realizează $O (V 3)$ sau complexitatea timpului mai scăzută prin aplicarea regulilor adecvate în selectarea operațiilor de push și relabelare aplicabile. Performanța empirică poate fi îmbunătățită și mai mult prin euristică.

Structura de date „arc curent” și operațiunea de descărcare

Structura de date „arc curent” este un mecanism de vizitare a vecinilor de intrare și ieșire a unui nod din rețeaua de flux într-o ordine circulară statică. Dacă pentru un nod este creată o listă legată individual de vecini, structura datelor poate fi la fel de simplă ca un indicator în listă care trece prin listă și se întoarce la cap atunci când se termină.

Pe baza structurii de date „arc curent”, operația de descărcare poate fi definită. O operațiune de descărcare se aplică unui nod activ și împinge în mod repetat fluxul din nod până când devine inactiv, reetichetându-l după cum este necesar pentru a crea arcuri admisibile în proces.

discharge(u):
    while x_f[u] > 0 do
        if current-arc[u] has run off the end of neighbors[u] then
            relabel(u)
            rewind current-arc[u]
        else
            let (u, v) = current-arc[u]
            if (u, v) is admissible then
                push(u, v)
            let current-arc[u] point to the next neighbor of u

Reguli de selectare a nodurilor active

Definirea operației de descărcare reduce algoritmul push-relabel la selectarea repetată a unui nod activ de descărcare. În funcție de regula de selecție, algoritmul prezintă diferite complexități de timp. Din motive de scurtă durată, ignorăm $s$ și $t$ atunci când ne referim la noduri în următoarea discuție.

Regula de selecție FIFO

FIFO Algoritmul push-reetichetat organizează nodurile activ într - o coadă. Nodurile inițiale active pot fi inserate în ordine arbitrară. Algoritmul elimină întotdeauna nodul din partea din față a cozii pentru descărcare. Ori de câte ori un nod inactiv devine activ, acesta este atașat în spatele cozii.

Algoritmul are $O (V 3)$ complexitate de timp.

Regula de selecție din nou în etichetă

Algoritmul relabel-to-front push-relabel organizează toate nodurile într-o listă legată și menține invariantul că lista este sortată topologic în raport cu rețeaua admisibilă. Algoritmul scanează lista din față în spate și efectuează o operațiune de descărcare pe nodul curent dacă este activ. Dacă nodul este reetichetat, acesta este mutat în partea din față a listei și scanarea este repornită din față.

Algoritmul are, de asemenea, $o$ complexitate de timp $O$ $($ $V$ $3$ $)$ .

Cea mai înaltă regulă de selectare a etichetelor

Algoritmul push-relabel cu cea mai mare etichetă organizează toate nodurile în găleți indexate de etichetele lor. Algoritmul selectează întotdeauna un nod activ cu cea mai mare etichetă de descărcat.

Algoritmul are $O (V 2 \sqrt E)$ complexitate de timp. Dacă se folosește în schimb regula de selecție a etichetei celei mai mici, complexitatea timpului devine $O (V 2 E)$ .

Tehnici de implementare

Deși în descrierea algoritmului generic push- $relabel de$ mai sus, $𝓁 ($ $u$ $)$ este setat la zero pentru fiecare nod u altul decât $s$ și $t$ la început, este de preferat să efectuați o căutare în lățime înapoi de la $t$ pentru a calcula exact etichete.

Algoritmul este de obicei separat în două faze. Faza 1 calculează un pre-flux maxim descărcând numai noduri active ale căror etichete sunt sub $n$ . Faza a doua convertește prefluxul maxim într-un debit maxim returnând excesul de debit care nu poate atinge $t$ în $s$ . Se poate arăta că faza a doua are complexitatea timpului $O (VE)$ indiferent de ordinea operațiilor de împingere și reetichetare și, prin urmare, este dominată de prima fază. Alternativ, poate fi implementat folosind descompunerea fluxului.

Euristicile sunt cruciale pentru îmbunătățirea performanței empirice a algoritmului. Două euristici utilizate în mod obișnuit sunt euristica gap și euristica globală de reetichetare. Euristica decalajului detectează lacune în funcția de etichetare. Dacă există o etichetă 0 <𝓁 ' <| V | pentru care nu există nod $u$ astfel încât $𝓁 (u) = 𝓁'$ , apoi orice nod $u$ cu $𝓁' <𝓁 (u) <| V |$ a fost deconectat de la $t$ și poate fi reetichetat la $(| V | + 1)$ imediat. Euristice redefini la nivel mondial efectuează periodic înapoi-lățime prima căutare de la $t$ în $G f$ pentru a calcula etichetele exacte ale nodurilor. Ambele euristici ignoră operațiile de etichetare inutile, care reprezintă un blocaj al algoritmului și contribuie la ineficacitatea arborilor dinamici.

Exemple de implementări

Implementarea C

#include <stdlib.h>
#include <stdio.h>

#define NODES 6
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
#define INFINITE 10000000

void push(const int * const * C, int ** F, int *excess, int u, int v) {
  int send = MIN(excess[u], C[u][v] - F[u][v]);
  F[u][v] += send;
  F[v][u] -= send;
  excess[u] -= send;
  excess[v] += send;
}

void relabel(const int * const * C, const int * const * F, int *height, int u) {
  int v;
  int min_height = INFINITE;
  for (v = 0; v < NODES; v++) {
    if (C[u][v] - F[u][v] > 0) {
      min_height = MIN(min_height, height[v]);
      height[u] = min_height + 1;
    }
  }
};

void discharge(const int * const * C, int ** F, int *excess, int *height, int *seen, int u) {
  while (excess[u] > 0) {
    if (seen[u] < NODES) {
      int v = seen[u];
      if ((C[u][v] - F[u][v] > 0) && (height[u] > height[v])) {
        push(C, F, excess, u, v);
      } else {
        seen[u] += 1;
      }
    } else {
      relabel(C, F, height, u);
      seen[u] = 0;
    }
  }
}

void moveToFront(int i, int *A) {
  int temp = A[i];
  int n;
  for (n = i; n > 0; n--) {
    A[n] = A[n-1];
  }
  A[0] = temp;
}

int pushRelabel(const int * const * C, int ** F, int source, int sink) {
  int *excess, *height, *list, *seen, i, p;

  excess = (int *) calloc(NODES, sizeof(int));
  height = (int *) calloc(NODES, sizeof(int));
  seen = (int *) calloc(NODES, sizeof(int));

  list = (int *) calloc((NODES-2), sizeof(int));

  for (i = 0, p = 0; i < NODES; i++){
    if ((i != source) && (i != sink)) {
      list[p] = i;
      p++;
    }
  }

  height[source] = NODES;
  excess[source] = INFINITE;
  for (i = 0; i < NODES; i++)
    push(C, F, excess, source, i);

  p = 0;
  while (p < NODES - 2) {
    int u = list[p];
    int old_height = height[u];
    discharge(C, F, excess, height, seen, u);
    if (height[u] > old_height) {
      moveToFront(p, list);
      p = 0;
    } else {
      p += 1;
    }
  }
  int maxflow = 0;
  for (i = 0; i < NODES; i++)
    maxflow += F[source][i];

  free(list);

  free(seen);
  free(height);
  free(excess);

  return maxflow;
}

void printMatrix(const int * const * M) {
  int i, j;
  for (i = 0; i < NODES; i++) {
    for (j = 0; j < NODES; j++)
      printf("%d\t",M[i][j]);
    printf("\n");
  }
}

int main(void) {
  int **flow, **capacities, i;
  flow = (int **) calloc(NODES, sizeof(int*));
  capacities = (int **) calloc(NODES, sizeof(int*));
  for (i = 0; i < NODES; i++) {
    flow[i] = (int *) calloc(NODES, sizeof(int));
    capacities[i] = (int *) calloc(NODES, sizeof(int));
  }

  // Sample graph
  capacities[0][1] = 2;
  capacities[0][2] = 9;
  capacities[1][2] = 1;
  capacities[1][3] = 0;
  capacities[1][4] = 0;
  capacities[2][4] = 7;
  capacities[3][5] = 7;
  capacities[4][5] = 4;

  printf("Capacity:\n");
  printMatrix(capacities);

  printf("Max Flow:\n%d\n", pushRelabel(capacities, flow, 0, 5));

  printf("Flows:\n");
  printMatrix(flow);

  return 0;
}

Implementare Python

def relabel_to_front(C, source: int, sink: int) -> int:
    n = len(C)  # C is the capacity matrix
    F = [[0] * n for _ in range(n)]
    # residual capacity from u to v is C[u][v] - F[u][v]

    height = [0] * n  # height of node
    excess = [0] * n  # flow into node minus flow from node
    seen   = [0] * n  # neighbours seen since last relabel
    # node "queue"
    nodelist = [i for i in range(n) if i != source and i != sink]

    def push(u, v):
        send = min(excess[u], C[u][v] - F[u][v])
        F[u][v] += send
        F[v][u] -= send
        excess[u] -= send
        excess[v] += send

    def relabel(u):
        # Find smallest new height making a push possible,
        # if such a push is possible at all.
        min_height = ∞
        for v in xrange(n):
            if C[u][v] - F[u][v] > 0:
                min_height = min(min_height, height[v])
                height[u] = min_height + 1

    def discharge(u):
        while excess[u] > 0:
            if seen[u] < n:  # check next neighbour
                v = seen[u]
                if C[u][v] - F[u][v] > 0 and height[u] > height[v]:
                    push(u, v)
                else:
                    seen[u] += 1
            else:  # we have checked all neighbours. must relabel
                relabel(u)
                seen[u] = 0

    height[source] = n  # longest path from source to sink is less than n long
    excess[source] = ∞  # send as much flow as possible to neighbours of source
    for v in range(n):
        push(source, v)

    p = 0
    while p < len(nodelist):
        u = nodelist[p]
        old_height = height[u]
        discharge(u)
        if height[u] > old_height:
            nodelist.insert(0, nodelist.pop(p))  # move to front of list
            p = 0  # start from front of list
        else:
            p += 1

    return sum(F[source])

Languages

In other projects