Boost The Efficiency Of Your Implementations By Using LEDA!

May 2005: Comparison Between Various Available Maxflow Implementations: Boost vs. Hi_Pr 3.5 vs. LEDA 5.0

 

The Algorithms and Data Structures Group of the University of Trier in Germany has made some tests in order to compare different available maxflow implementations.

The Competitors

Boost BGL

A graph library available at http://www.boost.org/libs/graph/doc/table_of_contents.html

Hi_Pr 3.5

This is a highly optimized C-implementation of the push-relabel method, following Goldberg and Tarjan, "A New Approach to the Maximum Flow Problem," J. ACM Vol. 35, 921--940, 1988
and
Cherkassky and Goldberg, "On Implementing Push-Relabel Method for the Maximum Flow Problem," Proc. IPCO-4, 157--171, 1995.

LEDA 5.0

A commercial graph library available at http://www.algorithmic-solutions.com

The Test Platform

2 x Ultra Sparc III (1.2GHz), 2048 MB RAM; Compiler: GCC-3.4.2 -O2

Problem Instances and Results

Three different types of networks have been tested. See the results for:

Copyright © 1998-2007 Algorithmic Solutions Software GmbH. All rights reserved.