[boost] Re: Re: Re: Re: Re: [BGL] forced client complexity

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-04-07 06:35:41

Hi Jeremy,

>> 1. Use pointers and bear this overhead
>> 2. Store cached value of index inside vertex_descriptor, as you
>> suggest in
>> the other post. In this case we have space overhead.
> 
> True, though vertex_descriptor's are not stored in memory very often...
> usually appear as local variables, so the space is just consuming more
> registers.

Or stack space, but anyway, local variables can be optimized just fine by
compiler. 

I'm not sure how ofter vertex descriptor is stored, but sometimes it is. For
example, the predecessor map in depth_first_search.

Maybe, if we really go for convenience, we can create 'vertex' class which
is not so efficient but user friendly, and still retain vertex_descriptor
for performance critical parts.

The vertex would keep vertex_index, provide access to the 'primary vertex
data' (e.g. City), and also provide access to other properties. There also
would be a method to get 'vertex', given vertex_descriptor.

Two classes for the same concept might cause user confusion, but is there
are way to get both efficiency and convenience?

>> So, it seems we can't have nice-for-users 'v->value' or *v syntax
>> without
>> overhead. It's the question which kind of overhead is better.
>>
>> BTW, what about vertex_descriptor stability. If we use vector for
>> storage,
>> it means the addresses can change when we *add* vertex, which would
>> invalidate already stored vertex descriptors. Does this mean we need
>> to use
>> list/deque for the 'easy-to-use' graph type?
> 
> That's a good question. Invalidation is certainly not user friendly.

Then, we either use listS for user-friend graph, or use the vertex type
which stores vertex_descriptor internally. 

> BTW, there's another issue with the idea of automatically assigning
> indices
> when VertexList!=vecS. If we want to make sure the indices stay in the
> range [0,num_vertices(g)) in the face of adding and removing vertices,
> then
> there will be a price to pay in terms of renumbering vertices or
> recycling indices.

Yes, I think I've talked about this last time the auto-number issue was
raised. But do we have a choice? Is it practical to except that user will
do renumbering/recycling himself? Besides, the price for recycling is just
extra vector<int>, which is not much compared with all the other
bookkeeping.

- Volodya