COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 10 years ago

#47 closed task (fixed)

Port network flow algorithms

Reported by: alpar Owned by: kpeter
Priority: critical Milestone: LEMON 1.1 release
Component: core Version:
Keywords: Cc:
Revision id:

Description (last modified by kpeter)

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 10 years ago.
suurb1_39ff10276621.patch (5.4 KB) - added by kpeter 10 years ago.
suurb2_613d47d29dc3.patch (15.5 KB) - added by kpeter 10 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 10 years ago by alpar

  • Description modified (diff)

comment:2 Changed 10 years ago by alpar

  • Description modified (diff)

comment:3 Changed 10 years ago by alpar

  • Description modified (diff)

comment:4 Changed 10 years ago by alpar

  • Description modified (diff)

comment:5 Changed 10 years ago by alpar

  • Description modified (diff)

comment:6 Changed 10 years ago by deba

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

comment:7 Changed 10 years ago by alpar

  • Description modified (diff)

comment:8 Changed 10 years ago by alpar

  • Description modified (diff)

comment:9 Changed 10 years ago by alpar

  • Description modified (diff)

comment:10 Changed 10 years ago by alpar

  • Milestone changed from LEMON 1.0 release to Post 1.0

comment:11 Changed 10 years ago by alpar

  • Owner changed from alpar to kpeter

comment:12 Changed 10 years ago by kpeter

  • Description modified (diff)
  • Status changed from new to assigned

comment:13 follow-up: Changed 10 years ago by alpar

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

Changed 10 years ago by alpar

Changed 10 years ago by kpeter

Changed 10 years ago by kpeter

comment:14 in reply to: ↑ 13 ; follow-up: Changed 10 years ago by kpeter

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 10 years ago by alpar

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 10 years ago by alpar

  • Priority changed from major to critical

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 follow-up: Changed 10 years ago by kpeter

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 10 years ago by alpar

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 10 years ago by alpar

  • Resolution set to fixed
  • Status changed from assigned to closed

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.