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

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

Hi Jeremy,

> vertex_descpriptor's are handles... passed by value. You would
> not want the City object copied, so the vertex descriptor would
> be a pointer to some object that inherits from City. However,
> dereferencing this pointer will add overhead to the execution
> time, especially in the case when a vertex_descriptor would
> have just been an int.

It's not always overhead. Say vertex_descriptor is int. When you want to
traverse out edges you need to access element of the vector which stores
adjacency structure and then iterate over it.

If vertex_descriptor is pointer, you'd just directly get adjacency
structure, and that's likely to be faster.

In the case of accessing property map by index, we indeed get some overhead
for dereferencing.

But really, we've got only two variants:
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.

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?

- Volodya