COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 8 years ago

#323 closed defect (fixed)

Fixes and improvements for Suurballe

Reported by: kpeter Owned by: kpeter
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 kpeter 9 years ago.
323-int-30c77d1c0cba.patch (1.1 KB) - added by kpeter 9 years ago.
323-rework-ec0b1b423b8b.patch (10.4 KB) - added by kpeter 9 years ago.
323-fullinit-9a7e4e606f83.patch (6.5 KB) - added by kpeter 9 years ago.
323-traits-d0408235c756.patch (7.6 KB) - added by kpeter 9 years ago.
323-bothbranches.bundle (880 bytes) - added by kpeter 8 years ago.
323-main.bundle (5.5 KB) - added by kpeter 8 years ago.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 9 years ago by alpar

What's this ticket about?

Just a post-it for yourself?

Strange.

comment:2 Changed 9 years ago by kpeter

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 kpeter

Changed 9 years ago by kpeter

comment:3 Changed 9 years ago by kpeter

[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 kpeter

Changed 9 years ago by kpeter

comment:4 Changed 9 years ago by kpeter

  • [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 kpeter

comment:5 Changed 9 years ago by kpeter

  • Status changed from new to assigned

[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 follow-ups: Changed 9 years ago by 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)

What do you think?

comment:7 in reply to: ↑ 6 ; follow-up: Changed 8 years ago by alpar

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 8 years ago by kpeter

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 ; follow-up: Changed 8 years ago by 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!)

comment:10 in reply to: ↑ 9 ; follow-up: Changed 8 years ago by alpar

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 8 years ago by kpeter

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 8 years ago by kpeter

Changed 8 years ago by kpeter

comment:12 follow-up: Changed 8 years ago by 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.

comment:13 in reply to: ↑ 12 ; follow-up: Changed 8 years ago by alpar

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 8 years ago by kpeter

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 8 years ago by kpeter

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

comment:16 Changed 8 years ago by alpar

  • Resolution set to fixed
  • Status changed from assigned to closed
Note: See TracTickets for help on using tickets.