COIN-OR::LEMON - Graph Library

Opened 15 years ago

Closed 11 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 thoneyvazul 13 years ago.
078bb2a214ca.patch (21.7 KB) - added by Alpar Juttner 13 years ago.
be2b4a8d4548.patch (21.6 KB) - added by thoneyvazul 13 years ago.
177-patches-87df475c2753--2ecc1e07d4ff.patch (37.6 KB) - added by Peter Kovacs 11 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 15 years ago by Alpar Juttner

Description: modified (diff)

comment:2 Changed 15 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Peter Kovacs

comment:3 Changed 15 years ago by Peter Kovacs

Status: newassigned

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

Peter,

shouldn't we postpone this ticket to Milestone 1.2?

If yes, please do it.

comment:5 Changed 15 years ago by Peter Kovacs

Milestone: LEMON 1.1 releaseLEMON 1.2 release

comment:6 Changed 15 years ago by Peter Kovacs

Type: enhancementtask

comment:7 Changed 14 years ago by Peter Kovacs

Milestone: LEMON 1.2 releaseLEMON 1.3 release

Changed 13 years ago by thoneyvazul

Attachment: 6c97bde900e6.patch added

comment:8 Changed 13 years ago by thoneyvazul

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

Changed 13 years ago by Alpar Juttner

Attachment: 078bb2a214ca.patch added

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

Cc: Peter Kovacs added

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

Attachment: be2b4a8d4548.patch added

comment:12 Changed 13 years ago by 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.

comment:13 Changed 11 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 11 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 11 years ago by Peter Kovacs

comment:15 in reply to:  14 Changed 11 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 11 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.