Изворни код странице Push-relabel algoritam maksimalnog protoka grafa

{{Neprovereni seminarski}}

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

== Algoritam ==

Data je mreža protoka <math>G(V,E)</math>, tako da je kapacitet iz čvora ''u'', do čvora ''v'' zadat sa <math>c(u,v)</math>, 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:
* <math>f(u,v)</math>. Trenutni protok od ''u'' do ''v''. Dostupan kapacitet je <math>c(u,v) - f(u,v)</math>.
* <math>\mathrm{visina}(u)</math>. Operaciju ''push'' od ''u'' do ''v'' vršimo samo kada je <math>\mathrm{visina}(u)</math> > <math>\mathrm{visina}(v)</math>. Za svako ''u'', <math>\mathrm{visina}(u)</math> je neoznačen ceo broj.
* <math>\mathrm{visak}(u)</math>. Zbir protoka od, i do, čvora ''u''.

Nakon svakog koraka algoritma važi:

* <math>\ f(u,v) \leq c(u,v)</math>. Protok između ''u'' i ''v'', ne prekoračuje kapacitet.
* <math>\ f(u,v) = - f(v,u)</math>. Održavamo protok mreže.
* <math>\ \sum_v f(v,u) = \mathrm{visak}(u) \geq 0</math> za svaki čvor <math>u \neq s</math>. 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 <math>|V|</math> čvorova. Dakle, mora biti moguće dodeliti ''visinu'' takvim čvorovima za svaki pravilan protok. <math>\mathrm{visina}(s) = |V|</math> i <math>\mathrm{height}(t) = 0</math>, i ako postoji pozitivan protok od ''u'' do ''v'', <math>\mathrm{height}(u) > \mathrm{height}(v)</math>. Kako podešavamo visinu čvorova, tok teče kroz mrežu kao voda kroz pejzaž. Za razliku od algoritama kao što je [[Ford-Fulkersonov algoritam|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 <math>2|V|-1</math> pre nego što je ovo završeno, tako da je najduži mogući put nazad do ''s'', ne računajući ''t'', jednak <math>|V|-1</math>, a <math>\mathrm{visina}(s) = |V|</math>. 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:
* <math>\mathrm{visak}(u) > 0</math>. Više toka ulazi u čvor, nego što iz njega izlazi, do sad.
* <math>c(u,v) - f(u,v) > 0</math>. Raspoloživ određeni kapacitet iz ''u'' ka ''v''.
* <math>\mathrm{visina}(u) > \mathrm{visina}(v)</math>. Može se slati samo u niži čvor.
Šaljemo određenu količinu toka jednaku <math>\min(\mathrm{visak}(u), c(u,v)-f(u,v))</math>.

=== 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:
* <math>\mathrm{visak}(u) > 0</math>. Mora da postoji razlog za ovu operaciju.
* <math>\mathrm{visina}(u) \leq \mathrm{visina}(v)</math> za svako ''v'' takvo da je <math>c(u,v)-f(u,v) > 0</math>. Jedini čvorovi koji imaju dovoljan kapacitet su viši.
Kada vršimo ovu operaciju na ''u'', podešavamo <math>\mathrm{visina}(u)</math> tako da ona bude najniža vrednost takva da je <math>\mathrm{visina}(u) > \mathrm{visina}(v)</math> za neko ''v'' gde je <math>c(u,v)-f(u,v) > 0</math>.

=== Push-relabel algoritam ===

''Push-relabel algoritmi'' generalno imaju ovakav raspored:
# Sve dok se može izvršiti ''push'' ili ''relabel'' operacija
## Izvrši legalan ''push'', ili
## Izvrši legalan ''relabel''

Složenost ovih algoritama je generalno <math>O(V^2 E)</math>.

=== Pražnjenje ===

U ''relabel-to-front'' algoritmu, ''pražnjenje'' na čvoru ''u'' je sledeća operacija:
# Sve dok je <math>\mathrm{visak}(u) > 0</math>:
## Ako nisu sve komšije isprobane od poslednje ''relabel'' operacije:
### Pokušaj da izvršiš operaciju ''push'' na nekom od neisprobanih komšija.
## 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:

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

Složenost ovog algoritma je <math>O(V^3)</math>.

Primer implementacije u [[C (programski jezik)|C]]-u:
<source lang="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 **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;
	}
</source>

Primer implementacije u [[Pajton (programski jezik)|Python]]-u:
<source lang="python">
  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])
</source>
Primetimo da gornja implementacija nije previše efikasna. Sporija je od [[Edmonds-Karpov algoritam|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 <code>posecen[u]</code> bude iterator za ovaj čvor, umesto da obilazimo sve čvorove.
* Ukoliko postoji <math>k</math> takvo da ni za jedan čvor <math>u</math> ne važi, <math>\mathrm{visina}(u)=k</math>, možemo podesiti <math>\mathrm{visina}(u)=\max(\mathrm{visina}(u), \mathrm{visina}(s) + 1)</math> za sve čvorove, osim za <math>s</math> za koji je <math>\mathrm{visina}(u)>k</math>. Ovo je zbog toga što svako takvo <math>k</math> predstavlja minimalan rez grafa , i nijedan deo toka neće ići iz čvorova <math>S = \{u\mid \mathrm{visina}(u)>k\}</math> u čvorove <math>T = \{v\mid \mathrm{visina}(v)<k\}</math>. Ako <math>(S,T)</math> nije bio minimalan rez, postojala bi ivica <math>(u,v)</math> takva da <math>u \in S</math>, <math>v \in T</math> i <math>c(u,v)-f(u,v) > 0</math>. Ali onda <math>\mathrm{visina}(u)</math> nikada ne bi bila veća od <math>\mathrm{visina}(v)+1</math>, što je kontradiktorno tome da je <math>\mathrm{visina}(u) > k</math> i <math>\mathrm{visina}(v) < k</math>.

== Reference ==

* {{Cite book| ref=harv|last=Cormen|first=Thomas H.|authorlink =Thomas H. Cormen| author2 =[[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]|title=[[Introduction to Algorithms]]|location=|publisher=Second Edition. MIT Press and McGraw–Hill|year=2001|isbn=978-0-262-03293-3|pages=}} Section 26.4: Push–relabel algorithms, and section 26.5: The relabel-to-front-algorithm.

* [[Andrew V. Goldberg]], [[Robert E. Tarjan]]. [http://doi.acm.org/10.1145/12130.12144 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. {{page|year=1986|isbn=978-0-89791-193-1|pages}}

{{normativna kontrola}}

{{СОРТИРАЊЕ:Пуш-релабел алгоритам максималног протока графа}}
[[Категорија:Графовски алгоритми]]