21 Apr 2012 11:19

## A* search extension

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

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

What do you think?

Regards,
```

24 Apr 2012 11:10

### Re: A* search extension

```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
```

25 Apr 2012 11:00

### Re: A* search extension

```  Tiago,

I totally understand your reasons for choosing not to change the current
interface at this time being, and respect your decision.

Regards,

Guillaume

--
View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/A-search-extension-tp3927853p3937670.html
Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
```

Gmane