Re: [boost] BGL experience report and question

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-10 17:42:48

----- Original Message -----
From: "Lie-Quan Lee" <llee_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Thursday, January 10, 2002 4:47 PM
Subject: Re: [boost] BGL experience report and question

> On Thu, 2002-01-10 at 15:39, David Abrahams wrote:
> > Ah, the attachment bug again!
> >
> > Here's the message:
> > -------
> > After lots of work, I managed to get MSVC to ICE on my little graph
example
> >

>
> If this is not MSVC problem, what is it? :-)

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.

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

> BTW, in line 256, I believe this pointer cannot be used int friend
> function. Fix that and give a shot. It should be fine to compile with
> MSVC.

MSVC, like many other compilers, erroneously fails to instantiate those
inline friend functions unless used, so nothing was detecting it.

> > My impression (this is the 2nd time I've used it) is that BGL is a tour
de force of generic programming, but it needs work to make it a practical
tool. I don't say this just because of the MSVC problem, but because of all
the problems I have had getting to this point, especially missing
documentation and the inability to take advantage of obvious optimizations.
> >
> > That said, I want to give it one more shot. I just realized that I can't
represent my problem with an in-memory graph: what I really need is an A*
search of a state space. I've never tried to apply BGL to that sort of
problem. Are there any examples around?
>
> I did not see any example yet. If you have out-of-memory graph
> conforming to what BGL algorithms requre, I will expect BGL algorithms
> can be applied on to that graph.

Oh, I'm sure it can. However, I'm not even sure that you have the algorithm
I want.

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?

-Dave