Opened 11 years ago
Closed 10 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 )
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 11 years ago by
Description: | modified (diff) |
---|
comment:2 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:3 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:4 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:5 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:6 Changed 11 years ago by
comment:7 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:8 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:9 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:10 Changed 11 years ago by
Milestone: | LEMON 1.0 release → Post 1.0 |
---|
comment:11 Changed 10 years ago by
Owner: | changed from Alpar Juttner to Peter Kovacs |
---|
comment:12 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Status: | new → assigned |
comment:13 follow-up: 14 Changed 10 years ago by
The changeset [2f64c4a692a8] is a port of Suurballe algorithm. Could anyone review it?
Changed 10 years ago by
Attachment: | 2f64c4a692a8.patch added |
---|
Changed 10 years ago by
Attachment: | suurb1_39ff10276621.patch added |
---|
Changed 10 years ago by
Attachment: | suurb2_613d47d29dc3.patch added |
---|
comment:14 follow-up: 15 Changed 10 years ago by
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 Changed 10 years ago by
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
Priority: | major → 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
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 Changed 10 years ago by
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
Resolution: | → fixed |
---|---|
Status: | assigned → closed |
Elevator should be conform to the C++ standard. The uninitialized iterator cannot be copied Use -D_GLIBCXX_DEBUG to check conformity