Hi Guillaume,

On 04/21/2012 11:19 AM, Guillaume Lemaître wrote:

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

-- Tiago de Paula Peixoto tiago@skewed.de