Re: [boost] BGL experience report and question

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-10 21:41:21

Hi Rich, thanks for your reply...

----- Original Message -----
From: "Lie-Quan Lee" <llee_at_[hidden]>

> Hi Dave,
>
> > It is clearly an MSVC problem. My point about practicality is that I
could
> > have solved the same problem more quickly for /any/ of the 5 compilers
I'm
> > targeting by writing a custom breadth-first-search. For the library to
be
> > effective for most problems, it has to be more accessible than
handwritten
> > approaches.
>
> I am thinking about to change the way about color in breadth_frist_visit
> so that generalized color can be used without hack.

Sorry, what do you mean by that? Are you referring to my generational
coloring scheme?

> As to stopping
> breadth-first-search as soon as some conditions satisfies, currently we
> did not have a good solution yet. -- Your idea about flushing queue is
> interesting, but there are several unknown issues such as who does the
> flushing and where the flushing happened.

Jeremy emailed me the idea of modifying the property map so every node is
reported to be black. I don't know whether that's effective or not.

> > Actually, it's not an A* search that I need. From reviewing my search
> > algorithms, it looks like I want something more like best-first search.
I
> > don't think dijkstra's algorithm can be made to do that, can it?
> >
>
> I think dijkstra's algorithm can do something like uniform cost search.

I'm not sure that is related to best-first, is it?
Best-first has very different qualities from dijkstra. For example, the cost
of the path to date is irrelevant; you only care about the estimate of the
length to the goal (which, BTW, is not something I see a provision for in
any of the BGL algorithms). It's really a heuristic search.

> You can construct your search with mutable_queue

Where is mutable_queue documented?

> and
> breadth_first_visit. The queue type in the breadth_first_visit is a
> template. For normal Breadth-first search, it is boost::queue. For
> Dijkstra' shortest path, it is a mutable_queue.

I think I might want a breadth-first visit with a simple priority queue with
vertices rated on distance-to-goal. Wouldn't that do best-first?

-Dave