COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 6 years ago

#177 closed task (done)

Port the Edmonds-Karp max. flow alg.

Reported by: Alpar Juttner Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.3 release
Component: core Version: hg main
Keywords: Cc: Peter Kovacs
Revision id:

Description (last modified by Alpar Juttner)

This ticket is a follow-up of #47.

The affected files in

  • lemon/edmonds_karp.h

Attachments (4)

6c97bde900e6.patch (22.0 KB) - added by Antal Nemes 9 years ago.
078bb2a214ca.patch (21.7 KB) - added by Alpar Juttner 9 years ago.
be2b4a8d4548.patch (21.6 KB) - added by Antal Nemes 9 years ago.
177-patches-87df475c2753--2ecc1e07d4ff.patch (37.6 KB) - added by Peter Kovacs 6 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 11 years ago by Alpar Juttner

Description: modified (diff)

comment:2 Changed 11 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Peter Kovacs

comment:3 Changed 11 years ago by Peter Kovacs

Status: newassigned

comment:4 in reply to:  3 Changed 10 years ago by Alpar Juttner

Peter,

shouldn't we postpone this ticket to Milestone 1.2?

If yes, please do it.

comment:5 Changed 10 years ago by Peter Kovacs

Milestone: LEMON 1.1 releaseLEMON 1.2 release

comment:6 Changed 10 years ago by Peter Kovacs

Type: enhancementtask

comment:7 Changed 10 years ago by Peter Kovacs

Milestone: LEMON 1.2 releaseLEMON 1.3 release

Changed 9 years ago by Antal Nemes

Attachment: 6c97bde900e6.patch added

comment:8 Changed 9 years ago by Antal Nemes

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

Changed 9 years ago by Alpar Juttner

Attachment: 078bb2a214ca.patch added

comment:9 in reply to:  8 ; Changed 9 years ago by 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.

comment:10 Changed 9 years ago by Alpar Juttner

Cc: Peter Kovacs added

comment:11 in reply to:  9 Changed 9 years ago by 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.

Changed 9 years ago by Antal Nemes

Attachment: be2b4a8d4548.patch added

comment:12 Changed 9 years ago by Antal Nemes

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.

comment:13 Changed 6 years ago by Alpar Juttner

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

comment:14 Changed 6 years ago by 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.

Changed 6 years ago by Peter Kovacs

comment:15 in reply to:  14 Changed 6 years ago by 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.

comment:16 Changed 6 years ago by Alpar Juttner

Resolution: done
Status: assignedclosed

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

Note: See TracTickets for help on using tickets.