Port network flow algorithms

[Alpar Juttner]

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

[Balazs Dezso]

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

[Alpar Juttner]

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

[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.

[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.

[Alpar Juttner]

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).

[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.

[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.

[Alpar Juttner]

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.