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 $O(V^{2}E)$ , dok implementacija korišćenjem FIFO (prvi unutra - prvi napolje) pravila pronalaženja najviše tačke ima složenost $O(V^{3})$ . Pravilo pronalaženja najviše aktivne tačke daje složenost $O(V^{2}{\sqrt {E}})$ , a implementacija preko Sletorovog i Tarjanovog dinamičkog stabla ima složenost $O(VE\log(V^{2}/E))$ . Asimptotski, algoritam je efikasniji od Edmonds-Karpovog algoritma koji ima složenost $O(VE^{2})$ .

Algoritam

Data je mreža protoka $G(V,E)$ , tako da je kapacitet iz čvora u, do čvora v zadat sa $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:

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

Nakon svakog koraka algoritma važi:

$\ f(u,v)\leq c(u,v)$ . Protok između u i v, ne prekoračuje kapacitet.
$\ f(u,v)=-f(v,u)$ . Održavamo protok mreže.
$\ \sum _{v}f(v,u)=\mathrm {visak} (u)\geq 0$ za svaki čvor $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 $|V|$ čvorova. Dakle, mora biti moguće dodeliti visinu takvim čvorovima za svaki pravilan protok. $\mathrm {visina} (s)=|V|$ i $\mathrm {height} (t)=0$ , i ako postoji pozitivan protok od u do v, $\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 $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 $|V|-1$ , a $\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:

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

Šaljemo određenu količinu toka jednaku $\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:

$\mathrm {visak} (u)>0$ . Mora da postoji razlog za ovu operaciju.
$\mathrm {visina} (u)\leq \mathrm {visina} (v)$ za svako v takvo da je $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 $\mathrm {visina} (u)$ tako da ona bude najniža vrednost takva da je $\mathrm {visina} (u)>\mathrm {visina} (v)$ za neko v gde je $c(u,v)-f(u,v)>0$ .

Push-relabel algoritam

Push-relabel algoritmi generalno imaju ovakav raspored:

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 $O(V^{2}E)$ .

Pražnjenje

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

Sve dok je $\mathrm {visak} (u)>0$ $\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:

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:
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 $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 $k$ takvo da ni za jedan čvor $u$ ne važi, $\mathrm {visina} (u)=k$ , možemo podesiti $\mathrm {visina} (u)=\max(\mathrm {visina} (u),\mathrm {visina} (s)+1)$ za sve čvorove, osim za $s$ za koji je $\mathrm {visina} (u)>k$ . Ovo je zbog toga što svako takvo $k$ predstavlja minimalan rez grafa , i nijedan deo toka neće ići iz čvorova $S=\{u\mid \mathrm {visina} (u)>k\}$ u čvorove $T=\{v\mid \mathrm {visina} (v)<k\}$ . Ako $(S,T)$ nije bio minimalan rez, postojala bi ivica $(u,v)$ takva da $u\in S$ , $v\in T$ i $c(u,v)-f(u,v)>0$ . Ali onda $\mathrm {visina} (u)$ nikada ne bi bila veća od $\mathrm {visina} (v)+1$ , što je kontradiktorno tome da je $\mathrm {visina} (u)>k$ i $\mathrm {visina} (v)<k$ .