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(V E \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:

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

Pražnjenje[уреди]

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

  1. Sve dok je \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 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.

Reference[уреди]