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)
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
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: ↓ 14 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: ↓ 15 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: ↓ 18 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
Elevator should be conform to the C++ standard.
The uninitialized iterator cannot be copied
Use -D_GLIBCXX_DEBUG to check conformity