Algorytm push-relabel

Algorytm push-relabel

Rodzaj	problem maksymalnego przepływu
Struktura danych	sieć przepływowa
Złożoność
Czasowa	$O(V^{2}E)$

Algorytm push-relabel – jeden z najbardziej efektywnych algorytmów obliczania maksymalnego przepływu. Ogólny algorytm działa ze złożonością $O(V^{2}E),$ podczas gdy modyfikacja Relabel-to-Front ma złożoność czasową $O(V^{3}),$ rozwiązanie z wyborem najbardziej aktywnego wierzchołka $O(V^{2}{\sqrt {E}}),$ a implementacja z dynamicznym drzewem Sleatora-Tarajana $O(VE\log(V^{2}/E)).$ Asymptotycznie, algorytm ten jest znacznie bardziej efektywny niż algorytm Edmondsa-Karpa, którego złożoność czasowa wynosi $O(VE^{2}).$

Działanie

W sieci przepływowej, przepływ wpływający do wierzchołka musi być równy przepływowi opuszczającemu wierzchołek (z wyjątkiem źródła $s$ i ujścia $t$). W związku z tym ograniczeniem nie można akumulować przepływu w sieci.

Algorytmy przedprzepływowe pomijają to założenie i pozwalają na sytuację, gdy do wierzchołka wpływa więcej przepływu niż z niego wypływa. Sytuacja ta nazywana jest nadmiarowym przepływem, bądź przedprzepływem. Wierzchołek z nadmiarowym przepływem nazywany jest wierzchołkiem aktywnym. Nadmiarowy przepływ można jedynie przemieścić w dół krawędzi residualych grafu residualnego. Przepływ zostaje przesłany przez sieć (push) poprzez dostosowanie wysokości wierzchołków. Wysokość wierzchołków jest dostosowywana i utrzymywana za pomocą koncepcji valid labelling. Ściśle mówiąc, koncepcja ta zakłada, że dla każdej krawędzi residualnej $\mathrm {height} (u)\leqslant \mathrm {height} (v)+1,$ gdzie $\mathrm {height} (u)$ jest wysokością wierzchołka $u,$ dla każdej krawędzi residualnej incydentnej do $u.$ Innymi słowy, wierzchołek nie może być wyższy o więcej niż 1 od swojego sąsiada na krawędzi residualnej (przy czym nie istnieje ograniczenie o ile niższy może być).

Przepływ przepływa zawsze z wierzchołka o większej wysokości do wierzchołka o mniejszej wysokości.

Przesłanie przedprzepływu przez sieć oznacza przemieszczenie go w dół po krawędzi residualnej z wierzchołka $u$ do wierzchołka $v,$ gdzie $\mathrm {height} (u)=\mathrm {height} (v)+1.$ Operacja push nazywana jest wysycającą (saturating push) jeśli użyta została cała przepustowość krawędzi residualnej (a więc krawędź $(u,v)$ została usunięta z grafu residualnego). Sytuację w której po przesłaniu przepływu dostępna jest jeszcze pojemność krawędzi $(u,v)$ nazywa się niewysycającą (non-saturating push). Należy zauważyć, że non-saturating push wyczerpuje cały nadmiarowy przepływ z wierzchołka $u,$ z kolei saturating push może wyczerpywać $u,$ ale nie musi.

Definicja

Algorytm push-relabel znajduje maksymalny przepływ dla sieci przepływowej, spełniającej następujące warunki:

Ograniczenie objętości:	$f(u,v)\leqslant c(u,v).$ Przepływ wzdłuż krawędzi nie może przekraczać jej przepustowości.
Symetria skośna:	$f(u,v)=-f(v,u).$ Suma przepływów w odwrotnych kierunkach musi być zerowa.
Zachowanie przepływu:	$\sum _{w\in V}f(u,w)=0,$ chyba że $u=s$ lub $u=t.$ Przepływ sieciowy do wierzchołka jest zerowy, z wyjątkiem źródła, które „produkuje” przepływ, i ujścia, które „konsumuje” przepływ.

