COIN-OR::LEMON - Graph Library

Opened 12 years ago

Closed 11 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)

3774c5a08cb0.patch (29.5 KB) - added by Balazs Dezso 11 years ago.
Port min cost arborescence

Download all attachments as: .zip

Change History (12)

comment:1 Changed 12 years ago by Alpar Juttner

Type: defecttask

comment:2 Changed 12 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:3 Changed 11 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Balazs Dezso

comment:4 Changed 11 years ago by Balazs Dezso

Status: newassigned

Changed 11 years ago by Balazs Dezso

Attachment: 3774c5a08cb0.patch added

Port min cost arborescence

comment:5 Changed 11 years ago by Balazs Dezso

The patch [3774c5a08cb0] contains the port. Maybe it can be renamed to MinCostBranching?. What is your opinion?

comment:6 in reply to:  5 ; Changed 11 years ago by Alpar Juttner

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 in reply to:  6 ; Changed 11 years ago by Balazs Dezso

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 in reply to:  7 Changed 11 years ago by Alpar Juttner

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 Changed 11 years ago by Alpar Juttner

So, shell I put the patch to the main branch "as is"?

comment:10 in reply to:  9 Changed 11 years ago by Balazs Dezso

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 11 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

I added the test file to the cmake config, and pushed it to the main branch. See [7f8560cb9d65].

Note: See TracTickets for help on using tickets.