Hi Guillaume,

Hi Tiago,

In my opinion, the astar_search function contract could be extended to

accept a set of source vertices instead of a single one, without any

loss of generality.

In my particular need, I search the best path reaching a goal,

considering various start points. The trivial way to do that is:

for each eligible start point:

run astar_search with this start point as 'source'

memorize best path if better than ever

But, the astar_search algorithm, particularly when associated to a

AStarVisitor that build the graph locally to the examined vertices,

tends to limit the combinatorial explosion of searching. So that

iterating over eligible start points is necessarily sub-optimal.

So, currently, I introduce a pseudo-vertex as the source point, which

links to all my real eligible source points for no additional cost, and

benefit from the automatic scope restriction from astar_search which may

directly select the best start point by itself.

This seems to me to be the appropriate solution.

Note that the task being solved is to find the best path to the target

vertex from _either one_ of the available source vertices. The first

variation you proposed finds the best paths from _all_ the available

sources, and you then just find the best among them and discard the

extra information obtained; thus it is certainly an overkill.

Another way to do that (and simplify user code) is to extend the

'source' parameter notion from a single vertex to a set of vertices (in

order to initialize the open vertices list).

You mean essentially to incorporate the "dummy vertex" approach into the

function itself?

Although it could be done, I usually avoid making functions more

complicated than necessary. The task of finding the best path from one

of many candidate sources can be easily solved (for all the search

algorithms) by including a dummy vertex like you did. If this is

implemented for astar, it should also, for completeness, be implemented

in the other search functions as well, since it would be equally useful

there. I'm just not sure if it is worthwhile to modify all these

functions to cover a special case which can be easily solved by the

user. Furthermore I do not like the idea of search functions modifying

the graph, without being explicit about it.

But I will keep this in mind. If I think of a nice way of implementing

this, I will do so. Of course, you may suggest an approach, or even

better, a patch!

Cheers,

Tiago