Push-relabel algoritam maksimalnog protoka grafa

Push-relabel algoritam je jedan od najefikasnijih algoritama za izračunavanje maksimalnog protoka. U opštem slučaju, algoritam ima vremensku složenost ${\displaystyle O(V^{2}E)}$, dok implementacija korišćenjem FIFO (prvi unutra - prvi napolje) pravila pronalaženja najviše tačke ima složenost ${\displaystyle O(V^{3})}$. Pravilo pronalaženja najviše aktivne tačke daje složenost ${\displaystyle O(V^{2}{\sqrt {E}})}$, a implementacija preko Sletorovog i Tarjanovog dinamičkog stabla ima složenost ${\displaystyle O(VE\log(V^{2}/E))}$. Asimptotski, algoritam je efikasniji od Edmonds-Karpovog algoritma koji ima složenost ${\displaystyle O(VE^{2})}$.

Algoritam

Data je mreža protoka ${\displaystyle G(V,E)}$, tako da je kapacitet iz čvora u, do čvora v zadat sa ${\displaystyle c(u,v)}$, sa izvorom s i ponorom t. Želimo da pronađemo maksimalni protok koji se može poslati od s do t, kroz zadatu mrežu. Na čvorove se primenju dve vrste operacija, push i relabel. Tokom algoritma održavamo:

• ${\displaystyle f(u,v)}$. Trenutni protok od u do v. Dostupan kapacitet je ${\displaystyle c(u,v)-f(u,v)}$.
• ${\displaystyle \mathrm {visina} (u)}$. Operaciju push od u do v vršimo samo kada je ${\displaystyle \mathrm {visina} (u)}$ > ${\displaystyle \mathrm {visina} (v)}$. Za svako u, ${\displaystyle \mathrm {visina} (u)}$ je neoznačen ceo broj.
• ${\displaystyle \mathrm {visak} (u)}$. Zbir protoka od, i do, čvora u.

Nakon svakog koraka algoritma važi:

• ${\displaystyle \ f(u,v)\leq c(u,v)}$. Protok između u i v, ne prekoračuje kapacitet.
• ${\displaystyle \ f(u,v)=-f(v,u)}$. Održavamo protok mreže.
• ${\displaystyle \ \sum _{v}f(v,u)=\mathrm {visak} (u)\geq 0}$ za svaki čvor ${\displaystyle u\neq s}$. Samo izvor može da proizvodi protok.

Primetimo da je poslednji uslov manje rigorozan od odgovarajućeg uslova za pravilan protok u običnoj mreži protoka.

Zapažamo da je najduži mogući put od s do t dugačak ${\displaystyle |V|}$ čvorova. Dakle, mora biti moguće dodeliti visinu takvim čvorovima za svaki pravilan protok. ${\displaystyle \mathrm {visina} (s)=|V|}$ i ${\displaystyle \mathrm {height} (t)=0}$, i ako postoji pozitivan protok od u do v, ${\displaystyle \mathrm {height} (u)>\mathrm {height} (v)}$. Kako podešavamo visinu čvorova, tok teče kroz mrežu kao voda kroz pejzaž. Za razliku od algoritama kao što je Ford-Fulkersonov, protok kroz mrežu nije obavezno i pravilan protok u toku izvršavanja algoritma.

Ukratko, visine čvorova (izuzev s i t) su podešene, i tok je poslat između čvorova, dok maksimalan mogući protok ne stigne do t. Tada nastavljamo da povećavamo visinu internih čvorova dok se sav tok koji je ušao u mrežu, ali nije dostigao t, ne vrati do s. Čvor može dostići visinu ${\displaystyle 2|V|-1}$ pre nego što je ovo završeno, tako da je najduži mogući put nazad do s, ne računajući t, jednak ${\displaystyle |V|-1}$, a ${\displaystyle \mathrm {visina} (s)=|V|}$. Visina čvora t se čuva na 0.

Push

Push od u do v znači slanje dela viška protoka u u, do čvora v. Ovi uslovi moraju biti ispunjeni da bi push mogao da se odvija:

• ${\displaystyle \mathrm {visak} (u)>0}$. Više toka ulazi u čvor, nego što iz njega izlazi, do sad.
• ${\displaystyle c(u,v)-f(u,v)>0}$. Raspoloživ određeni kapacitet iz u ka v.
• ${\displaystyle \mathrm {visina} (u)>\mathrm {visina} (v)}$. Može se slati samo u niži čvor.

Šaljemo određenu količinu toka jednaku ${\displaystyle \min(\mathrm {visak} (u),c(u,v)-f(u,v))}$.

Relabel

Operacija relabel na čvoru u je povećavanje visine tog čvora dok ona nije veća od najmanje jednog čvora čiji kapacitet nije ispunjen. Uslovi za ovu operaciju:

