[Lemon-devel] Experiment with push-relabel matching alg.

[Alpár Jüttner]

Hi,

I've conducted some experimental evaluation with the Elevator class and
the bipartite matching algorithm based on the push-relabel principle.
Namely, this class use a data structure that makes is possible to
recognize when an empty level appears, and it can lift all items above
this empty level to the highest one. Therefore I compared the original
version with an improved one that lifts the element above an empty level
to the top whenever it appears.

The attached picture shows the results. The red cross shows the original
version, the green x is the new version (the x-axis indicates the size
of the underlying graph). The tests shows dramatic improvement, and the
strange dual behavior seems to have disappeared.

Jacint, does the max flow algorithm use this block lifting feature?

Regards,
Alpar

-------------- next part --------------
A non-text attachment was scrubbed...
Name: push2top2.png
Type: image/png
Size: 6554 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-devel/attachments/20070122/de39a7fa/attachment.png>