Fixes and improvements for Suurballe

[Alpar Juttner]

What's this ticket about?

Just a post-it for yourself?

Strange.

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

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

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

[Peter Kovacs]

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

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

[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).

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

[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!)

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

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

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

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

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

[Peter Kovacs]

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