Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 15:36, 10 April 2014

Revision as of 17:59, 10 April 2014

Line 5:

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

==OverviewConcepts==

===Definitions and notations===

{{seealsomain|Flow network}}

Consider a flow network {{nowrap|''G''(''V'', ''E'')}} with a pair of distinct vertices ''s'' and ''t'' designated as the source and the sink, respectively. For each edge {{nowrap|(''u'', ''v'') ∈ ''E''}}, {{nowrap|''c''(''u'', ''v'') ≥ 0}} denotes its capacity; if {{nowrap|(''u'', ''v'') ∉ ''E''}}, we assume that {{nowrap|''c''(''u'', ''v'') {{=}} 0}}. A flow on ''G'' is a function {{nowrap|''f'': ''V'' × ''V'' → '''R'''}} satisfying the following conditions:

In a flow network, flow going into a vertex must equal flow going out of a vertex (with

the exception of the source node and the sink node, ''s'' and ''t'' respectively). Thus we cannot

accumulate flow anywhere in the network.

:;Capacity constraints

The Preflow algorithm relaxes this constraint while it determines the maximum flow of the network, allowing a vertex to have more flow coming

::{{nowrap|''f''(''u'', ''v'') ≤ ''c''(''u'', ''v'')&emsp;∀''u'', ''v'' ∈ ''V''}}

into it than going out. This is called the ''excess'' flow of a vertex, or ''preflow''. Any vertex with excess flow

:;Skew symmetry

is known as an ''active vertex''. Excess flow can only be moved down [[residual graph|residual edges]] of the [[residual graph]]. Flow is ''pushed'' through the network by adjusting the ''height'' of the vertices. Height is updated and maintained via the concept of a ''valid labelling''. Stated precisely this labelling is <math>h(u) \leq h(v) +1</math>, where ''h(u)'' is height of vertex ''u'', for each residual edge incident to ''u''. In other words a vertex cannot be more than 1 higher from its neighbour on a residual edge (there is no bound on how much lower it can be).

::{{nowrap|''f''(''u'', ''v'') {{=}} −''f''(''v'', ''u'')&emsp;∀''u'', ''v'' ∈ ''V''}}

Flow always goes from a higher vertex to a lower vertex.

:;Flow conservation

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

The push-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:

To ''push'' preflow is to move it down a residual edge from a vertex ''u'' to a vertex ''v'', where <math>h(u) = h(v)+1 </math>. It is called a ''saturating push'' if all of the capacity of the residual edge was used (and thus the edge ''(u,v)'' is removed from the residual graph). It is called a ''non-saturating push'' if after the push there is still available capacity on edge ''(u,v)''. Note that a non-saturating push will deplete all the excess flow from vertex ''u''. A saturating push may deplete ''u'', but not necessarily.

:;Nonnegative excesses:

{{seealso|Flow network}}

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

{{nowrap|''e''(''s'')}} is assumed to be infinite. A vertex ''u'' is called ''active'' if {{nowrap|''e''(''u'') > 0}}.

The push-relabel algorithm finds maximum flow on a [[flow network]]. There are three conditions for a flow network:

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, the excess of ''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]].

:{|

| '''Capacity constraints''': || <math>\ f(u,v) \le c(u,v)</math>. The flow along an edge cannot exceed its capacity.

|-

| '''Skew symmetry''': || <math>\ f(u,v) = - f(v,u)</math>. The net flow from <math>\ u</math> to <math>\ v</math> must be the opposite of the net flow from <math>\ v</math> to <math>\ u</math> (see example).

|-

| '''Flow conservation''': || <math>\ \sum_{w \in V} f(u,w) = 0</math>, unless <math>\ u=s</math> or <math>\ u=t</math>. The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.

|}

The push-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

The '''preflow''' algorithm observes the first two of the conditions of flow networks, plus a relaxed third condition for the duration of the algorithm (the algorithm finishes once all the excess is gone from the graph, at which point we have a legal flow, and the '''Flow conservation''' constraint is again observed):

:;Valid labeling

:{|

::{{nowrap|''h''(''u'') ≤ ''h''(''v'') + 1&emsp;∀(''u'', ''v'') ∈ ''E_f''}}

| '''Non-negativity constraint: ''' <math>\ \sum_{w \in V} f(u, w) = \mathrm{excess}(u) \geq 0</math> for all nodes <math>u \neq s</math>. More flow enters a node than exits.

|}

