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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2008-01-17 08:56:39

> Aaron Windsor wrote:
> > 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
>
> On Jan 17, 2008 7:05 AM, Lars-Peter Ellekilde <lpe_at_[hidden]> wrote:
> Hi
> Thanks for the reply. I haven't seen the comment about x86 Linux in the
> code, but guess it very well be my problem.
> The program I am writing constructs a graph with random data, thus it is
> difficult for me to reproduce the error in a small example.
>
> Any good ideas on how best to detect if it enters an infinite loop?
> Would it be possible just to use the visitor and see if the vertex under
> examination is the same as the previous one?

The comment about looping seems to indicate that the A* visitor's
"edge_not_relaxed" method will be repeatedly called. You may want to
stick a std::cout in this method and see what's happening when the
looping occurs - I don't know whether it will loop on the same edge or
on a sequence of edges, but you may be able to short-circuit the
search there.

Regrds,
Aaron