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