Opened 16 years ago
Closed 15 years ago
#60 closed task (fixed)
Port min cost arborescence algorithm
| Reported by: | Alpar Juttner | Owned by: | Balazs Dezso |
|---|---|---|---|
| Priority: | major | Milestone: | LEMON 1.1 release |
| Component: | core | Version: | |
| Keywords: | Cc: | ||
| Revision id: |
Description
The following files are affected.
- lemon/min_cost_arborescence.h
- test/arborescence_test.cc
Attachments (1)
Change History (12)
comment:1 Changed 16 years ago by
| Type: | defect → task |
|---|
comment:2 Changed 16 years ago by
| Milestone: | LEMON 1.0 release → Post 1.0 |
|---|
comment:3 Changed 16 years ago by
| Owner: | changed from Alpar Juttner to Balazs Dezso |
|---|
comment:4 Changed 15 years ago by
| Status: | new → assigned |
|---|
Changed 15 years ago by
| Attachment: | 3774c5a08cb0.patch added |
|---|
comment:5 follow-up: 6 Changed 15 years ago by
The patch [3774c5a08cb0] contains the port. Maybe it can be renamed to MinCostBranching?. What is your opinion?
comment:6 follow-up: 7 Changed 15 years ago by
Replying to deba:
The patch [3774c5a08cb0] contains the port. Maybe it can be renamed to MinCostBranching?. What is your opinion?
Please ask an expert or google which one is the more widely accepted name so that I can merge it into the main branch.
comment:7 follow-up: 8 Changed 15 years ago by
Replying to alpar:
Replying to deba:
The patch [3774c5a08cb0] contains the port. Maybe it can be renamed to MinCostBranching?. What is your opinion?
Please ask an expert or google which one is the more widely accepted name so that I can merge it into the main branch.
At first look, both names are conventional, the arborescence can be found easier, because the branching name can be found in other contexts also. As I remember, there is a slight difference between the names, actually the arborescence has exactly one root, while the branching can have multiple roots. Furthermore, the algorithm is discovered independently by Liu and Chu, and Edmond, the titles of the articles are accordingly "On the shortest arborescence of directed graphs" and "Optimum branchings".
comment:8 Changed 15 years ago by
Replying to deba:
At first look, both names are conventional, the arborescence can be found easier, because the branching name can be found in other contexts also. As I remember, there is a slight difference between the names, actually the arborescence has exactly one root, while the branching can have multiple roots. Furthermore, the algorithm is discovered independently by Liu and Chu, and Edmond, the titles of the articles are accordingly "On the shortest arborescence of directed graphs" and "Optimum branchings".
What to do then? Shell we keep using "arborescence"?
comment:9 follow-up: 10 Changed 15 years ago by
So, shell I put the patch to the main branch "as is"?
comment:10 Changed 15 years ago by
Replying to alpar:
So, shell I put the patch to the main branch "as is"?
Yes, in my opinion it can go into the main branch. The arborescence name is suitable for the algorithm.
comment:11 Changed 15 years ago by
| Resolution: | → fixed |
|---|---|
| Status: | assigned → closed |
I added the test file to the cmake config, and pushed it to the main branch. See [7f8560cb9d65].
Port min cost arborescence