[Lemon-devel] Circulation benchmark

[Kovács Péter]

Dear Developers,

Recently I have performed benchmark tests on the Circulation class and two 
alternative solutions for the feasible flow/circulation problem. The 
Circulation class proved to be the fastest, it was about 2.5 times faster on 
average than the corresponding function of the LEDA library.

The problem is to find a feasible flow (or in other words a feasible 
circulation) in a network in the following general manner. Each edge has an 
associated lower and upper bound that denotes the minimum and maximum amount 
that can flow on the edge and each node has an associated supply/demand 
value (signed). The difference of the incoming and outgoing amount of flow 
should be equal to the supply/demand value at each node. We assume that the 
sum of the (signed) supply/demand values of the nodes equals zero.

The Lemon Circulation class provides solution for a more general problem. We 
do not need to specify an exact supply/demand amount at the nodes, we should 
only give upper bounds for them. However if the sum of this values equals 
zero, we will receive equality at each node.
 
I tested three solutions. One of which is to simply use the Circulation 
class. An other method is to copy the graph to a SmartGraph structure, add 
two artificial nodes and some artificial edges to it and find a maximum flow 
in the new graph using the Preflow class. The third method is to use the 
FEASIBLE_FLOW function of the LEDA library.

I performed the benchmark on about 100 different NETGEN input files of 
different sizes form 50 nodes to 10000 nodes and different capacity and 
supply/demand values. I obtained similar results for almost all of them. The 
Circulation method was the best. It was about 2.2 times faster than copying 
and running Preflow and 2.5 times faster than the corresponding LEDA 
function on average. Moreover there was some graphs for which the LEDA 
function was extremely slow, at least 100 times slower than the two Lemon 
solutions.

Regards,
Peter