COIN-OR::LEMON - Graph Library

Opened 16 years ago

Closed 15 years ago

#47 closed task (fixed)

Port network flow algorithms

Reported by: Alpar Juttner Owned by: Peter Kovacs
Priority: critical Milestone: LEMON 1.1 release
Component: core Version:
Keywords: Cc:
Revision id:

Description (last modified by Peter Kovacs)

The affected files are

  • lemon/elevator.h
  • lemon/edmonds_karp.h
  • lemon/circulation.h
  • lemon/cost_scaling.h
  • lemon/min_cost_flow.h
  • lemon/min_cost_max_flow.h
  • lemon/preflow.h
  • lemon/capacity_scaling.h
  • lemon/min_mean_cycle.h
  • lemon/cycle_canceling.h
  • lemon/network_simplex.h
  • lemon/suurballe.h
  • lemon/goldberg_tarjan.h
  • test/min_cost_flow_test.lgf
  • test/preflow_test.cc
  • test/min_cost_flow_test.cc
  • test/min_cost_flow_test.net
  • test/preflow_graph.dim
  • test/suurballe_test.cc

And also:

  • lemon/dynamic_tree.h
  • lemon/dinitz_sleator_tarjan.h

Attachments (3)

2f64c4a692a8.patch (22.5 KB) - added by Alpar Juttner 15 years ago.
suurb1_39ff10276621.patch (5.4 KB) - added by Peter Kovacs 15 years ago.
suurb2_613d47d29dc3.patch (15.5 KB) - added by Peter Kovacs 15 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 16 years ago by Alpar Juttner

Description: modified (diff)

comment:2 Changed 16 years ago by Alpar Juttner

Description: modified (diff)

comment:3 Changed 16 years ago by Alpar Juttner

Description: modified (diff)

comment:4 Changed 16 years ago by Alpar Juttner

Description: modified (diff)

comment:5 Changed 16 years ago by Alpar Juttner

Description: modified (diff)

comment:6 Changed 16 years ago by Balazs Dezso

Elevator should be conform to the C++ standard. The uninitialized iterator cannot be copied Use -D_GLIBCXX_DEBUG to check conformity

comment:7 Changed 16 years ago by Alpar Juttner

Description: modified (diff)

comment:8 Changed 16 years ago by Alpar Juttner

Description: modified (diff)

comment:9 Changed 16 years ago by Alpar Juttner

Description: modified (diff)

comment:10 Changed 16 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:11 Changed 16 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Peter Kovacs

comment:12 Changed 16 years ago by Peter Kovacs

Description: modified (diff)
Status: newassigned

comment:13 Changed 15 years ago by Alpar Juttner

The changeset [2f64c4a692a8] is a port of Suurballe algorithm. Could anyone review it?

Changed 15 years ago by Alpar Juttner

Attachment: 2f64c4a692a8.patch added

Changed 15 years ago by Peter Kovacs

Attachment: suurb1_39ff10276621.patch added

Changed 15 years ago by Peter Kovacs

Attachment: suurb2_613d47d29dc3.patch added

comment:14 in reply to:  13 ; Changed 15 years ago by Peter Kovacs

Replying to alpar:

The changeset [2f64c4a692a8] is a port of Suurballe algorithm. Could anyone review it?

[39ff10276621] and [613d47d29dc3] contain improvements for [2f64c4a692a8]. The first one just applies the unifier script to the new files (except for the modified Makefile.am files), the second one contains several small doc improvements.

Apart from these changes I think it is okay.

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

Replying to kpeter:

[39ff10276621] and [613d47d29dc3] contain improvements for [2f64c4a692a8]. The first one just applies the unifier script to the new files (except for the modified Makefile.am files),

I would definitely like to avoid the application of the unifier script to all ported tool one by one. It is much preferable to do when all new tools targeting the next release will have been ported.

the second one contains several small doc improvements.

Therefore I rebased [613d47d29dc3] on the top of [2f64c4a692a8], and they both are in the main branch now.

comment:16 Changed 15 years ago by Alpar Juttner

Priority: majorcritical

I think it is really important to port a big chunk of the network flow related tools for the next release.

The question is how strongly these tools depend of map copying (#146).

comment:17 Changed 15 years ago by Peter Kovacs

I think this whole task is really huge. Some algorithms would be very important to have in the 1.1 release, others are not so critical. So I suggest to divide this ticket to more ones.

The mian groups could be:

  • Max. flow (basic algorithms)
    • lemon/elevator.h
    • lemon/edmonds_karp.h
    • lemon/preflow.h
    • test/preflow_test.cc
    • test/preflow_graph.dim
  • Max. flow (special algorithms, using dynamic tree)
    • lemon/dynamic_tree.h
    • lemon/goldberg_tarjan.h
    • lemon/dinitz_sleator_tarjan.h
  • Circulation
    • lemon/circulation.h
  • Min. mean cycle
    • lemon/min_mean_cycle.h
  • Min. cost flow
    • lemon/capacity_scaling.h
    • lemon/cost_scaling.h
    • lemon/cycle_canceling.h
    • lemon/network_simplex.h
    • lemon/min_cost_flow.h
    • lemon/min_cost_max_flow.h
    • test/min_cost_flow_test.cc
    • test/min_cost_flow_test.lgf
    • test/min_cost_flow_test.net

In fact, the dynamic tree structure and the min. mean cycle algorithm are not network flow tools, but they are only used by network flow algorithms.

As you can see many algorithms and tools do not have test files, so we should write more.

I think the basic max. flow algorithms and the circualtion algorithm would be critical to involve in LEMON 1.1, the other tools (max. flow algorithms using dynamic tree, min. cost flow algorithms) could be postponed if it is necessary.

However as soon as the Circulation and the Bellman-Ford algorithm are ported, I can port the min. mean cycle algorithm and all the min. cost flow algorithms quickly and easily (as I'm currently working on them). So it is not a problem if we would like to have them in the 1.1 release.

I do not know exactly how strongly these tools depend on map copying, but I guess that the basic max. flow algorithms don't depend on it at all.

comment:18 in reply to:  17 Changed 15 years ago by Alpar Juttner

Replying to kpeter:

I do not know exactly how strongly these tools depend on map copying, but I guess that the basic max. flow algorithms don't depend on it at all.

Let's start with these, then.

comment:19 Changed 15 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

I've cut the remaining part of this ticket into several follow-ups, see #174, #175, #176, #177, #178, #179 ad #180.

Thus this one can be closed.

Note: See TracTickets for help on using tickets.