Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 00:36, 14 April 2014

Revision as of 02:20, 18 April 2014

Line 1:

In [[mathematical optimization]], the '''push-relabelpush–relabel algorithm''' (alternatively, '''preflow-pushpreflow–push algorithm''') is an algorithm for computing [[maximum flow]]s. The name "push-relabelpush–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring vertices using ''push'' operations under the guidance of an admissible network maintained by ''relabel'' operations. In comparison, the [[Ford–Fulkerson algorithm]] performs global augmentations that send flow following paths from the source all the way to the sink.<ref name="clrs26"/>

The push-relabelpush–relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a [[strongly polynomial]] {{nowrap|''O''(''V''²''E'')}} time complexity, which is asymptotically more efficient than the {{nowrap|''O''(''VE''²)}} [[Edmonds–Karp algorithm]].<ref name="goldberg86"/> Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label vertex selection rule has {{nowrap|''O''(''V''²{{sqrt|''E''}})}} time complexity and is generally regarded as the benchmark for maximum flow algorithms.<ref name="ahuja97"/><ref name="goldberg08"/> Subcubic {{nowrap|''O''(''VE''&#x200a;log&#x200a;(''V''²/''E''))}} time complexity can be achieved using [[Link-cut tree|dynamic trees]], although in practice it is less efficient.<ref name="goldberg86"/>

The push-relabelpush–relabel algorithm has been extended to compute [[minimum cost flow]]s.<ref name="goldberg97"/> The idea of distance labels has led to a more efficient augmenting path algorithm, which in turn can be incorporated back into the push-relabelpush–relabel algorithm to create a variant with even higher empirical performance.<ref name="goldberg08"/><ref name="ahuja91"/>

==Concepts==

Line 19:

::{{nowrap|∑_{''v''&#x200a;∈&#x200a;''V''} ''f''(''v'', ''u'') {{=}} 0&emsp;∀''u'' ∈ ''V'' \ {''s'', ''t''}}}

The push-relabelpush–relabel algorithm introduces the concept of ''preflows''. A preflow is a function with a definition almost identical to that of a flow except that it relaxes the flow conservation condition. Instead of requiring strict flow balance at vertices other than ''s'' and ''t'', it allows them to carry positive excesses. Put symbolically:

:;Nonnegative excesses:

Line 28:

For each {{nowrap|(''u'', ''v'') ∈ ''V'' × ''V''}}, denote its ''residual capacity'' by {{nowrap|''c_f''(''u'', ''v'') {{=}} ''c''(''u'', ''v'') − ''f''(''u'', ''v'')}}. The residual network of ''G'' with respect to a preflow ''f'' is defined as {{nowrap|''G_f''(''V'', ''E_f'')}} where {{nowrap|''E_f'' {{=}} {(''u'', ''v'') {{!}} ''u'', ''v'' ∈ ''V'' ∧ ''c_f''(''u'', ''v'') > 0}}}. If there is no path from any active vertex to ''t'' in {{nowrap|''G_f''}}, the preflow is called ''maximum''. In a maximum preflow, {{nowrap|''e''(''t'')}} is equal to the value of a maximum flow; if ''T'' is the set of vertices from which ''t'' is reachable in {{nowrap|''G_f''}}, and {{nowrap|''S'' {{=}} ''V'' \ ''T''}}, then {{nowrap|(''S'', ''T'')}} is a [[Max-flow min-cut theorem|minimum ''s''-''t'' cut]].

The push-relabelpush–relabel algorithm makes use of distance labels, or ''heights'', of the vertices denoted by {{nowrap|''h''(''u'')}}. For each vertex {{nowrap|''u'' ∈ ''V'' \ {''s'', ''t''}}}, {{nowrap|''h''(''u'')}} is a nonnegative integer satisfying

:;Valid labeling

Line 66:

To see that a relabel operation on vertex ''u'' preserves the validity of {{nowrap|''h''(''u'')}}, notice that this is trivially guaranteed by definition for the out-edges of ''u'' in {{nowrap|''G_f''}}. For the in-edges of ''u'' in the {{nowrap|''G_f''}}, the increased {{nowrap|''h''(''u'')}} can only satisfy the constraints less tightly, not violate them.

==The generic push-relabelpush–relabel algorithm==

===Description===

Line 73:

After initialization, the algorithm repeatedly executes an applicable push or relabel operation until no such operations apply, at which point the preflow has been converted into a maximum flow.

generic-push-relabelpush–relabel(G(V, E), s, t):

create a preflow f that saturates all out-edges of s

let h[u] = 0 ∀v ∈ V

Line 90:

==Practical implementations==

While the generic push-relabelpush–relabel algorithm has {{nowrap|''O''(''V''²''E'')}} time complexity, efficient implementations achieve {{nowrap|''O''(''V''³)}} or lower time complexity by enforcing appropriate rules in selecting applicable push and relabel operations. The empirical performance can be further improved by heuristics.

==="Current-edge" data structure and discharge operation===

Line 109:

===Active vertex selection rules===

Definition of the discharge operation reduces the push-relabelpush–relabel algorithm to repeatedly selecting an active node to discharge. Depending on the selection rule, the algorithm exhibits different time complexities. For the sake of brevity, we ignore ''s'' and ''t'' when referring to the vertices in the following discussion.

====FIFO selection rule====

The [[FIFO]] push-relabelpush–relabel algorithm<ref name="goldberg86"/> organizes the active vertices into a queue. The initial active nodes can be inserted in arbitrary order. The algorithm always removes the vertex at the front of the queue for discharging. Whenever an inactive vertex is becomes active, it is appended to the back of the queue.

The algorithm has {{nowrap|''O''(''V''³)}} time complexity.

====Relabel-to-front selection rule====

The relabel-to-front push-relabelpush–relabel algorithm<ref name="clrs26"/> organizes all vertices into a linked list and maintains the invariant that the list is [[Topological sorting|topologically sorted]] with respect to the admissible network. The algorithm scans the list from front to back and performs a discharge operation on the current vertex if it is active. If the node is relabeled, it is moved to the front of the list, and the scan is restarted from the front.

The algorithm also has {{nowrap|''O''(''V''³)}} time complexity.

====Highest label selection rule====

The highest-label push-relabelpush–relabel algorithm<ref name="cheriyan88"/> organizes all vertices into buckets indexed by their heights. The algorithm always selects an active vertex with the largest height to discharge.

The algorithm has {{nowrap|''O''(''V''²{{sqrt|''E''}})}} time complexity. If the lowest-label selection rule is used instead, the time complexity becomes {{nowrap|''O''(''V''²''E'')}}.<ref name="ahuja97"/>

===Implementation techniques===

Although in the description of the generic push-relabelpush–relabel algorithm above, {{nowrap|''h''(''u'')}} is set to zero for each vertex ''u'' other than ''s'' and ''t'' at the beginning, it is preferable to perform a backward [[breadth-first search]] from ''t'' to compute the exact heights.<ref name="goldberg86"/>

The algorithm is typically separated into two phases. Phase one computes a maximum preflow by discharging only active vertices whose heights are below ''n''. Phase two converts the maximum preflow into a maximum flow by returning excess flow that cannot reach ''t'' to ''s''. It can be shown that phase two has {{nowrap|''O''(''VE'')}} time complexity regardless of the order of push and relabel operations and is therefore dominated by phase one. Alternatively, it can be implemented using flow decomposition.<ref name="amo93"/>

Line 138:

#include <stdlib.h>

#include <stdio.h>

#define NODES 6

#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

#define INFINITE 10000000

void push(const int * const * C, int ** F, int *excess, int u, int v) {

int send = MIN(excess[u], C[u][v] - F[u][v]);

Line 150:

excess[v] += send;

}

void relabel(const int * const * C, const int * const * F, int *height, int u) {

int v;

Line 161:

}

};

void discharge(const int * const * C, int ** F, int *excess, int *height, int *seen, int u) {

while (excess[u] > 0) {

Line 167:

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

Line 177:

}

}

void moveToFront(int i, int *A) {

int temp = A[i];

Line 186:

A[0] = temp;

}

int pushRelabel(const int * const * 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)) {

Line 202:

}

}

height[source] = NODES;

excess[source] = INFINITE;

for (i = 0; i < NODES; i++)

push(C, F, excess, source, i);

p = 0;

while (p < NODES - 2) {

Line 223:

for (i = 0; i < NODES; i++)

maxflow += F[source][i];

free(list);

free(seen);

free(height);

free(excess);

return maxflow;

}

void printMatrix(const int * const * M) {

int i,j;

Line 241:

}

}

int main(void) {

int **flow, **capacities, i;

Line 250:

capacities[i] = (int *) calloc(NODES, sizeof(int));

}

//Sample graph

capacities[0][1] = 2;

Line 260:

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;

}