From 795f5b739c8b22f256bbc089ac35a0353defa7f5 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Mon, 5 May 2014 09:57:42 +0200 Subject: [PATCH] More push-relabel --- flow.tex | 141 ++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 104 insertions(+), 37 deletions(-) diff --git a/flow.tex b/flow.tex index 26c2674..b706d4d 100644 --- a/flow.tex +++ b/flow.tex @@ -186,14 +186,13 @@ the source node until the sink node is found, as this will yield the shortest possible augmenting path. This version of the algorithm is called Edmonds-Karp and has a running time of $O(\abs{V}\abs{E}^2)$. See \cite{cormen2009introduction} for a description of the breadth-first -search, and a formal proof of the running time of Edmonds-Karp. +search, and a formal proof of the running time of the algorithm. \subsubsection{Dinitz'} \fixme{I did implement this, but it is maybe not very central to the project/report, since I use an other algorithm in the final implementation. Maybe a comparison would be nice though.} -\subsubsection{Dinic's algorithm} The «best» of the augmenting-path algorithms (citation needed). Makes a level graph with BFS, and finds a blocking flow through this graph which only goes from nodes with one label to nodes with greater labels. When @@ -208,13 +207,13 @@ maximum valid flow when the algorithm is finished. \subsubsection{Preflow} Instead of maintaining a valid flow, we introduce the concept of a -\emph{preflow}, in which we relax the flow concervation constraint from -earlier a bit. For a preflow $f$, the flow must always be less than the +\emph{preflow}, as we relax the flow concervation constraint from +earlier. For a preflow $f$, the flow must always be less than the capacity, as before, but we allow positive excess in all vertices except the source and the sink. The flow conservation constraint from before then becomes \begin{description} - \item[Relaxed flow conservation:] For all $u \in V - \{s, t\}$ + \item[Preflow conservation:] For all $u \in V - \{s, t\}$ \begin{equation} \sum_{v \in V} f(v, u) \geq \sum_{v \in V} f(u, v), \end{equation} @@ -223,75 +222,143 @@ then becomes node. \end{description} -For all vertices $u \in V$ we define the excess function +\fixme{Vertex vs.\ node.} + +\fixme{Describe saturated in the $G_f$ section. And $N$.} + +For all vertices $u \in V$ we define the excess \begin{equation} e(u) = \sum_{v \in V} f(v, u) - \sum_{v \in V} f(u, v), \end{equation} which represents the amount of flow which \emph{disappears} in node $u$. -Following from the constraint above $e(u) \geq 0$ for all vertices -except the source and the sink. +Equivalent to the preflow conservation constraint is stating that $e(u) +\geq 0$ for all vertices except the source and the sink. -The idea of the algorithm is to maintain a height distribution among the +The idea of the algorithm is to maintain a height map of the nodes of the network and then ``lift'' the source node to let as many units as possible flow through the edges of the network towards the sink. When a maximum preflow is reached, there will normally be excess flow in some of the vertices, which has to be pushed back towards the -source in order to obtained a valid flow. - -The algorithm is based on two basic vertex operations, the \emph{push} -operation, which attempts to redistribute the excess of a vertex to its -neighbors, and the \emph{relabel} operation, which recalculates the -height of a vertex depending on the height of its neighbors. - -\subsubsection{The push operation} +source in order to obtain a valid flow. + +The height map $d : V \to \mathbb{N}$ is also often called a distance +labeling and it satisfies $d(t) = 0$ and for every edge $(u, v)$ in the +residual network, i.e.\ every edge with $c_f(u, v) > 0$, the labeling +satisfies $d(u) \leq d(v) + 1$. For every vertex $u$ for which there is +a path through the residual network to the sink, $d(u)$ will be a lower +bound on the length of such a path. + +A vertex $u$ is \emph{active} if $u \in V - \{s,t\}$, it has positive +excess ($e(u) > 0$) and $d(u) < N$. These are the nodes we want to +operate on to increase the preflow. + +The algorithm performs two basic operations, the \emph{push} and +\emph{relabel} operations, while always maintaining a valid preflow $f$ +and distance labeling $d$. + +\subsubsection{The push procedure} + +The push operation moves excess flow from an active vertex along an edge +$(u, v) \in E_f$ such that $d(u) = d(v) + 1$, i.e.\ to a vertex with a +smaller distance label. We call such edges \emph{admissible}. See +Algorithm \ref{alg:push} for a pseudocode implementation of the push +operation. Assuming that $f$ is a valid preflow, it is easy to verify +that $f$ remains a valid preflow after running the push procedure on +some admissible edge $(u, v)$. The capacity constraint is fulfilled +since we at most increase the flow along $(u, v)$ with the residual +capacity $c_f(u,v)$. The preflow constraint is fulfilled since the +excess $e$ increases for $v$, remains non-negative for $u$ and remains +the same for all other vertices. + +The distance labels are not changed during the push procedure, however, +the residual network is changed. The edge $(u, v)$ might disappear, and +an edge $(v, u)$ will surely appear if it does not already exist. Assume +that $d$ is a valid labeling. When starting the push procedure we have +$d(u) = d(v) + 1$, so we also have the following +\begin{align} + d(u) &\leq d(v) + 1 \\ + d(v) &\leq d(u) + 1, +\end{align} +and $d$ remains a valid labeling. \fixme{not very clear} + +\fixme{Change height $h$ to distance $d$.} + +\fixme{Operation < procedure.} \begin{algorithm} \begin{algorithmic} - \Function{Push}{$u$} - \ForAll{$v$ neighbour of $u$} - \If{$res(u, v) > 0$} - \State $f \gets \min(res(u, v), excess[u])$ - \State $flow(u, v) \mathrel{+}= f$ - \State $flow(v, u) \mathrel{-}= f$ - \State $excess[u] \mathrel{-}= f$ - \State $excess[v] \mathrel{+}= f$ - \EndIf - \EndFor + \Function{Push}{$u$, $v$} + \State $f_{aug} \gets \min(c_f(u, v), e(u))$ + \State $f(u, v) \mathrel{+}= f_{aug}$ + \State $e(u) \mathrel{-}= f_{aug}$ + \State $e(v) \mathrel{+}= f_{aug}$ \EndFunction \end{algorithmic} \caption{\sf The push procedure of the Push-Relabel algorithm} +\label{alg:push} \end{algorithm} -\subsubsection{The relabel operation} - +\subsubsection{The relabel procedure} +The relabel procedure is our tool for changing the distance labeling of +our vertices. It changes the label of a vertex to the greatest possible +value, which is one more than the lowest label among its neighbors in +the residual graph. See Algorithm \ref{alg:relabel} for a pseudocode +implementation. \begin{algorithm} \begin{algorithmic} \Function{Relabel}{$u$} - \If{$u$ is only node at its height} - \Call{Gap}{$u$} - \Else - \State $height[u] \gets min(height[v] \, \forall v \in - neighbors[u] : res(u, v) > 0) + 1$ - \EndIf +% \If{$u$ is only node at its height} +% \Call{Gap}{$u$} +% \Else + \State $d(u) \gets min(d(v) \; \forall v \in + neighbors(u) : c_f(u, v) > 0) + 1$ +% \EndIf \EndFunction \end{algorithmic} \caption{\sf The relabel procedure of the Push-Relabel algorithm} +\label{alg:relabel} \end{algorithm} +If $d$ was a valid labeling before running the relabel procedure, then +we still have $d(u) \leq d(v) + 1$ for all neighbors $v$ of $u$ in the +residual graph, and $d$ remains a valid labeling. + \subsubsection{Putting it all together} +The idea is now to initialize a valid preflow and distance labeling, and +then run the push and relabel procedures when possible until a maximum +preflow is obtained. + +\begin{algorithm} +\begin{algorithmic} + \Function{Discharge}{$u$} + \ForAll{$v$ neighbor of $u$} + \If{$c_f(u, v) > 0$ and $h(u) = h(v) + 1$} + \Call{Push}{$u$, $v$} + \EndIf + \EndFor + + \If{$e(u) > 0$} + \Call{Relabel}{$u$} + \EndIf + \EndFunction +\end{algorithmic} +\caption{\sf The discharge procedure of the Push-Relabel algorithm} +\label{alg:discharge} +\end{algorithm} \subsubsection{Heuristics} \begin{algorithm} \begin{algorithmic} \Function{Gap}{$u$} - \State $k \gets height[u]$ + \State $k \gets h(u)$ \ForAll{$v$ with height $\geq k$} - \State $height[v] \gets N$ + \State $h(v) \gets N$ \EndFor \EndFunction \end{algorithmic} \caption{\sf The gap procedure of the Push-Relabel algorithm} +\label{alg:gap} \end{algorithm} The nodes are allowed to have a positive excess but we still follow the -- 2.47.3