The heights of ''s'' and ''t'' are fixed at {{nowrap|{{!}}''V''{{!}}}} and 0, respectively.

Given a flow network <math>G(V,E)</math> with capacity from node ''u'' to node ''v'' given as <math>c(u,v)</math>, and the flow across ''u'' and ''v'' given as <math> f(u,v) </math>, source ''s'' and sink ''t'', we want to find the maximum amount of flow you can send from ''s'' to ''t'' through the network. Some key concepts used in the algorithm are:

:{|

| '''residual edge''': ||If available capacity <math>c(u,v) - f(u,v)>0</math> we have a residual edge <math>r(u,v)</math>.

|-

| '''residual edge (Alternate)''': ||<math>r(v,u) = - f (u,v)</math>. We can push flow back along an edge.

|-

| '''residual graph''': ||The set of all residual edges forms the residual graph.

|-

| '''legal labelling''': ||For each residual edge <math>(u,v), \mathrm{height}(u) \leq \mathrm{height}(v) +1 </math>. We only ''push'' from ''u'' to ''v'' if <math>\mathrm{height}(u) = \mathrm{height}(v)+1</math>.

|-

| '''excess(u)''':|| Sum of flow to and from ''u''.

|-

| '''height(u)''':|| Each vertex is assigned a height value. For values <math>\leq |V|</math>, the height serves as an estimate of the distance to the sink node ''t''. For values <math> > |V|</math>, the height is an estimate of the distance back to the sink ''s''.

|}

The height of a vertex is a lower bound of its unweighted distance in the residual network to ''t'' or to ''s'' if it has been separated from ''t''. An edge {{nowrap|(''u'', ''v'') ∈ ''E_f''}} is called ''admissible'' if {{nowrap|''h''(''u'') {{=}} ''h''(''v'') + 1}}. The network {{nowrap|''G̃_f''(''V'', ''Ẽ_f'')}} where {{nowrap|''Ẽ_f'' {{=}} {(''u'', ''v'') {{!}} (''u'', ''v'') ∈ ''E_f'' ∧ ''h''(''u'') {{=}} ''h''(''v'') + 1}}} is called the ''admissible network''. The admissible network is acyclic.

We observe that the longest possible path from ''s'' to ''t'' is <math>|V|</math> nodes long. Therefore it must be possible to assign ''height'' to the nodes such that for any legal flow, <math>\mathrm{height}(s) = |V|</math> and <math>\mathrm{height}(t) = 0</math>, and if there is a positive flow from ''u'' to ''v'', <math>\mathrm{height}(u) > \mathrm{height}(v)</math>. As we adjust the height of the nodes, the flow goes through the network as water through a landscape. Differing from algorithms such as [[Ford–Fulkerson algorithm|Ford–Fulkerson]], the flow through the network is not necessarily a legal flow throughout the execution of the algorithm.

===Operations===

====Push====

The push operation applies on an admissible out-edge {{nowrap|(''u'', ''v'')}} an active vertex ''u'' in {{nowrap|''G_f''}}. It moves {{nowrap|min{''e''(''u''), ''c_f''(''u'', ''v'')}}} units of flow from ''u'' to ''v''.

push(u, v):

assert e[u] > 0 and h[u] == h[v] + 1

Δ = min(e[u], c[u][v] - f[u][v])

f[u][v] += Δ

f[v][u] -= Δ

e[u] -= Δ

e[v] += Δ

A push operation that causes {{nowrap|''f''(''u'', ''v'')}} to reach {{nowrap|''c''(''u'', ''v'')}} is called a ''saturating'' push; otherwise, it is called an ''unsaturating'' push. After an unsaturating push, {{nowrap|''e''(''u'') {{=}} 0}}.

====Relabel====

The relabel operation applies on an active vertex ''u'' without any admissible out-edges in {{nowrap|''G_f''}}. It modifies {{nowrap|''h''(''u'')}} to the minimum value such that an admissible out-edge is created. Note that this always increases {{nowrap|''h''(''u'')}}.

relabel(u):

assert e[u] > 0 and h[u] <= h[v] ∀v such that f[u][v] < c[u][v]

h[u] = min(h[v] ∀v such that f[u][v] < c[u][v]) + 1

==Push-relabel Algorithm==