Algorytm przedprzepływowy zachowuje dwa pierwsze warunki dla sieci przepływowej, jednocześnie zaniedbując trzeci na czas trwania algorytmu (algorytm kończy się kiedy cały nadmiar jest usunięty z grafu – w tym momencie występuje już prawidłowy przepływ, a warunek zachowania przepływu jest spełniony).

Ograniczenie na nieujemność nadmiaru: $\sum _{w\in V}f(u,w)=\mathrm {excess} (u)\geqslant 0$ dla wszystkich wierzchołków $u\neq s.$ Więcej przepływu wpływa do wierzchołka niż go opuszcza.

Dla danej sieci $G(V,E)$ o przepustowości $c(u,v)$ z wierzchołka $u$ do wierzchołka $v,$ i przepływie pomiędzy $u$ i $v$ danym jako $f(u,v),$ źródle $s$ i ujściu $t,$ możemy wyznaczyć maksymalny przepływ jaki można przesłać od „s” do „t”. Algorytm wykorzystuje definicje:

krawędź residualna:	Jeśli dostępna jest przepustowość $c(u,v)-f(u,v)>0$ mamy krawędź residualną $r(u,v).$
krawędź residualna (odwrotna):	$r(v,u)=-f(u,v).$ Możemy przesyłać przepływ w obu kierunkach.
graf residualny:	Zestaw krawędzi residualnych formuje graf residualny.
poprawne etykietowanie ("legal labelling"):	Dla krawędzi residualnych $(u,v),$ $\mathrm {height} (u)\leqslant \mathrm {height} (v)+1$ operację push możemy wykonywać jedynie na wierzchołkach.
nadmiar(u):	Suma przepływu wpływającego do $u$ i opuszczającego $u.$
wysokość(u):	Każdemu wierzchołkowi przypisana jest konkretna wysokość. Dla wartości $\leqslant |V|,$ wysokość służy do oszacowania odległości do ujścia $t.$ Dla wartości $>|V|,$ wysokość służy do oszacowania odległości z powrotem do źródła $s.$

Można zaobserwować, że najdłuższa możliwa ścieżka z $s$ do $t$ ma długość $|V|$ wierzchołków. Stąd musi być możliwe, aby przypisać wysokość do wierzchołków dla każdego prawidłowego przepływu $\mathrm {height} (s)=|V|$ i $\mathrm {height} (t)=0,$ a jeśli występuje przepływ dodatni z $u$ do $v,$ $\mathrm {height} (u)>\mathrm {height} (v).$ W odróżnieniu od algorytmu Forda-Fulkersona, przepływ przez sieć nie musi być przepływem prawidłowym przez cały czas trwania algorytmu.

Algorytm Push-Relabel

Wysokości aktywnych wierzchołków są podnoszone na tyle, by zaszło przesłanie przepływu do sąsiednich wierzchołków – dzieje się tak aż do momentu kiedy cały przepływ dotrze do ujścia $t.$ Wówczas kontynuujemy podnoszenie wysokości wewnętrznych wierzchołków aż do momentu, kiedy cały przepływ, jaki wpłynął do sieci, ale nie opuścił jej przez $t,$ wpłynie z powrotem do $s.$ Wierzchołek może osiągnąć wysokość $2|V|-1$ zanim proces ten zostanie ukończony, ponieważ najdłuższa możliwa ścieżka do $s$ nie przechodząca przez $t$ jest długości $|V|-1,$ i $\mathrm {height} (s)=|V|.$ Wysokość $t$ jest utrzymywana jako 0.

