Пусх-релабел алгоритам максималног протока графа

Пусх-релабел алгоритам је један од најефикаснијих алгоритама за израчунавање максималног протока. У општем случају, алгоритам има временску сложеност $O(V^{2}E)$, док имплементација коришћењем ФИФО (први унутра - први напоље) правила проналажења највише тачке има сложеност $O(V^{3})$. Правило проналажења највише активне тачке даје сложеност $O(V^{2}{\sqrt {E}})$, а имплементација преко Слеторовог и Тарјановог динамичког стабла има сложеност $O(VE\log(V^{2}/E))$. Асимптотски, алгоритам је ефикаснији од Едмондс-Карповог алгоритма који има сложеност $O(VE^{2})$.

Алгоритам

Дата је мрежа протока $G(V,E)$, тако да је капацитет из чвора у, до чвора в задат са $c(u,v)$, са извором с и понором т. Желимо да пронађемо максимални проток који се може послати од с до т, кроз задату мрежу. На чворове се примењу две врсте операција, пусх и релабел. Током алгоритма одржавамо:

• $f(u,v)$. Тренутни проток од у до в. Доступан капацитет је $c(u,v)-f(u,v)$.
• $\mathrm {visina} (u)$. Операцију пусх од у до в вршимо само када је $\mathrm {visina} (u)$ > $\mathrm {visina} (v)$. За свако у, $\mathrm {visina} (u)$ је неозначен цео број.
• $\mathrm {visak} (u)$. Збир протока од, и до, чвора у.

Након сваког корака алгоритма важи:

• $\ f(u,v)\leq c(u,v)$. Проток између у и в, не прекорачује капацитет.
• $\ f(u,v)=-f(v,u)$. Одржавамо проток мреже.
• $\ \sum _{v}f(v,u)=\mathrm {visak} (u)\geq 0$ за сваки чвор $u\neq s$. Само извор може да производи проток.

Приметимо да је последњи услов мање ригорозан од одговарајућег услова за правилан проток у обичној мрежи протока.

Запажамо да је најдужи могући пут од с до т дугачак $|V|$ чворова. Дакле, мора бити могуће доделити висину таквим чворовима за сваки правилан проток. $\mathrm {visina} (s)=|V|$ и $\mathrm {height} (t)=0$, и ако постоји позитиван проток од у до в, $\mathrm {height} (u)>\mathrm {height} (v)$. Како подешавамо висину чворова, ток тече кроз мрежу као вода кроз пејзаж. За разлику од алгоритама као што је Форд-Фулкерсонов, проток кроз мрежу није обавезно и правилан проток у току извршавања алгоритма.

Укратко, висине чворова (изузев с и т) су подешене, и ток је послат између чворова, док максималан могући проток не стигне до т. Тада настављамо да повећавамо висину интерних чворова док се сав ток који је ушао у мрежу, али није достигао т, не врати до с. Чвор може достићи висину $2|V|-1$ пре него што је ово завршено, тако да је најдужи могући пут назад до с, не рачунајући т, једнак $|V|-1$, а $\mathrm {visina} (s)=|V|$. Висина чвора т се чува на 0.

Пусх

Пусх од у до в значи слање дела вишка протока у у, до чвора в. Ови услови морају бити испуњени да би пусх могао да се одвија:

• $\mathrm {visak} (u)>0$. Више тока улази у чвор, него што из њега излази, до сад.
• $c(u,v)-f(u,v)>0$. Расположив одређени капацитет из у ка в.
• $\mathrm {visina} (u)>\mathrm {visina} (v)$. Може се слати само у нижи чвор.

Шаљемо одређену количину тока једнаку $\min(\mathrm {visak} (u),c(u,v)-f(u,v))$.

Релабел

Операција релабел на чвору у је повећавање висине тог чвора док она није већа од најмање једног чвора чији капацитет није испуњен. Услови за ову операцију:

• $\mathrm {visak} (u)>0$. Мора да постоји разлог за ову операцију.
• $\mathrm {visina} (u)\leq \mathrm {visina} (v)$ за свако в такво да је $c(u,v)-f(u,v)>0$. Једини чворови који имају довољан капацитет су виши.

