Boost logo

Boost :

From: Andrew Sutton (asutton_at_[hidden])
Date: 2007-06-17 21:59:54

> Glad to see that you are making progress on this problem - I think
> improving the usability of the BGL for the casual user is a very
> worthwhile project.
> <snip>


Interesting ideas, but maybe a little overkill for the scope of my
work :) - I'm not touching any of the existing classes anyways. I
think however, that your suggestions make vertex/edge indexing
integral to the BGL - which I'm not convinced it should be.

The more I think about it, the more it feels like the indexing stuff
is there because it's declaratively harder to do without it.
Conceptually, graph algorithms need to access properties of vertices
and edges in constant time. When we use vecS as a storage selector,
this is trivially done since the descriptors are literally the
indices. This makes the accessors *really* trivial and plainly
constant time - unfortunately also highly unstable under destructive
operations. To be honest, the indexing really feels like more of a
crutch than anything else.

I think an ultimate goal - and this is also well beyond the scope of
my work this summer - might be to completely eliminate any dependence
on indexing for property accessors. We might be able to use hash_maps
as a viable alternative since realistically, descriptors are integral
types and assigned in such a way that hash collisions should be very

There are, unfortunately as I see it, two problems with this. First,
there's substantial momentum built around the current model
(indexing, etc.). The second, probably more impractical, is the
commitment of users to the current design (i.e., backwards
compatibility). I don't know how practical it would be to introduce
and implement such a large change into the current codebase - even if
people did agree that it would be a good idea.

Ironically, this may be a great argument for independent library

Andrew Sutton

Boost list run by bdawes at, gregod at, cpdaniel at, john at