Kiedy już cały możliwy przepływ zostanie przemieszczony do $t,$ nie istnieje ścieżka w grafie prowadząca z $s$ do $t$ (w rzeczywistości stwierdzenie to jest prawdziwe tak długo jak wyczerpujemy minimalnego przekroju). Oznacza to, że kiedy nadmiarowy przepływ powróci do $s,$ mamy do czynienia nie tylko z przepływem spełniającym zasadę zachowania przepływu, ale jednocześnie z przepływem maksymalnym według twierdzenia o minimalnym przekroju i maksymalnym przepływie. Algorytm bazuje na dwóch funkcjach:

Push

Push z $u$ do $v$ oznacza przesłanie całej możliwej ilości nadmiarowego przepływu z $u$ do $v.$ Aby przeprowadzić procedurę push, spełnione muszą być trzy warunki:

$u$ jest aktywny	lub $\mathrm {excess} (u)>0.$ Więcej przepływu dociera do wierzchołka niż go opuszcza.
$r(u,v)>0$	Istnieje krawędź residualna $r(u,v)$ od $u$ do $v,$ dla której $r(u,v)=c(u,v)-f(u,v)$
$\mathrm {height} (u)=\mathrm {height} (v)+1$	$u$ jest wyższy niż $v.$

Jeśli powyższe warunki są spełnione, można przeprowadzić push:

Function Push(u,v)
   flow = min(excess(u), c(u,v)-f(u,v));
   excess(u) -= flow;                   // odejmuje ilość przepływu, która zostanie przesłana dalej
   excess(v) += flow;                   // dodaje przepływ do wierzchołka do którego przesyłamy
   f(u,v) += flow;                      // dodaje przepływ do krawędzi (u,v)
   f(v,u) -= flow;                      // odejmuje przepływ od krawędzi przeciwnej, aby zachować skośną symetrię

Relabel

Kiedy wykonujemy operację relabel na wierzchołku $u,$ zwiększamy jego wysokość do momentu kiedy jest o 1 większa od najniższego sąsiada w grafie residualnym. Warunki dla relabel:

$u$ jest aktywny
$\mathrm {height} (u)\leqslant \mathrm {height} (v)$ gdzie $r(u,v)>0$

Mamy więc nadmiarowy przepływ do przesłania, jednak nie znajdujemy się wyżej niż którykolwiek z sąsiadów posiadających dostępną pojemność wzdłuż ich krawędzi. Wtedy możemy wykonać relabel:

Function Relabel(u)
   height(u) = min(height(v) where r(u,v) > 0) + 1;

Algorytm Push-Relabel

Cały algorytm Push-Relabel wygląda następująco:

Algorithm Push-Relabel(G(V,E),s,t)
   while push or relabel are legal:   //dopóki możemy wykonywać operację push-relabel
      Perform a legal push, or
      perform a legal relabel;

Wykonywanie tych dwóch funkcji w dowolnej kolejności, tak długo jak pozostają aktywne wierzchołki, prowadzi do obliczenia maksymalnego przepływu. Złożoność obliczeniowa tego algorytmu, gdy nie uwzględniamy kolejności wykonywania operacji push i relabel, wynosi $O(V^{2}E).$ Czynnikiem zwiększającym pesymistyczną złożoność algorytmu jest ilość wykonywanych operacji non-saturating push.

Algorytm Relabel-to-Front

Algorytm Relabel-to-Front jest wariantem algorytmu Push-Relabel, który obniża złożoność obliczeniową z $O(V^{2}E)$ do $O(V^{3}).$ Osiąga się to dzięki przeprowadzeniu procedur push i relabel w określonym porządku. Główna różnica polega na tym, że wykonujemy push and relabel na pojedynczym wierzchołku do momentu, kiedy jego nadmiar jest zupełnie wykorzystany. To ogranicza ilość operacji non-saturating push, które stanowią czynnik zwiększający pesymistyczną złożoność obliczeniową algorytmu.

