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