Port the Edmonds-Karp max. flow alg.

[Alpar Juttner]

This ticket is a follow-up of #47.

The affected files in

• lemon/edmonds_karp.h

[Alpar Juttner]

Peter,

shouldn't we postpone this ticket to Milestone 1.2?

If yes, please do it.

[thoneyvazul]

Added 6c97bde900e6.patch file contains an implementation for the Edmonds-Karp algorithm.

[Alpar Juttner]

Replying to thoneyvazul:

Added 6c97bde900e6.patch file contains an implementation for the Edmonds-Karp algorithm.

[078bb2a214ca] is a slight modification of the patch, namely

• it gives a reference to the svn revision it was (probably) ported from
• Doesn't list E-K amongst the 1.2 features (this version has already been released)

I basically like the port, but it would be nice if Peter could also have a look at it and adjust the namings at some places (e.g. template parameters) in order to better follow the conventions.

[Peter Kovacs]

Replying to alpar:

I basically like the port, but it would be nice if Peter could also have a look at it and adjust the namings at some places (e.g. template parameters) in order to better follow the conventions.

I'm going to check it soon (namings, doc, etc.)

Apart from that, I would like to merge the test file of E-K and Preflow (and all other max flow algorithms that will be ported in the future). They should have (almost) the same interface and hence can be tested together. For similar examples, see e.g. min_cost_flow_test.cc and min_mean_cycle_test.cc.

[thoneyvazul]

In be2b4a8d4548.patch I rechecked the template parameter names and changed them a little bit, so that it is more consistent to the preflow algorithm.

[Alpar Juttner]

I see no problem with version [be2b4a8d4548]. Peter, could you have a short look at it, too?

[Peter Kovacs]

I revised [be2b4a8d4548] and made some patches for it, see attached file.

• [87df475c2753] Improve and fix API doc of EdmondsKarp according to Preflow
• [0ad9454fd0b6] Rename DefFlowMap named parameter to SetFlowMap in EdmondsKarp according to Preflow
• [d1c4ed808574] Rename flow init functions according to Preflow (flowInit() --> init(), checkedFlowInit() --> checkedInit())
• [67ffe67e28de] Merge test files of Preflow and EdmondsKarp
• [2ecc1e07d4ff] Avoid usage of alternative operator

As for merging the test files: not only does this patch reduce code duplication (which is preferred in most cases), but it also helps preventing such inconsistencies that are fixed in the previous two commits.

As for the last changeset: I don't know if we accept such alternative operators (e.g. and, or) in LEMON code or not, but it was rather strange for me. You may omit this changeset if you don't like it.

[Alpar Juttner]

Replying to kpeter:

As for the last changeset: I don't know if we accept such alternative operators (e.g. and, or) in LEMON code or not, but it was rather strange for me. You may omit this changeset if you don't like it.

You are right, it should be avoided. It may even cause some compatibility issues.

[Alpar Juttner]

I rebased the above patches to the current tip and pushed to the main branch. See [92a884824429], [6a8a688eacf6], [2f00ef323c2e], [08f2dc76e82e], [45befc97b1bc] and [473c71baff72].