Re: [boost] [graph] managed vertex indexing

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>

Aaron,

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

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

Andrew Sutton
asutton_at_[hidden]