Re: [boost] BGL experience report and question

From: Lie-Quan Lee (llee_at_[hidden])
Date: 2002-01-10 21:26:30

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

> > With MSVC6 in mind, you cannot use the version of breath_first_visit
> > with named function parameters (for God-know-only reasons). So change
> > the call to breadth_first_visit in your code to the following:
> >      boost::queue<vertex> q;
> >     breadth_first_visit(
> > g, &*vertices().find(source), q,
> > bfs_visitor<null_visitor>(), color
> > );
> 
> Close; I need a queue<vertex const*>, but yes, it now compiles. Thank you!

Great!

> 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.
You can construct your search with mutable_queue 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. 
 
-- 
Lie-Quan Lee (AKA: Rich Lee)