This page
contains the results of a comparison between the preflow-push maxflow code of
Cherkassky/Goldberg
(http://www.intertrust.com/star/goldberg/soft.html)
and the LEDA
(http://www.mpi-sb.mpg.de/LEDA)
implementation as described in chapter 7.10 of the LEDA
book (http://www.mpi-sb.mpg.de/~mehlhorn/LEDAbook.html)
on four different hardware
platforms
(follow the corresponding links at the end of this page). In this experiment
the LEDA
code has
been used with two different graph data structures:
is LEDA's
standard (general purpose) graph type that needs 16n + 12m words of memory.
is based on
a smaller static graph data structure that needs only 8n + 7m words of memory.
Note that
both data structures have been used with exactly the same maxflow source code
(LEDAROOT/incl/templates/max_flow.t).
We used Goldberg's ak-Generator to create
difficult and large maxflow problems (ak(i) for i=1,000
to 50,000). The experiments show
that the
large standard graph type (LEDA large) causes a slow-down by a factor of less
than
two compared
to the Cherkassky/Goldberg implementation whereas the new static and smaller
graph data
structure (LEDA small) achieves about the same running time as CG (on some
machines
it is slightly
slower, on others slightly faster).
Follow
these links to see the results for a particular hardware platform: