COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

#323 closed defect (fixed)

Fixes and improvements for Suurballe

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description


Attachments (7)

323-bugfix-c67e235c832f.patch (542 bytes) - added by Peter Kovacs 9 years ago.
323-int-30c77d1c0cba.patch (1.1 KB) - added by Peter Kovacs 9 years ago.
323-rework-ec0b1b423b8b.patch (10.4 KB) - added by Peter Kovacs 9 years ago.
323-fullinit-9a7e4e606f83.patch (6.5 KB) - added by Peter Kovacs 9 years ago.
323-traits-d0408235c756.patch (7.6 KB) - added by Peter Kovacs 9 years ago.
323-bothbranches.bundle (880 bytes) - added by Peter Kovacs 9 years ago.
323-main.bundle (5.5 KB) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 9 years ago by Alpar Juttner

What's this ticket about?

Just a post-it for yourself?

Strange.

comment:2 Changed 9 years ago by Peter Kovacs

I'm working on more changesets to attach here. The ticket was created earlier just because its ID is needed to be put it into the commit logs.

Changed 9 years ago by Peter Kovacs

Changed 9 years ago by Peter Kovacs

Attachment: 323-int-30c77d1c0cba.patch added

comment:3 Changed 9 years ago by Peter Kovacs

[c67e235c832f] is a bug fix, it should be merged into both branches. [30c77d1c0cba] removes the unnecessary integer requirement for length type. It is on the top of the bug fix. It should be merged into the main branch, but it could be merged into branch 1.1, as well.

Changed 9 years ago by Peter Kovacs

Changed 9 years ago by Peter Kovacs

comment:4 Changed 9 years ago by Peter Kovacs

  • [ec0b1b423b8b] improves the implementation and the doc of Suurballe.
  • [9a7e4e606f83] adds a fullInit(s) function to handle multiple targets faster, see #181. A start() function is also added, just for the sake of convenience.

Changed 9 years ago by Peter Kovacs

comment:5 Changed 9 years ago by Peter Kovacs

Status: newassigned

[d0408235c756] adds traits class and named parameters for the following types: FlowMap, PotentialMap, Path, Heap+HeapCrossRef.

Note that this changeset emits a lot of warnings unless it is merged with the heap concept fixes in [50d28aa826bb], see #180.

comment:6 Changed 9 years ago by Peter Kovacs

The default types in the traits class are questionable.

  • Path vs SimplePath (only addBack() function is used)
  • int vs char (or bool?) for the value type of the flow map (it is 0-1-valued)

What do you think?

comment:7 in reply to:  6 ; Changed 9 years ago by Alpar Juttner

Replying to kpeter:

The default types in the traits class are questionable.

  • Path vs SimplePath (only addBack() function is used)

Path don't have to be configurable at all. The class should use the best efficient format internally, then path() should expose expose this. Similarly to the implementation of Dijkstra's corresponding function.

  • int vs char (or bool?) for the value type of the flow map (it is 0-1-valued)

We should choose the best efficient one (I guess it is bool, but who knows...)

Moreover, I can't see much use of making this data type configurable either. (But in contrast with the path type, there is nothing wrong with allowing it).

comment:8 in reply to:  7 Changed 9 years ago by Peter Kovacs

Replying to alpar:

Path don't have to be configurable at all. The class should use the best efficient format internally, then path() should expose expose this. Similarly to the implementation of Dijkstra's corresponding function.

Dijkstra uses a special path storage: paths are not built unless they are queried. However, in Suurballe, the first phase constructs a flow map and the second phase builds paths from that flow map. For this, we use a general path type, e.g. Path or SimplePath. Of course, the following code is valid for all path type:

  AnyPathType p = suurballe.path(0);

However, this code isn't:

  const AnyPathType& p = suurballe.path(0);

In fact, I don't know whether SimplePath is more efficient than Path if you use only addBack() functions.

  • int vs char (or bool?) for the value type of the flow map (it is 0-1-valued)

We should choose the best efficient one (I guess it is bool, but who knows...)

Or the most "natural" one.

Moreover, I can't see much use of making this data type configurable either. (But in contrast with the path type, there is nothing wrong with allowing it).

It is useful only for efficiency reasons.

comment:9 in reply to:  6 ; Changed 9 years ago by Peter Kovacs

Replying to kpeter:

The default types in the traits class are questionable.

  • Path vs SimplePath (only addBack() function is used)
  • int vs char (or bool?) for the value type of the flow map (it is 0-1-valued)

In fact, these questions have already been decided in the former releases. Using the proposed patches, one can modfy these types, but the default values should be the same as in release 1.1.

Well, is there any drawback of the proposed solutions? (They have been waiting here for 5 months!)

comment:10 in reply to:  9 ; Changed 9 years ago by Alpar Juttner

Replying to kpeter:

Replying to kpeter:

The default types in the traits class are questionable.

  • Path vs SimplePath (only addBack() function is used)
  • int vs char (or bool?) for the value type of the flow map (it is 0-1-valued)

In fact, these questions have already been decided in the former releases. Using the proposed patches, one can modfy these types, but the default values should be the same as in release 1.1.

Well, is there any drawback of the proposed solutions? (They have been waiting here for 5 months!)

Yes, they have been waiting. They have been waiting for satisfactory answers to your questions. I.e. they have been waiting waiting for your clever observation above.

comment:11 in reply to:  10 Changed 9 years ago by Peter Kovacs

Replying to alpar:

Yes, they have been waiting. They have been waiting for satisfactory answers to your questions. I.e. they have been waiting waiting for your clever observation above.

And maybe, I have been waiting for someone else to observe this fact instead of me. :) After all, what about applying these changesets and close this ticket and #181, as well?

Changed 9 years ago by Peter Kovacs

Attachment: 323-bothbranches.bundle added

Changed 9 years ago by Peter Kovacs

Attachment: 323-main.bundle added

comment:12 Changed 9 years ago by Peter Kovacs

I attached two bundle files. The first one contains [c67e235c832f] and [30c77d1c0cba], which should be merged into the main branch and into the branch 1.1. The second one contains [ec0b1b423b8b], [9a7e4e606f83], [d0408235c756] and [690da4cfd21b], which should be applied to the main branch only.

comment:13 in reply to:  12 ; Changed 9 years ago by Alpar Juttner

Replying to kpeter:

I attached two bundle files. The first one contains [c67e235c832f] and [30c77d1c0cba], which should be merged into the main branch and into the branch 1.1. The second one contains [ec0b1b423b8b], [9a7e4e606f83], [d0408235c756] and [690da4cfd21b], which should be applied to the main branch only.

Please submit each changeset into trac only once. Giving references to the already uploaded changesets is plenty enough.

[690da4cfd21b] stalked into the bundle file without any discussion. Moreover it contains rather irrelevant changes that already exist in the main branch. I've cleaned it up.

Chgsets [d0408235c756] and [690da4cfd21b] do not compile without merging them into the tip of the main, thus I rebased them to the tip, see [abb95d48e89e] and [9f6ed854d409], reps.

comment:14 in reply to:  13 Changed 9 years ago by Peter Kovacs

Replying to alpar:

Please submit each changeset into trac only once. Giving references to the already uploaded changesets is plenty enough.

I have just noticed that these changesets were not imported to your lemon-chaos repository, so I wanted to help you with these bundles.

[690da4cfd21b] stalked into the bundle file without any discussion. Moreover it contains rather irrelevant changes that already exist in the main branch. I've cleaned it up.

I forgot to attach it separately, and yes, it was not clear enough. I'm sorry.

Chgsets [d0408235c756] and [690da4cfd21b] do not compile without merging them into the tip of the main,

As I wrote it before.

thus I rebased them to the tip, see [abb95d48e89e] and [9f6ed854d409], reps.

Thanks.

comment:15 Changed 9 years ago by Peter Kovacs

I think this ticket can be closed, all proposed changesets went to the corresponding branches.

comment:16 Changed 9 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed
Note: See TracTickets for help on using tickets.