Re: [Boost-users] BGL A-star does not terminate

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2008-01-16 21:48:40

On Jan 15, 2008 2:13 AM, Lars-Peter Ellekilde <lpe_at_[hidden]> wrote:
> Hi
> I have been trying to use the a* implementation in BGL to do a shortest
> path search in en undirected graph. In my application I can not
> guarantee that the graph only contains a single connected components,
> thus a solution may not always exist. Given a query where start and goal
> are in two different components the a* algorithm appears to loop forever.
>
> Is this expected behavior or does it indicate that I might be using it
> wrong somehow? If it is expected, what will be the best way to make the
> algorithm terminate and indicate there is no solution (perhaps I use the
> visitor for this purpose).
>
> Best regards and thanks
> - Lars-Peter

Hi Lars-Peter,

Can you give more information about the case were the implementation
appears to loop forever? What platform are you using? Do you have a
relatively small example that causes it to loop? There's a note in the
code that mentions a case where the implementation can loop on x86
Linux.

The generally accepted way to break out of any BGL traversal early is
to have the visitor throw an exception, so if you have an easy way of
detecting that you won't be able to find the goal at all, you may want
to consider this approach.

Regards,
Aaron