Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 21:17, 10 April 2014

Revision as of 22:40, 10 April 2014

Line 82:

It can be shown that the algorithm executes {{nowrap|''O''(''V''²)}} relabels, {{nowrap|''O''(''VE'')}} saturating pushes and {{nowrap|''O''(''V''²''E'')}} nonsaturating pushes.<ref name="clrs26"/> Data structures can be designed to pick an applicable operation in {{nowrap|''O''(1)}} time. Therefore, the time complexity of the algorithm is {{nowrap|''O''(''V''²''E'')}}.

==Practical implementations==

==Relabel-to-Front Algorithm==

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

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

The Relabel-to-Front algorithm is a variant of the Push-Relabel algorithm that improves the

The "current-edge" data structure is a mechanism for visiting the in- and out-neighbors of a vertex in the flow network in a static circular order. If a singly linked list of neighbors is created for a vertex, the data structure can be as simple as a pointer into the list that steps through the list and rewinds to the head when it runs off the end.

running time from <math>O(V^2E)</math> to <math>O(V^3)</math>. It does so by executing Push and

Relabel in a specified order. The main difference is we wish to apply Push and Relabel to a single

vertex until its excess is completely spent. This limits the number of ''non-saturating'' pushes that

we make, which is the main bottle-neck of this algorithm.

Based on the "current-edge" data structure, the discharge operation can be defined. A discharge operation applies on an active node and repeatedly pushes flow from the node until it becomes inactive, relabeling it as necessary to create admissible edges.

To do this, we maintain a list of all the vertices in the graph <math> L = V - \{s,t\} </math>, in any

particular order (they will be put in order as the algorithm executes). In addition to this master

list, each vertex maintains a list of its neighbours in the graph, in arbitrary but static order.

These neighbours are the vertices it can potentially push flow to. Then, starting at the first

vertex in the list and moving to each in turn, we ''Discharge'' a vertex <math>u \in L </math> if it is active. If a vertex is relabelled during discharge, it is moved to the front of the list, and we start again at the next vertex (formerly the first vertex). Discharge is detailed below:

discharge(u);:

===Discharge===

while excess(e[u)] > 0:

In ''relabel-to-front'', a ''discharge'' on a node ''u'' is the following:

if current-edge[u] has run off the end of neighbors[u]

relabel(u);

rewind current-edge[u]

else:

current let (u, v) = current.next;-edge[u]

if (u, v) is admissible

push(u, u.currentNeighbourv);

let current-edge[u] point to the next neighbor of u

===Active vertex selection rules===

Function Discharge(u):

Definition of the discharge operation reduces the push-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.

while excess(u) > 0:

if (u.currentNeighbour != NIL):

push(u, u.currentNeighbour);

u.currentNeighbour = u.nextNeighbour;

else:

relabel(u);

u.currentNeighbour = u.headOfNeighbourList; //start again at the beginning of the neighbour list

===Relabel-to-Front=FIFO selection rule====

The [[FIFO]] push-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.

In the ''relabel-to-front'' algorithm we fully discharge each vertex before moving to the next one. The ordering tends to reduce the number of non-saturating pushes we do:

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

Algorithm Relabel-to-Front(G(V,E),s,t):

for each vertex v incident to s:

push(s,v); //note that this will saturate the edges (s,v), since the flow from s is limitless

L = v - {''s'',''t''}; //build a list of all vertices in any order

current = L.head;

while (current != NIL):

old_height = height(u);

discharge(u);

if height(u) > old_height:

Move ''u'' to front of ''L''

current = current.next;

====Relabel-to-Frontfront Algorithmselection rule====

The running time for ''relabel-to-front'' is <math>O(V^3)</math> (proof omitted). Again the bottleneck is non-saturating pushes, but we have reduced the number. Note that after step 1 there is no path from ''s'' to ''t'' in the residual graph.

The relabel-to-front push-relabel algorithm<ref name="clrs26"/> organizes all vertices into a linked list. The nodes can be inserted in arbitrary order. 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-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''^2{{sqrt|''E''}})}} time complexity.

==Sample implementation==