New heuristics in MCF algorithms

[Peter Kovacs]

The attached patch contains implementation improvements and new heuristics for MCF algorithms.

[Alpar Juttner]

Does this patch matured enough to be included into lemon-1.2?

[Alpar Juttner]

I noticed that you replaced bool vectors to char at several placed, perhaps for performance reason. It's clear that you have carefully evaluated this change. However, I still have the feeling that the right choice here highly depends on the platform and also on the actual implementation of std::vector<>. Thus I suggest including comments at these places clarifying that these std::vector<char>s are actually bool ones, char is used only for the sake of performance.

[Peter Kovacs]

Replying to alpar:

Does this patch matured enough to be included into lemon-1.2?

Yes, it does. It was checked on almost all input files I have. However, I will most likely make further improvements in the CostScaling algorithm, because it does not give right solution for some very large instances (overflow problems?). This problem seems to be independent from the new heuristics.

This patch is not critical, but I wil need it for a paper soon, in which citing LEMON 1.2 would be better than an "upcomming release", wouldn't it?

[Peter Kovacs]

I attached a better version of the former patch, see [f3bc4e9b5f3a]. The two differences are the followings:

• Better relabeling in CostScaling to improve numerical stability and to make the code slightly faster.
• Notes are added to the classes about the usage of vector<char> instead of vector<bool> for efficiency reasons. (As Alpar suggested.)

This changeset is matured and tested enough to add to the main branch. Note that there are users how are interested in the performance of our cost scaling implementation (apart from my preferences about adding this changeset to release 1.2).

[Peter Kovacs]

[f3bc4e9b5f3a] went to the main branch.