Aby to zrobić, tworzymy listę wszystkich wierzchołków w grafie $L=V-\{s,t\},$ w dowolnej kolejności (zostaną uporządkowane podczas działania algorytmu). Dodatkowo dla każdego wierzchołka tworzymy listę sąsiedztwa, której kolejność jest dowolna, ale musi być stała. Elementami tej listy są potencjalni sąsiedzi do których możemy przesłać przepływ. Następnie, kolejno zaczynając od pierwszego wierzchołka na liście przeprowadzamy procedurę Discharge dla każdego wierzchołka $u\in L,$ jeśli jest aktywny. Jeśli nie możemy wykonać operacji push, wykonujemy relabel i umieszczamy wierzchołek na początku listy.

Procedura Discharge

W relabel-to-front, procedura discharge na wierzchołku przebiega następująco:

Function Discharge(u):
    while excess(u) > 0:
       if (u.currentNeighbour != NIL):
          push(u, u.currentNeighbour);
          u.currentNeighbour = u.nextNeighbour;
       else:
          relabel(u);
          u.currentNeighbour = u.headOfNeighbourList;    //wraca z powrotem na początek listy sąsiadów

Relabel-to-Front

W algorytmie relabel-to-front w pełni rozładowujemy wierzchołek przed przejściem do kolejnego. Kolejność ta ogranicza ilość wykonywanych procedur non-saturating push.

Algorithm Relabel-to-Front(G(V,E),s,t):
   for each vertex v incident to s:
      push(s,v);                       // wyczerpie to krawędzie (s,v) - przepływ jest ograniczony
   L = v - {s,t};                      // tworzy listę wierzchołków w dowolnej kolejności
   current = L.head;
   while (current != NIL):
      old_height = height(u);
      discharge(u);
      if height(u) > old_height:
         Move u to front of L
      current = current.next;

Złożoność obliczeniowa algorytmu relabel-to-front wynosi $O(V^{3})$(dowód pomijamy). Ponownie czynnikiem zwiększającym pesymistyczną złożoność algorytmu jest ilość procedur ‘non-saturating push’, jednak w tym przypadku ich ilość została zredukowana. Należy zauważyć, że po wykonaniu pierwszego kroku nie istnieje ścieżka z $s$ do $t$ w grafie esidualnym.

Przykładowe implementacje

Implementacja w 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;
}

Implementacja w Pythonie:

  def relabel_to_front(C, source, sink):
     n = len(C) # C - macierz przepustowości
     F = [[0] * n for _ in xrange(n)]
     # przepustowość residualna z u do v wynosi C[u][v] - F[u][v]

     height = [0] * n # wysokość wierzchołka
     excess = [0] * n # różnica między przepływem wpływającym do wierzchołka a opuszczającym go
     seen   = [0] * n # wierzchołki odwiedzone od czasu ostatniego wywołania relabel
     # kolejka wierzchołków
     nodelist = [i for i in xrange(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):
         # znajdź najmniejszą wysokość umożliwiającą
         # operację push
         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: # sprawdź kolejnego sąsiada
                 v = seen[u]
                 if C[u][v] - F[u][v] > 0 and height[u] > height[v]:
                     push(u, v)
                 else:
                     seen[u] += 1
             else: # odwiedzono wszystkich sąsiadów, wykonujemy relabel
                 relabel(u)
                 seen[u] = 0

     height[source] = n   # najdłuższa ścieżka z s to t jest mniejsza niż n
     excess[source] = Inf # prześlij jak najwięcej przepływu do wszystkich sąsiadów s
     for v in xrange(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)) # przenieś na początek listy
             p = 0 # zacznij od początku listy
         else:
             p += 1

     return sum(F[source])

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 26.4: Push-relabel algorithms, and section 26.5: The relabel-to-front-algorithm.
• Andrew V. Goldberg, Robert E. Tarjan. A new approach to the maximum flow problem. Annual ACM Symposium on Theory of Computing, Proceedings of the eighteenth annual ACM symposium on Theory of computing, 136–146. ISBN 0-89791-193-8, 1986.