• ${\displaystyle \mathrm {visak} (u)>0}$. Mora da postoji razlog za ovu operaciju.
• ${\displaystyle \mathrm {visina} (u)\leq \mathrm {visina} (v)}$ za svako v takvo da je ${\displaystyle c(u,v)-f(u,v)>0}$. Jedini čvorovi koji imaju dovoljan kapacitet su viši.

Kada vršimo ovu operaciju na u, podešavamo ${\displaystyle \mathrm {visina} (u)}$ tako da ona bude najniža vrednost takva da je ${\displaystyle \mathrm {visina} (u)>\mathrm {visina} (v)}$ za neko v gde je ${\displaystyle c(u,v)-f(u,v)>0}$.

Push-relabel algoritam

Push-relabel algoritmi generalno imaju ovakav raspored:

1. Sve dok se može izvršiti push ili relabel operacija
   1. Izvrši legalan push, ili
   2. Izvrši legalan relabel

Složenost ovih algoritama je generalno ${\displaystyle O(V^{2}E)}$.

Pražnjenje

U relabel-to-front algoritmu, pražnjenje na čvoru u je sledeća operacija:

1. Sve dok je ${\displaystyle \mathrm {visak} (u)>0}$:
   1. Ako nisu sve komšije isprobane od poslednje relabel operacije:
      1. Pokušaj da izvršiš operaciju push na nekom od neisprobanih komšija.
   2. Inače: Izvrši operaciju relabel nad u

Ovo zahteva da je za svaki čvor poznato koji čvorovi su isprobani od poslednjeg relabel-a.

Relabel-to-front algoritam, FIFO implementacija

U relabel-to-front algoritmu, red operacija push i relabel je zadat na sledeći način:

1. Pošalji što je moguće veći deo toka iz s.
2. Sagradi listu svih temena osim s i t.
3. Sve dok nismo prošli kroz celu listu:
   1. Isprazni trenutno najviše teme
   2. Ako se visina najviše tačke izmenila:
      1. Pomeri trenutnu najvišu tačku na početak liste
      2. Ponovi prolazak kroz listu iz početka

Složenost ovog algoritma je ${\displaystyle O(V^{3})}$.

Primer implementacije u C-u:

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

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

	void push(const int **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 **C, const int **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 **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 **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 **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;
	}

Primer implementacije u Python-u:

  def relabel_to_front(C, source, sink):
     n = len(C) # C is the capacity matrix
     F = [[0] * n for _ in xrange(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 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):
         # 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] = Inf # send as much flow as possible to neighbours of source
     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)) # move to front of list
             p = 0 # start from front of list
         else:
             p += 1

     return sum(F[source])

Primetimo da gornja implementacija nije previše efikasna. Sporija je od Edmonds-Karpovog algoritma čak i za guste grafove. Da bismo ga ubrzali, možemo uraditi bar dve stvari:

• Napraviti listu komšija za svaki čvor, i neka indeks posecen[u] bude iterator za ovaj čvor, umesto da obilazimo sve čvorove.
• Ukoliko postoji ${\displaystyle k}$ takvo da ni za jedan čvor ${\displaystyle u}$ ne važi, ${\displaystyle \mathrm {visina} (u)=k}$, možemo podesiti ${\displaystyle \mathrm {visina} (u)=\max(\mathrm {visina} (u),\mathrm {visina} (s)+1)}$ za sve čvorove, osim za ${\displaystyle s}$ za koji je ${\displaystyle \mathrm {visina} (u)>k}$. Ovo je zbog toga što svako takvo ${\displaystyle k}$ predstavlja minimalan rez grafa , i nijedan deo toka neće ići iz čvorova ${\displaystyle S=\{u\mid \mathrm {visina} (u)>k\}}$ u čvorove ${\displaystyle T=\{v\mid \mathrm {visina} (v)<k\}}$. Ako ${\displaystyle (S,T)}$ nije bio minimalan rez, postojala bi ivica ${\displaystyle (u,v)}$ takva da ${\displaystyle u\in S}$, ${\displaystyle v\in T}$ i ${\displaystyle c(u,v)-f(u,v)>0}$. Ali onda ${\displaystyle \mathrm {visina} (u)}$ nikada ne bi bila veća od ${\displaystyle \mathrm {visina} (v)+1}$, što je kontradiktorno tome da je ${\displaystyle \mathrm {visina} (u)>k}$ i ${\displaystyle \mathrm {visina} (v)<k}$.

Reference

• Cormen, Thomas H.; Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw–Hill. ISBN 978-0-262-03293-3. CS1 одржавање: Вишеструка имена: списак аутора (веза) 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. 1986. ISBN 978-0-89791-193-1.