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 , dok implementacija korišćenjem FIFO (prvi unutra - prvi napolje) pravila pronalaženja najviše tačke ima složenost . Pravilo pronalaženja najviše aktivne tačke daje složenost , a implementacija preko Sletorovog i Tarjanovog dinamičkog stabla ima složenost . Asimptotski, algoritam je efikasniji od Edmonds-Karpovog algoritma koji ima složenost .

Algoritam[уреди]

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

  • . Trenutni protok od u do v. Dostupan kapacitet je .
  • . Operaciju push od u do v vršimo samo kada je > . Za svako u, je neoznačen ceo broj.
  • . Zbir protoka od, i do, čvora u.

Nakon svakog koraka algoritma važi:

  • . Protok između u i v, ne prekoračuje kapacitet.
  • . Održavamo protok mreže.
  • za svaki čvor . 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 čvorova. Dakle, mora biti moguće dodeliti visinu takvim čvorovima za svaki pravilan protok. i , i ako postoji pozitivan protok od u do 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 pre nego što je ovo završeno, tako da je najduži mogući put nazad do s, ne računajući t, jednak , a . 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:

  • . Više toka ulazi u čvor, nego što iz njega izlazi, do sad.
  • . Raspoloživ određeni kapacitet iz u ka v.
  • . Može se slati samo u niži čvor.

Šaljemo određenu količinu toka jednaku .

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:

  • . Mora da postoji razlog za ovu operaciju.
  • za svako v takvo da je . Jedini čvorovi koji imaju dovoljan kapacitet su viši.

Kada vršimo ovu operaciju na u, podešavamo tako da ona bude najniža vrednost takva da je za neko v gde je .

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 .

Pražnjenje[уреди]

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

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

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 takvo da ni za jedan čvor ne važi, , možemo podesiti za sve čvorove, osim za za koji je . Ovo je zbog toga što svako takvo predstavlja minimalan rez grafa , i nijedan deo toka neće ići iz čvorova u čvorove . Ako nije bio minimalan rez, postojala bi ivica takva da , i . Ali onda nikada ne bi bila veća od , što je kontradiktorno tome da je i .

Reference[уреди]