Re: [boost] BGL limitations (?) and possible solutions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-14 12:49:50

----- Original Message -----
From: "Jeremy Siek" <jsiek_at_[hidden]>
To: "boost" <boost_at_[hidden]>
Sent: Monday, January 14, 2002 12:21 PM
Subject: Re: [boost] BGL limitations (?) and possible solutions

> On Tue, 8 Jan 2002, David Abrahams wrote:
>
> david.> Suppose I want to find the length of the shortest path from A to B
in an
> david.> arbitrary graph. I would normally use a breadth-first search, and
store
> david.> intermediate distances to each active vertex alongside its
descriptor in the
> david.> algorithm's Queue. AFAICT, the BGL approach makes me pay for a
property map
> david.> that can store the distances from A to X for any arbitrary vertex
X. This
> david.> could be fixed, however, by allowing users to store some other
type in the
> david.> buffer, and modifying some of the visitor interfaces to give them
access to
> david.> these objects. Does this make sense, or have I overlooked
something obvious?
>
> What exactly is the problem you are trying to solve? Are you trying to
> optimize space? Or are you tring to make the interface simpler?

Yes, and yes.

> Also, note that at the end of the algorithm, the Queue is empty, so if a
> user wanted to know the distances after the algorithm is finished, they
> would not have access to that information if it was stored on the Queue.

I was hoping to collect the information when B is discovered.

> david.> Secondly, (and I know we've discussed this in the past), what
about
> david.> terminating the search as soon as the path is found? I guess I
could give
> david.> the visitor access to the Queue, and flush it when I've found what
I'm
> david.> looking for, but it will still go on to explore the rest of the
edges on the
> david.> current node. Is there a reason not to give visitors a return
value and
> david.> check that? Won't inlined visitors that always return false cause
the check
> david.> to be optimized away?
>
> How about instead pass the color map into the visitor, and assign black to
> vertices at the appropriate time?

Rich points out that I will still deal with everything left in the queue.
It's easy enough to clear the queue on finish_vertex (except that the stupid
queue interface doesn't include clear()).

At this point I've lost track of exactly what I was doing when I wrote this,
so please don't waste any pf your time trying to solve these problems for
me. My only point was that there are a number of obvious optimizations and
simplifications which are available to hand-written graph algorithms, which
I can't take advantage of with BGL. Just for example, the requirement that
you can get the source vertex for any edge is an unneccessary imposition
which imposes the cost of an extra vertex descriptor in each edge.

-Dave