\documentstyle{dimacs-l} %%%%%%%%%%%%%%%%% \input{psfig} %%%%%%%%%%%%%%%%% \begin{document} \def\JACM{{J.\ ACM }} \title[IMPLEMENTING A MAXFLOW ALGORITHM]{Implementing a Maximum Flow Algorithm: Experiments with Dynamic Trees} \author[T. BADICS AND E. BOROS]{T. Badics and E. Boros} \address{RUTCOR, Rutgers University, New Brunswick, NJ 08903-5062.} \email{badics@rutcor.rutgers.edu \\ boros@rutcor.rutgers.edu} \subjclass{Primary 90B10; Secondary 68P05, 68-04} \date{August 15, 1992} \thanks{The second author is supported in part by NSF (Grant DMS 89-06870) and AFOSR (Grants 89-0512 and 90-0008).} \maketitle \begin{abstract} This paper contains experimental results with a maximum flow algorithm developed by Cheriyan and Hagerup. Comparison was made to a preflow-push type maxflow implementation, and we examined also the effect of the dynamic trees data structure and several heuristic parameters. \end{abstract} \section{Introduction} In this paper we report on an implementation of a maximum flow algorithm by Cheriyan and Hagerup \cite{CH}. Our aim was to test the behavior of this algorithm in practice, concerning it's good theoretical worst case bound. We were particularly interested in the effect of using theoretically well behaving data structures such as dynamic trees \cite{ST}, and Fibonacci heaps \cite{FH}. We also made comparisons to two preflow-push based algorithm by Goldberg and Tarjan \cite{GT88}, and to an implementation of pushes along several edges without using dynamic trees. In Sections 2. the basic notations and a short description of the Cheriyan--Hagerup algorithm are given. In Section 3. details of the implementation and the used data structures are presented. In Section 4. a summary of the experimental results and a few questions that could be addressed in the future are given. \section{Basic notions and the PLED algorithm} We assume that the reader is familiar with the generic maximum flow algorithm in \cite{GT88} and refer to \cite{GT88} for definitions of the terms {\sl network, source $s$, sink $t$, edge capacity $c(v, w)$, flow, maximum flow, preflow $f$, flow excess $e(v)$ of a vertex $v$, residual graph, residual capacity $rescap(v, w)$ of the edge $(v, w)$, valid labeling $d$, active vertex, push, saturating push, } and {\sl nonsaturating push.} Let $G = (V, E)$ denote the digraph (assumed symmetric) corresponding to the network. Let $N = |V|$, $M = |E|$. We call an edge $(v, w)$ {\sl eligible} if $rescap(v, w) > 0$ and $d(v) = d(w) + 1$. Each vertex $v \in V$ has an adjacency list consisting the edges $(v,w) \in E$. For each vertex $v$, the first eligible edge in the adjacency list of $v$ is called its {\sl current edge} and denoted by $ce(v)$ (such an edge may not exist, in which case $ce(v)$ refers to none). Our implementation is based on the algorithm developed by Cheriyan and Hagerup (see \cite{CH}). Following \cite{CH} we shall refer to this algorithm as PLED (shorthand for Prudent Linking and Excess Diminishing). This algorithm is an instance (with one minor exception) of the generic preflow algorithm by Goldberg and Tarjan \cite{GT88}. The difference (namely, the value of a push over an edge $(v,w)$ may be less then both the excess at $v$ and residual capacity of $(v,w)$) does not affect the essential properties of the generic algorithm (in particular, maximum flow is always correctly computed upon termination). PLED also uses an idea introduced by Ahuja and Orlin \cite{AO} of scaling the volume of the pushes. The scaling factor plays here, however, a slightly different role: the limits imposed on the volume of a push are not the same as in \cite{AO}. A third idea in PLED is randomization: after each relabeling of a vertex $v$, the edgelist of $v$ is permuted randomly. This random permutation ensures a better theoretical running time. Noga Alon showed in \cite{NA} that this randomization can be replaced by a deterministic procedure. The worst case running time of PLED, using the randomized procedure is $O(NM + N^{2}(logN)^{2})$ with high probability (see \cite{C1,C2,C3}). Using Alon's derandomization, the deterministic worst case bound improves to $O(NM+ N^{8/3}(logN))$. The worst case bound without randomization is $O(NMlog(N))$. Randomly permuting the edgelist of the vertex after relabeling can take substantial amount of time. From the implementation point of view just one random permutation of the adjacency list of each vertex at the start of execution suffices for the best theoretical running time, though the probability of failure increases slightly, $exp(-\Theta(\sqrt{NM} + NlogN))$ versus $exp(-\Theta(N\sqrt{NM} + N^2logN))$, see \cite{CH,C1}. Three main data structures are essential for PLED. \begin{itemize} \item {\bf Ordinary heap} that contains vertices which have big excesses and which are ordered by their distance labels. This structure supports the easy selection of a vertex for a push. (Select a vertex with the minimal distance label among the vertices having large enough excesses). \item {\bf Fibonacci heap}(see \cite{FH}) contains the rest of vertices, ordered by their (small) excesses. This supports constant (amortized) time decrease key operation and fast update of the scaling factor. \item {\bf Dynamic trees structure} (see \cite{ST}) to maintain a spanning forest $F$ of $G$ containing a subset of the current edges, where the value associated with an edge in $F$ is its residual capacity. This structure is able to send flow value along a path of length L in (amortized) time $O(logL)$\\ \end{itemize} \begin{tabbing} then \= then \= then \= then \= then \= \kill {\bf Sketch of the PLED algorithm:}\\[5mm] {\bf PLED Algorithm}\\ \> {\bf initialize}; \\ \> {\bf loop}( until all the excesses are eliminated)\\ \> \> v := {\bf select}; \\ \> \> {\bf macropush}(v);\\ \> {\bf endloop};\\ {\bf end PLED}\\ \end{tabbing} {\bf initialize}; \begin{quote} Perform the standard initialization of the variables $f, d$ and $e$ (see \cite{GT88}, pp.925) and of the dynamic trees, and Fibonacci heap data structures.\\ $\Delta := max(\{e(v) | v \in V-\{s,t\}\} \cup \{0\});$ \\ \end{quote} {\bf select:} vertex; \begin{quote} Return an active vertex $v$ with $e(v) \ge \Delta$ and minimum $d(v)$ or decrease $\Delta$ and then select $v$ as before.\\ \end{quote} {\bf macropush}($v$: vertex); \begin{quote} Send flow from $v$ over a path in the tree to which $v$ belongs, or if $v$ was a root then send flow from $v$ using edges $(v,w)$ for which $ rescap(v,w) \le$ {\bf limflow}($v$) until $v$ is relabeled or until $limflow(v)$ decreases to $< \Delta /2$ due to saturating pushes. If $limflow(v) > \Delta /2$ then v is linked to the other end of its current edge, and a treepush is executed. \\ \end{quote} {\bf limflow}(v : vertex): real; \begin{quote} return( if $e(v) \ge 2\Delta$ then $e(v)/2$ else $e(v)$);\\ \end{quote} The bottleneck factor in virtually all preflow-push type maximum-flow algorithm is the number of nonsaturating pushes. One of the properties of PLED is to try a sequence of nonsaturating pushes along several eligible edges that constitute a path in a tree of the eligible edges while avoiding saturation on that path, rather then performing a nonsaturating push along one single edge. These trees of the eligible edges are stored in a dynamic trees structure, in which one can perform a push in logarithmic time of the length of the path. Beside this property, PLED uses a scaling parameter for controlling the size of the pushes and the trees in the dynamic trees forest. A Fibonacci heap structure handles this scaling parameter efficiently. Finally for achieving the theoretically best bound, we either have to perform a random permutation or we have to generate a permutation by the deterministic scheme of \cite{NA} at the start of execution. Theoretically by permuting the adjacency lists after each relabel one could reach the best bound with higher probability, but the amount of work to do this can easily be substantial even if the number of relabel operations is just $\Theta(N)$. \section{Implementation} Since the algorithm requires the above data structures to achieve the theoretically best performance, we decided to implement all of them. In this we were encouraged by earlier experiences (see \cite{NG}) with implementations of Fibonacci heaps, and Splay trees \cite{Tj}. Splay trees play a main role in the dynamic trees structure. It was found in the experiments of \cite{NG} that a particular implementation of Splay trees was quite efficient comparing to some other search trees. In \cite{NG} Splay trees were compared to Binary, Red-Black and AVL trees and the Fibonacci heap was compared to Ordinary and Pairing heaps. Their study showed, that Fibonacci heaps are better than Ordinary heaps. This suggested that the use of Fibonacci heaps can have practical advantage, and that they can be implemented efficiently. So we implemented Fibonacci heaps and the dynamic trees data structure following \cite{ST}. Beside the above data structures, we implemented a routine for randomly permuting the edge lists of the vertices. Although the deterministic permutation of Alon derandomizes the algorithm, the overhead of such a permutation generating procedure is so large that we did not expect much improvement by implementing such a deterministic procedure. Moreover since our instances were mostly randomly generated, after some preliminary experiments we used the PLED algorithm without random permutations. For comparison reasons we coded Goldberg's simple preflow-push algorithm using simple FIFO queue for selecting the active vertices, and the dynamic trees version of this algorithm described in the same paper (\cite{GT88}). Later we refer to these codes as GOLD and GOLDYN respectively. In the code GOLDYN we did not control the size of the dynamic trees. Thus we got a code which has theoretical worst case bound $O(NMlogN)$ instead of $O(NMlog(N^2/M)$. The reason for this choice was mostly lack of time and the expected overhead of such a control mechanism. Besides, in the range of examples we tested the codes, the benefit from such size control, even without the overhead, probably is not significant. For testing the performance of the dynamic trees data structure, we implemented its operations ({\sl find-min, add-value, find-root, link, cut, etc.}) with storing the trees explicitly and executing these operations in the obvious (linear time) way. Hence we avoided the overhead of handling Splay trees and complicated updates. Later in this paper the codes using these ``non-dynamic tree'' operations are called NPLED and NGOLDYN. Note that the number of elementary operations for PLED and NPLED (or GOLDYN and NGOLDYN) are the same on the same instance, only the way of handling the tree operations are different. Therefore the difference in running time shows exactly the impact of the dynamic trees structure. In our implementations of all the codes we employed an idea, mentioned in (\cite{GT88}), the so called ``global-'' or ``big-relabeling''. Our early experiments showed clearly, that in PLED just like in GOLD or GOLDYN, the running times of the variant which uses global-relabeling were much smaller (orders of magnitude) than the one which does not use it. Therefore we built in some heuristic parameters controlling the calling frequency of big-relabeling and affecting thus the running time. A ``big-relabeling'' step consist of two breadth-first-searches, one starting from the sink and working on the sink side of the residual graph, and another one for the source side, starting from the source. In these breadth-first-searches the shortest distance is calculated from each vertex to the sink on the sink side, or to the source on the source side, respectively. Unfortunately breadth-first-search is a relatively expensive operation (it takes O(M) steps), so the calling frequency of big-relabel is very important and can be a subject of later studies. The effect of a big-relabeling is to lift all the vertices as high as possible, keeping the labeling feasible. This is the point where this expensive operation can help a lot. During the steps of these ``preflow-push'' type algorithms the label of a vertex $v$ (say $d(v)$) is always a lower bound on the shortest distance from $v$ to the sink if the sink is reachable from $v$ in the residual graph, or $(d(v)-N)$ is a lower bound on the distance from $v$ to the source. After each saturating push along the edge $(v, w)$, $v$ can either have another eligible edge for later pushes, or it will be relabeled, i.e. lifted right above its neighbors. In this latter case the deletion of the edge $(v, w)$ cuts the tree (formed by some of the current edges) to which $v$ belonged. All the vertices in the subtree, rooted at $v$, will keep their old labels, and so their real distance from the sink can become larger then the corresponding label values. Hence, after some iterations, there could be many such vertices whose label is far from their real distance. The algorithm will terminate only when all the remaining excesses are sent back to the source. Therefore vertices with positive excess have to be lifted above the source (having the label value $N$). Since one relabel lifts a vertex only above its neighbors, meaning an increase by 1 or 2 in its label in the average case, many simple relabel operations may be necessary right before termination. In the worst case for example, if the $s-t$ minimum cut $(V_s, V - V_s)$ with $V_s$ minimal has $|V_s| = \Theta(N)$, then we may need $O(N^2)$ simple relabels just to terminate the algorithm. In practice, we found that this so called second phase of the algorithm can take almost all the running time (because the number of relabels became significant). In contrast only one execution of big-relabel step will lift ALL the vertices as high as possible by calculating the exact distances from each vertex to the sink or to the source, respectively. Of course, if our graph is dense, one big-relabel can also take $O(M)$ time, but each of these steps are much cheaper than a simple relabeling. We built 3 parameters to control the calling frequency of the big-relabel procedure. \begin{enumerate} \item {\bf Relab-freq}, a nonnegative integer. A big-relabel is called after each {\bf Relab-freq} iterations. By iteration we mean a vertex selection. (This is a simple heuristic to call big-relabel with some constant frequency.) \item {\bf Cut-freq}, a nonnegative integer. After this many cuts in the tree structure a big-relabel is called. (This parameter estimates the total sum of the differences between the actual labels of the vertices and their shortest distances to the sink or to the source, respectively. After a cut performed at the vertex $v$, not only the label of $v$, but all the labels of its descendants in the tree can loose their exact meaning. That is the label of a vertex $w$ in the subtree of $v$ can be less than the shortest distance from $w$ to the sink, since the shortest distances may increase by cutting an edge. Hence, by calculating the number of cuts only, we are not taking into account all the labels in the subtree. Some further improvement could be done by making this estimation more precise.) \item {\bf Gap}, a switch which can be on or off. If on, it checks whether the labels of the vertices, not larger than $N-2$, form a consecutive sequence or not. If there is a gap (according to \cite{DM}), there is a cut in the residual graph, hence each vertex in the source side have to be lifted above the source, and therefore a big-relabel is called. \end{enumerate} Our experiments showed that before the maxflow value is reached, parameters {\bf Relab-freq} or {\bf Cut-freq} can be helpful. Their effect seemed to be equivalent in the sense that in almost all problems we tested, the number of iterations was roughly four times more than the number of cuts. So by setting {\bf Cut-freq} = {\bf Relab-freq}/4 we could get about the same number of big-relabels. The use of the {\bf Gap} parameter is extremely benefitial in this phase and its update is a very cheap operation. Therefore, in our experiments we always turned {\bf Gap} on. In the second phase, i.e. in the phase of sending back the excesses, {\bf Relab-freq} or {\bf Cut-freq} are useful, while {\bf Gap} has no impact at all. The second phase can take quite a long time, in particular for problems with long paths from the source to the sink, and with large excess to be sent back to the source. Therefore, the use of the big-relabel is important in this final phase, too. On the other hand, since big-relabel is a costly operation, we kept its calling frequency below a small linear function of the number of arcs, in order to keep the overall complexity at $O(NM)$. We implemented another mechanism to achieve better running times in all three codes. Namely at initialization the algorithm calculates an upper bound $U$ on the maximum flow value by taking the minimum of capacities of some cuts. Then it creates a new source by adding an artificial vertex $S$ and a new arc $(S, s)$ with capacity $U$ to the network, where $s$ was the old source. The new problem is obviously equivalent with the old one, and the extra cost of its implementation is negligible. The advantage of doing this is that we do not let the algorithm push too much excess into the network, reducing in this way the runtime of the second phase. We have found instances showing that without this procedure the running time was significantly bigger due to the long second phase. \section{Experimental results} For the experiments, we used the DIMACS suggested problems, and the generators GENRMF, WASHINGTON, and AC-MAX \cite{gen,wash,ac}. (See the DIMACS document ``The Core Experiments''). The families of networks we report on include the ones suggested by ``The Benchmark Experiments'', and two classes of problems made intentionally very difficult for Goldberg's preflow-push algorithm. The input parameters for the DIMACS benchmark problems were chosen, according to the structure of the particular networks, such that the number of nodes of the generated example increase approximately by multiples of $2$ up to the memory limitations of our workstation. \subsection{Description of the problem classes} The generator GENRMF takes 4 numbers ($ a, b, c_1 and c_2 $) as input parameters. The resulting network consists of $ b$ layers of $ (a \times a)$ grids, in one of the corners of the first layer is the source, and in the opposite corner of the last layer is the sink. Arcs are drawn between each neighboring grid nodes in both directions with capacities $ c_2a^2 $, and two consecutive layers are connected along a randomly generated perfect matching with capacities chosen randomly in the range $(c_1, c_2)$. The generator WASHINGTON takes several numbers as input parameters. The first argument chooses the type of the network, and the rest are specific to the type chosen. The generator AC-MAX generates fully dense or sparse random acyclic networks. The only parameter is $n$, the number of nodes in the network. (see ``The Core Experiments'')\\ The following is a description of the network families what we tested on. Exact parameters for the families GL, GW, WLM and AD are given in Table~\ref{Benchdef.tbl}. \begin{itemize} \item {\bf GL - Genrmf-Long}. Generated by the GENRMF code. They are called ``long'', because $ b$ is approximately $a^2$. \item {\bf GW - Genrmf-Wide}. Generated by the GENRMF code. They are called ``wide'', because $ a$ is approximately $b^2$. \item {\bf WLM - Washington-Line-Moderate}. Fairly dense networks, generated by the WASHINGTON code. The network type is ``6'', and the type specific parameters are $ n, m, deg$. The resulting network has $ n \times m$ nodes in a grid, plus two additional nodes for the source and sink. The source is connected to the first m nodes of the grid, and the last $ m$ nodes are connected to the sink by arcs with infinite capacities. For each node in the grid, $ deg$ arcs are generated with random capacities pointing to $ deg$ randomly selected nodes from the next $ deg$ columns. \item {\bf AD - Acyclic-Dense}. These instances are fully dense acyclic graphs with random capacities, generated by the AC-MAX code. \begin{table}[h]\begin{center} \caption{ Parameters used for generating the DIMACS Benchmark instances.\label{Benchdef.tbl}} %\protect{\vspace{1ex}} \begin{tabular}{||l|l|r|r||} \hline NAME &PARAMETERS&NODES&ARCS\\ \hline GL1 & $a$=6 $b$=31 $c_1$=1 $c_2$=10000 & 1116 & 4800 \\ GL2 & $a$=7 $b$=42 $c_1$=1 $c_2$=10000 & 2058 & 9065 \\ GL3 & $a$=8 $b$=64 $c_1$=1 $c_2$=10000 & 4096 & 18368 \\ GL4 & $a$=9 $b$=100 $c_1$=1 $c_2$=10000 & 8100 & 36819 \\ GL5 & $a$=11 $b$=128 $c_1$=1 $c_2$=10000 & 15488 & 71687 \\ GL6 & $a$=13 $b$=194 $c_1$=1 $c_2$=10000 & 32786 & 153673 \\ \hline GW1 & $a$=16 $b$=4 $c_1$=1 $c_2$=10000 & 1024 & 4608 \\ GW2 & $a$=21 $b$=5 $c_1$=1 $c_2$=10000 & 2205 & 10164 \\ GW3 & $a$=28 $b$=5 $c_1$=1 $c_2$=10000 & 3920 & 18256 \\ GW4 & $a$=37 $b$=6 $c_1$=1 $c_2$=10000 & 8214 & 38813 \\ GW5 & $a$=48 $b$=7 $c_1$=1 $c_2$=10000 & 16128 & 76992 \\ GW6 & $a$=64 $b$=8 $c_1$=1 $c_2$=10000 & 32768 & 157696 \\ \hline WLM1 & 6 64 4 5 & 258 & 1236 \\ WLM2 & 6 128 4 8 & 514 & 3975 \\ WLM3 & 6 256 4 8 & 1026 & 8069 \\ WLM4 & 6 512 4 11 & 2050 & 22279 \\ WLM5 & 6 1024 4 16 & 4098 & 65019 \\ WLM6 & 6 2048 4 22 & 8194 & 179258 \\ \hline AD1 & fully dense & 256 & 32640 \\ AD2 & fully dense & 321 & 51360 \\ AD3 & fully dense & 403 & 81003 \\ AD4 & fully dense & 507 & 128271 \\ AD5 & fully dense & 636 & 201930 \\ AD6 & fully dense & 800 & 319600 \\ \hline \end{tabular}\end{center} \end{table} \clearpage \item {\bf GB - Goldberg-Bad-Case}. A deterministic family, generated by the WASHINGTON code. The type is ``10'', and has one parameter $n$. The structure is described in Figure~\ref{GB-net}. This family was designed especially difficult for Goldberg's algorithm. We generated 30 networks of this kind, with changed the value of $n$ along a geometric series from 500 to 25000. \begin{figure}[h] \centerline{\psfig{figure=GB-net.ps,height=70pt,width=250pt}} \caption{ Goldberg-Bad-Case network \label{GB-net}} \end{figure} \item {\bf CL - Cheriyan-Graph-Long}. A deterministic family, generated by the WASHINGTON code. The type is ``11'', and has three parameters $n, m, c$. The structure is described in Figure~\ref{Cher-net}. This family was designed by J. Cheriyan, and also considered as a hard case for Goldberg's algorithm. For CL networks, we generated 30 instances with $n=1000$, $m=10$ and $c$ changed along a geometric series from 10 to 1000. \item {\bf CW - Cheriyan-Graph-Wide}. The same family as CL, except the generated 30 instances have parameters $n=1000$, $m$ changed along a geometric series from 10 to 1000 and $c=10$. \end{itemize} \begin{figure}[h] \centerline{\psfig{figure=Cher-net.ps,height=200pt,width=250pt}} \caption{ Cheriyan-Graph \label {Cher-net}} \end{figure} \clearpage The following three families were all generated by the code GENRMF, with different parameter settings. Each contains 30 instances. Capacities $c_1, c_2$ were set to 100 and 10000 respectively in each case. \begin{itemize} \item {\bf GXL - Genrmf-eXtra-Long}. Extreme ``long'' networks, with $a=4$, and $b$ changed along a geometric series from 20 to 2430. \item {\bf GM - Genrmf-Medium}. Cubic like networks, with $a=b$, and both were incremented by 1 from 5 to 34. \item {\bf GXW - Genrmf-eXtra-Wide}. Extreme ``wide'' networks, with $a$ changed along a geometric series from 20 to 94, and $b=4$. \end{itemize} \begin{table}[h]\begin{center} \caption{Benchmark times (sec) on the SPARCstation 1+ used for testing. \label{Bench.tbl}} \begin{tabular}{||l|r|r|r||r|r|r||} \hline {\bf FORTRAN} & \multicolumn{3}{c||}{\bf TEST 1} & \multicolumn{3}{c||}{\bf TEST 2}\\ \cline{2-7} {\bf (netflow)}& {\bf real } & {\bf user} & {\bf sys } & {\bf real } & {\bf user} & {\bf sys }\\ \hline f77 & 5.7 & 4.7 & 0.5 & 9.8 & 8.6 & 0.6 \\ f77 -O & 4.8 & 3.6 & 0.4 & 7.3 & 6.1 & 0.6 \\ f77 -O1 & 5.4 & 4.6 & 0.5 & 9.7 & 8.5 & 0.6 \\ f77 -O2 & 4.0 & 3.4 & 0.4 & 6.7 & 5.7 & 0.6 \\ f77 -O3 & 4.4 & 3.6 & 0.5 & 7.0 & 6.3 & 0.4 \\ f77 -O4 & 3.7 & 2.9 & 0.5 & 5.8 & 5.0 & 0.6 \\ \hline \hline {\bf C} & \multicolumn{3}{c||}{\bf TEST 1} & \multicolumn{3}{c||}{\bf TEST 2} \\ \cline {2-7} {\bf(wmatch)} & {\bf real } & {\bf user} & {\bf sys } & {\bf real } & {\bf user} & {\bf sys }\\ \hline cc & 5.5 & 5.2 & 0.2 & 46.2 & 44.7 & 0.5 \\ cc -O & 4.4 & 4.0 & 0.2 & 35.9 & 34.2 & 0.6 \\ gcc & 5.9 & 5.5 & 0.2 & 49.3 & 47.5 & 0.5 \\ gcc -O & 4.4 & 4.1 & 0.2 & 34.2 & 32.7 & 0.3 \\ \hline \end{tabular}\end{center} \end{table} \subsection {Description of the reported data} In all reported experiments we used the {\bf Gap} switch on , {\bf Relab-freq} = $0.5M$, {\bf Cut-freq} = 0 and the procedure to generate permutations was turned off. Table~\ref{Run.tbl}. contains the mean running times of 10 random instances and the relative variance for the DIMACS Benchmark problems. All reported times are in CPU seconds on a Sun Sparc 1+ Workstation and do not include I/O time. We attempted to measure the user CPU time what the program uses during the execution of the algorithm. Since we used a multi-user workstation under Unix, our obtained running times slightly depended on the workload of the system. This can explain a part of the large variances. Figures 3--9 contain graphical comparison of the tested algorithms on the GB, CL, CW, GXL, GM, GXW families. The codes were written in ANSI C language, employing structures, pointers in order to handle the various operations efficiently. Memory requirements are 24 bytes/edge for all codes and 64 bytes/vertex for PLED, 20 bytes/vertex for GOLD, and 40 bytes/vertex for GOLDYN. All integers are of 4 bytes. We used the Gnu C-compiler (gcc) with -O optimization option. Table~\ref{Bench.tbl}. contains some benchmark results which were obtained by executing the DIMACS provided Fortran and C codes on our machine.\\ \begin{table}[h]\begin{center} \caption{Mean running times (secs) and relative variances (\%) of the instances.\label{Run.tbl}} %\protect{\vspace{1ex}} \begin{tabular}{||l||r|r||r|r||r|r||} \hline NAME & \multicolumn{2}{c||} {PLED} & \multicolumn{2}{c||} {GOLD} & \multicolumn{2}{c||} {GOLDYN}\\ \cline{2-7} & mean & var \% & mean & var \% & mean & var \% \\ \hline GL1 & 2.11 & 19.9 & 0.68 & 19.6 & 1.14 & 22.3 \\ GL2 & 4.82 & 11.9 & 1.57 & 12.4 & 2.59 & 15.3 \\ GL3 & 11.20 & 9.9 & 3.76 & 6.9 & 5.71 & 9.9 \\ GL4 & 27.89 & 9.2 & 8.83 & 11.3 & 12.74 & 5.4 \\ GL5 & 64.69 & 9.3 & 20.94 & 10.1 & 28.98 & 7.3 \\ GL6 & 275.75 & 7.0 & 54.43 & 10.2 & 144.85 & 7.6 \\ \hline GW1 & 3.38 & 10.2 & 1.27 & 9.0 & 2.42 & 11.4 \\ GW2 & 8.91 & 7.5 & 3.45 & 5.7 & 6.55 & 3.9 \\ GW3 & 20.62 & 6.4 & 8.46 & 4.0 & 15.47 & 9.7 \\ GW4 & 61.92 & 7.6 & 23.49 & 6.1 & 43.86 & 6.3 \\ GW5 & 158.01 & 4.7 & 59.84 & 4.7 & 106.44 & 6.6 \\ GW6 & 979.44 & 6.5 & 149.21 & 8.0 & 314.10 & 6.0 \\ \hline WLM1 & 0.20 & 5.3 & 0.07 & 4.2 & 0.13 & 5.0 \\ WLM2 & 0.53 & 8.7 & 0.18 & 6.2 & 0.30 & 7.8 \\ WLM3 & 1.38 & 7.5 & 0.37 & 11.8 & 0.54 & 8.5 \\ WLM4 & 3.21 & 10.2 & 0.87 & 11.2 & 1.19 & 13.7 \\ WLM5 & 8.05 & 6.5 & 2.28 & 5.8 & 2.79 & 9.5 \\ WLM6 & 22.75 & 5.3 & 5.94 & 9.7 & 7.14 & 6.1 \\ \hline AD1 & 1.32 & 18.9 & 1.11 & 10.5 & 1.34 & 18.8 \\ AD2 & 2.42 & 19.8 & 1.80 & 13.2 & 2.22 & 15.1 \\ AD3 & 3.52 & 16.1 & 2.82 & 12.4 & 3.38 & 11.1 \\ AD4 & 5.78 & 16.5 & 4.65 & 11.3 & 5.68 & 11.6 \\ AD5 & 8.81 & 16.4 & 7.09 & 16.1 & 8.49 & 16.9 \\ AD6 & 14.43 & 12.6 & 14.01 & 8.1 & 14.27 & 10.2 \\ \hline \end{tabular}\end{center} \end{table} \begin{table}[h]\begin{center} \caption{Number of Saturating and Nonsaturating pushes.\label{Push.tbl}} %\protect{\vspace{1ex}} \begin{tabular}{||l||r|r|r||r|r|r||} \hline NAME & \multicolumn{3}{c||}{SATURATING} & \multicolumn{3}{c||}{NONSATURATING}\\ \cline{2-7} & GOLD & GOLDYN & PLED & GOLD & GOLDYN & PLED \\ \hline WLC1 & 895 & 1036 & 899 & 2735 & 2172 & 3451\\ WLC2 & 1838 & 2231 & 1878 & 7444 & 5889 & 10282\\ WLC3 & 3550 & 4392 & 3775 & 17720 & 13869 & 26400\\ WLC4 & 7397 & 9629 & 8465 & 45568 & 36075 & 71340\\ WLC5 & 14001 & 18996 & 17646 & 104444 & 81626 & 182883\\ WLC6 & 27666 & 39759 & 38472 & 252319 & 193867 & 461418\\ \hline GL1 & 1076 & 1217 & 1004 & 10783 & 8619 & 12343\\ GL2 & 2151 & 2514 & 2072 & 24849 & 19618 & 27864\\ GL3 & 4229 & 4890 & 4065 & 60679 & 45268 & 71501\\ GL4 & 8228 & 9378 & 8078 & 146039 & 104902 & 201734\\ GL5 & 17065 & 19465 & 16867 & 343387 & 245319 & 476582\\ GL6 & 36856 & 42414 & 38370 & 900646 & 624328 &1364934\\ \hline GW1 & 1899 & 3038 & 2598 & 19883 & 20123 & 15289\\ GW2 & 4858 & 7826 & 6759 & 51479 & 57841 & 42577\\ GW3 & 10453 & 17456 & 15319 & 124369 & 141565 & 95288\\ GW4 & 26700 & 44745 & 42481 & 342545 & 408457 & 287406\\ GW5 & 61309 & 102140 & 103667 & 826702 & 1037573 & 765610\\ GW6 &138916 & 236455 & 259357 & 2068616 & 2699497 &2268190\\ \hline WLM1 & 247 & 251 & 240 & 652 & 611 & 841\\ WLM2 & 490 & 503 & 459 & 1264 & 1179 & 1972\\ WLM3 & 938 & 978 & 882 & 3504 & 2651 & 7603\\ WLM4 & 1773 & 1857 & 1595 & 6367 & 4747 & 17397\\ WLM5 & 3621 & 3822 & 3149 & 12077 & 8594 & 39231\\ WLM6 & 6970 & 7480 & 5978 & 23030 & 15110 & 91198\\ \hline AD1 & 358 & 628 & 586 & 415 & 142 & 258\\ AD2 & 499 & 838 & 773 & 537 & 190 & 402\\ AD3 & 618 & 1040 & 936 & 670 & 235 & 443\\ AD4 & 759 & 1323 & 1186 & 858 & 292 & 534\\ AD5 & 954 & 1631 & 1483 & 1052 & 376 & 683\\ AD6 & 1183 & 1977 & 1902 & 1283 & 495 & 884\\ \hline \end{tabular}\end{center} \end{table} \begin{table}[h]\begin{center} \caption{Number of Vertex Selections and Relabels.\label{SelRel.tbl}} %\protect{\vspace{1ex}} \begin{tabular}{||l||r|r|r||r|r|r||} \hline NAME & \multicolumn{3}{c||}{SELECT} & \multicolumn{3}{c||}{RELABEL}\\ \cline{2-7} & GOLD & GOLDYN & PLED & GOLD & GOLDYN & PLED \\ \hline WLC1 & 3374 & 2470 & 3217 & 713 & 727 & 736\\ WLC2 & 9108 & 6601 & 8821 & 1828 & 1940 & 2112\\ WLC3 & 21674 & 15208 & 21884 & 4264 & 4477 & 5467\\ WLC4 & 55836 & 40074 & 59103 & 10953 & 12069 & 15545\\ WLC5 & 126935 & 88635 & 146368 & 23762 & 26680 & 40123\\ WLC6 & 307239 & 210937 & 365618 & 57558 & 63994 & 102588\\ \hline GL1 & 13454 & 8814 & 10152 & 2944 & 2954 & 3132\\ GL2 & 30803 & 20046 & 22795 & 6610 & 6844 & 7181\\ GL3 & 73657 & 43938 & 53240 & 14367 & 14884 & 16559\\ GL4 & 174621 & 96398 & 131540 & 31354 & 32443 & 40588\\ GL5 & 407952 & 218523 & 305694 & 72237 & 73552 & 95535\\ GL6 & 1054634 & 531145 & 811533 & 170055 & 178095 & 256119\\ \hline GW1 & 25255 & 19371 & 17671 & 5773 & 7095 & 6685\\ GW2 & 65811 & 51368 & 45786 & 15393 & 19091 & 17494\\ GW3 & 157419 & 119001 & 106912 & 35319 & 44203 & 40563\\ GW4 & 435163 & 329006 & 317527 & 98618 & 123425 & 120234\\ GW5 & 1054655 & 798915 & 810822 & 241743 & 302175 & 306952\\ GW6 & 2615522 & 1969943 & 2124932 & 578402 & 752522 & 804951\\ \hline WLM1 & 787 & 582 & 734 & 140 & 142 & 151\\ WLM2 & 1508 & 1143 & 1649 & 245 & 259 & 330\\ WLM3 & 4165 & 2511 & 5194 & 682 & 597 & 1092\\ WLM4 & 7506 & 4503 & 11088 & 1195 & 1035 & 2301\\ WLM5 & 14035 & 8046 & 24355 & 1960 & 1593 & 4975\\ WLM6 & 26470 & 14168 & 52860 & 3442 & 2572 & 10574\\ \hline AD1 & 590 & 567 & 556 & 188 & 187 & 307\\ AD2 & 788 & 761 & 864 & 270 & 270 & 470\\ AD3 & 974 & 915 & 944 & 326 & 318 & 518\\ AD4 & 1246 & 1198 & 1152 & 415 & 418 & 639\\ AD5 & 1513 & 1465 & 1471 & 497 & 499 & 815\\ AD6 & 1864 & 1805 & 1819 & 576 & 583 & 1021 \\ \hline \end{tabular}\end{center} \end{table} \subsection{Evaluation of the DIMACS Benchmark problems} From Table~\ref{Run.tbl}. at first sight we can say that the simple preflow-push code (GOLD) performs much better on these families than our PLED or GOLDYN implementation. The only exception were the AD instances, where all codes performed about the same way. Moreover the ratio of the running times of PLED over GOLD is getting bigger in almost all the cases as the number of nodes increases. This ratio is very much depending on the structure of the network. Having a closer look of the profile information of PLED, we found that PLED used about 45\% of the execution time for heap operations and only 10-12\% for dynamic trees operations. We have also found (see Table~\ref{SelRel.tbl}.) that the number of selections of the vertices for the same problem were about the same in PLED as in GOLD. Since GOLD uses only a simple FIFO policy, while PLED has a ``sophisticated'' minimum label selection rule, GOLD can be much faster in these cases. This means that using the global relabeling technique, in average both algorithms take approximately the same number of steps. The running times of PLED in Table~\ref{Run.tbl}. corresponds to the ``considered to be the best'' parameter settings. From early experiments we learned that using random or deterministic permutations instead of just leaving the edgelists untouched has no practical advantage. In some cases the number of operations decreased slightly if the edgelists were permuted, but the cost of such a procedure is high, and the running times became larger. We even encountered examples, in which the number of steps taken was more with using permutations than without them. Let us remark also since all the examples were generated randomly, an additional random permutation of the adjacency lists can not add much to the randomness of these lists. Our experiments also showed, that perhaps the best setting for the parameter {\bf Relab-freq} (, and {\bf Cut-freq}) is in the range $[0.4N..4N]$ ( $[0.1N..N]$ ), however, we could not make much difference between the values in this range. For several different settings from this range we obtained almost identical running times. On the other hand, of course, too small values for these parameters result in too many big-relabel calls, while too large values do not make profit of the big-relabel procedure. As we mentioned earlier, the effect of big-relabel is so significant, that its examination could be a subject of later studies. It is interesting that problems with short paths between the source and the sink (eg. the Acyclic-dense problems which are full graphs with diameter 1 or 2) need much less effort to solve than other problems. A reason for this perhaps, is that the maximum flow can be pushed over much sooner in these cases. \clearpage \subsection{Testing on the GXL, GM, GXW problems} Since the DIMACS Benchmark problems had only a limited set of networks, we decided to compare our codes on some ``extreme'' families too. We assumed that the length of paths from the source to the sink could be relevant for Goldberg's algorithm, so we generated the earlier described GXL, GM, GXW network families. Figures~\ref{GL.ps}.,~\ref{GM.ps}., and \ref{GW.ps}. show graphs of running times obtained on these networks. All the scales are linear and the runtimes are shown as functions of the number of vertices. Among these problems the GXW family seems to be the hardest to solve. Even the growth rate is the highest on GXW networks for all the codes. Again GOLD proved to be the fastest in the GM and GXW case, while PLED is the slowest in all three cases. However, on the GXL family the dynamic tree version of Goldberg's algorithm performed the best. This family has the property that the sink can be reached from the source using only relatively long paths, (compared to the size of the network). So the strategy of pushing excess along a longer path seems to have advantage in this case. GOLDYN pushes excesses as far as possible without controlling the size of this path or the amount to be pushed. On the other hand PLED does not use this ``greedy'' strategy (e.g. by limiting the amount to be pushed). This experiment also suggests that the longer the relative distance between the source and the sink, the more useful the GOLDYN algorithm could be. \begin{figure}[h] \centerline{\psfig{figure=GL.ps,height=230pt,width=330pt}} \caption{ Runtimes on the Genrmf-eXtra-Long problems.\label {GL.ps}} \end{figure} \begin{figure}[h] \centerline{\psfig{figure=GM.ps,height=230pt,width=330pt}} \caption{ Runtimes on the Genrmf-Medium problems.\label {GM.ps}} \end{figure} \begin{figure}[h] \centerline{\psfig{figure=GW.ps,height=230pt,width=330pt}} \caption{ Runtimes on the Genrmf-eXtra-Wide problems. \label {GW.ps}} \end{figure} \clearpage \subsection{The effect of dynamic trees} Figures~\ref{GB.ps}.,~\ref{CL.ps}. and \ref{CW.ps}. show the experimental results obtained on the GB, CL and CW families. To examine the effect of using the dynamic trees data structure, we also ran our NPLED and NGOLDYN code on these examples. Figure~\ref{GB1.ps}. contains the same runtimes as Figure~\ref{GB.ps}., except the scale is different since it shows PLED and GOLDYN only.\\ It is clear that GOLD, even with using the big-relabel strategy, is far the slowest on the GB problems. What is more interesting is that this family was the only case where PLED and GOLDYN outperformed their ``non-dynamic tree'' versions. While the running time of NPLED and NGOLDYN is exponentially increasing, PLED and GOLDYN has a nice linear behavior (see Figure~\ref{GB1.ps}.). The difference can be as large as 16 second versus 3192 second for GOLDYN vs. NGOLDYN and 73 second vs. 1862 second for PLED vs. NPLED on the largest example. This emphasizes again that pushes along long paths can be handled by the dynamic trees structure much more efficiently. We counted the average length of a push during the execution of PLED and GOLDYN, and found that in the case of the GB family it was significantly longer than in any other families. Significant means several hundreds or thousands for GB and less than 10 (ten) for the rest, including all the tested families. On the CL family both NPLED and NGOLDYN were faster than their counterparts, and on the CW family PLED could beat NPLED. Looking at the average push length in these cases we again found that it was very small (under 3) in the CL family for both algorithms, and slightly increasing, but still under 11 on the CW problems for GOLDYN. This length was the longest ($\approx 15$) on the CW family for PLED, what may explain why it could perform better then NPLED. It is worth to mention that in all the cases PLED tends to push along longer paths as we have found that the average length of a push was always longer for PLED than for GOLDYN. This may come from the fact that PLED links trees together only if the link has enough residual capacity, while GOLDYN can link trees with a small capacity edge, and hence by pushing along a path GOLDYN may have to cut more often than PLED. The second longest average length for pushes were found in the GXL case. This supports our conjecture that algorithms using dynamic trees like PLED or GOLDYN can have practical advantage on networks with extremely large distance between the source and the sink.\\ Figures~\ref{CL.ps}. and \ref{CW.ps}. also show that the actual structure of the network can change completely the ranking of the execution times of these algorithms. \begin{figure}[h] \centerline{\psfig{figure=GB.ps,height=220pt,width=330pt}} \caption{Runtimes on the Goldberg-Bad-Case problems. \label {GB.ps}} \end{figure} \begin{figure}[h] \centerline{\psfig{figure=GB1.ps,height=220pt,width=330pt}} \caption{Runtimes of PLED and GOLDYN on the Goldberg-Bad-Case problems. (Note that the last to sample points for the time of PLED shows that the workstation started to swap memory at these sizes, since PLED uses the memory most extensively.) \label {GB1.ps}} \end{figure} \begin{figure}[h] \centerline{\psfig{figure=CL.ps,height=230pt,width=330pt}} \caption{ Runtimes on the Cheriyan-Long problems. \label {CL.ps} } \end{figure} \begin{figure}[h] \centerline{\psfig{figure=CW.ps,height=230pt,width=330pt}} \caption{ Runtimes on the Cheriyan-Wide problems. \label {CW.ps}} \end{figure} \clearpage \section{Conclusions} Summarizing our work, we can conclude that although the PLED algorithm has a very good theoretical worst case bound, in practice Goldberg's simple preflow-push algorithm outperforms it on most of the examples of this study. Our study shows that the structure of the networks is the most important factor in ranking the algorithms. (E.g. see the examples shown on Figures~\ref{CL.ps}. and \ref{CW.ps}.) One such parameter to be considered, reflecting the structure of the network, could be the relative distance between the source and the sink. In this study we were particularly interested in the effectiveness of dynamic trees. Our experiments show clearly that there are families of problems for which dynamic trees improved the performance of our code at a small cost. To determine the properties of network classes on which the algorithms GOLDYN or PLED are the best would be an interesting topic of later works. Let us remark finally that Fibonacci heaps did not help much in these examples. They did not improve neither the running time nor the number of selection steps of PLED. \noindent{\bf Acknowledgment}: The authors are thankful to Joseph Cheriyan and to the anonymous referee for the many helpful comments and suggestions. \bibliographystyle{amsplain} \begin{thebibliography}{00} { \bibitem{CH}J.~Cheriyan and T.~Hagerup: ``A randomized maximum-flow algorithm''. in Proc.IEEE FOCS (1989), 118-123. \bibitem{C1}J.~Cheriyan and T.~Hagerup: ``A randomized maximum-flow algorithm''. Tech. Report 988, O.R.I.E, Cornell Univ., Ithaca, NY, Oct. 1991. \bibitem{C2}J.~Cheriyan, T.~Hagerup and K. Mehlhorn: ``Can a maximum flow be computed in $o(nm)$ time?''. Proc. 17th Internat. Colloquium on Automata, Languages and Programming, 1990, pp.235-248. \bibitem{C3}J.~Cheriyan, T.~Hagerup and K. Mehlhorn: ``An $o(n^3)$-Time Maximum-Flow Algorithm''. Tech. Report MPI-I-91-120, Max Planck Institut f\"ur Informatik, Saarbr\"ucken, Germany, Nov. 1991. \bibitem{NA}N.~Alon: ``Generating pseudo-random permutations and maximum flow algorithms'' {\sl Information Processing Letters} {\bf 35} (1990), 201-204. North-Holland \bibitem{AO}R.~K.~Ahuja and J.~B.~Orlin: ``A Fast and Simple Algorithm for the Maximum Flow Problem''. {\sl Operations Research} {\bf 37} (1989), 748-759. \bibitem{AOT}R.~K.~Ahuja, J.~B.~Orlin and R.~E.~Tarjan: ``Improved Time Bounds for the Maximum Flow Problem''. {\sl SIAM J.~Computing} {\bf 18} (1989), 939-954. \bibitem{wash}R.~Anderson, et al.: Program washington.c for creating maximum flow problem instances. Available through Dimacs. \bibitem{gen}T.~Badics: Program genrmf.c for creating maximum flow problem instances. Available through Dimacs. \bibitem{ac}G.~Waissi: Program ac-max.c for creating maximum flow problem instances. Available through Dimacs. \bibitem{DM}U.~Derigs and W.~Meier: ``Implementing Goldberg's max-flow-algorithm --- A computational investigation''. {\sl ZOR - Methods and Models of Operations Research} {\bf 33} (1989), 383-403. \bibitem{Goldb}A.~V.~Goldberg: ``A New Max-Flow Algorithm''. Tech.\ Rep.\ MIT/LCS/TM-291, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1985. \bibitem{GT88}A.~V.~Goldberg and R.~E.~Tarjan: ``A New Approach to the Maximum-Flow Problem''. \JACM{35} (1988), 921-940. \bibitem{GTT}A.~V.~Goldberg, \'E.~Tardos and R.~E.~Tarjan: {\sl Network Flow Algorithms}. Tech.\ Rep.\ No.~860, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1989. \bibitem{ST}D.~D.~Sleator and R.~E.~Tarjan: ``A Data Structure for Dynamic Trees''. {\sl Journal of Computer and System Sciences} {\bf 26} (1983), 362-391. \bibitem{Tj}R.~E.~Tarjan: {\sl Data Structures and Network Algorithms}. SIAM publications, Philadelphia, PA, 1983. \bibitem{FH}M.~L.~Fredman and R.~E.~Tarjan: ``Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms''. {\sl Journal of ACM} {\bf 34} (1987), 596-615. \bibitem{PH}M.~L.~Fredman, R.~Sedgewick, D.~D.~Sleator and R.~E.~Tarjan: ``The Pairing Heap: A New Form of Self-Adjusting Heap''. {\sl Algorithmica} {\bf 1} (1986), 111-129. \bibitem{NG}Gy.~Novotny: ``Comparison of Different Data Structures''. {\sl Thesis}. E\"otv\"os Lor\'and University, Budapest, 1989. } \end{thebibliography} \end{document}