Када вршимо ову операцију на у, подешавамо $\mathrm {visina} (u)$ тако да она буде најнижа вредност таква да је $\mathrm {visina} (u)>\mathrm {visina} (v)$ за неко в где је $c(u,v)-f(u,v)>0$.

Пусх-релабел алгоритам

Пусх-релабел алгоритми генерално имају овакав распоред:

1. Све док се може извршити пусх или релабел операција
   1. Изврши легалан пусх, или
   2. Изврши легалан релабел

Сложеност ових алгоритама је генерално $O(V^{2}E)$.

Пражњење

У релабел-то-фронт алгоритму, пражњење на чвору у је следећа операција:

1. Све док је $\mathrm {visak} (u)>0$:
   1. Ако нису све комшије испробане од последње релабел операције:
      1. Покушај да извршиш операцију пусх на неком од неиспробаних комшија.
   2. Иначе: Изврши операцију релабел над у

Ово захтева да је за сваки чвор познато који чворови су испробани од последњег релабел-а.

Релабел-то-фронт алгоритам, ФИФО имплементација

У релабел-то-фронт алгоритму, ред операција пусх и релабел је задат на следећи начин:

1. Пошаљи што је могуће већи део тока из с.
2. Сагради листу свих темена осим с и т.
3. Све док нисмо прошли кроз целу листу:
   1. Испразни тренутно највише теме
   2. Ако се висина највише тачке изменила:
      1. Помери тренутну највишу тачку на почетак листе
      2. Понови пролазак кроз листу из почетка

Сложеност овог алгоритма је $O(V^{3})$.

Пример имплементације у 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;
	}

Пример имплементације у Пyтхон-у:

  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])

Приметимо да горња имплементација није превише ефикасна. Спорија је од Едмондс-Карповог алгоритма чак и за густе графове. Да бисмо га убрзали, можемо урадити бар две ствари:

• Направити листу комшија за сваки чвор, и нека индекс posecen[u] буде итератор за овај чвор, уместо да обилазимо све чворове.
• Уколико постоји $k$ такво да ни за један чвор $u$ не важи, $\mathrm {visina} (u)=k$, можемо подесити $\mathrm {visina} (u)=\max(\mathrm {visina} (u),\mathrm {visina} (s)+1)$ за све чворове, осим за $s$ за који је $\mathrm {visina} (u)>k$. Ово је због тога што свако такво $k$ представља минималан рез графа , и ниједан део тока неће ићи из чворова $S=\{u\mid \mathrm {visina} (u)>k\}$ у чворове $T=\{v\mid \mathrm {visina} (v)<k\}$. Ако $(S,T)$ није био минималан рез, постојала би ивица $(u,v)$ таква да $u\in S$, $v\in T$ и $c(u,v)-f(u,v)>0$. Али онда $\mathrm {visina} (u)$ никада не би била већа од $\mathrm {visina} (v)+1$, што је контрадикторно томе да је $\mathrm {visina} (u)>k$ и $\mathrm {visina} (v)<k$.

Референце

• Цормен, Тхомас Х.; Цхарлес Е. Леисерсон, Роналд L. Ривест, анд Цлиффорд Стеин (2001). Интродуцтион то Алгоритхмс. Сецонд Едитион. МИТ Пресс анд МцГраw–Хилл. ИСБН 978-0-262-03293-3. ЦС1 одржавање: Вишеструка имена: списак аутора (веза) Сецтион 26.4: Пусх–релабел алгоритхмс, анд сецтион 26.5: Тхе релабел-то-фронт-алгоритхм.

• Андреw V. Голдберг, Роберт Е. Тарјан. А неw аппроацх то тхе маxимум флоw проблем. Аннуал АЦМ Сyмпосиум он Тхеорy оф Цомпутинг, Процеедингс оф тхе еигхтеентх аннуал АЦМ сyмпосиум он Тхеорy оф цомпутинг, 136–146. 1986. ISBN 978-0-89791-193-1.