Boost logo

Boost :

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-04-05 13:26:44

Hi Doug,

On Apr 5, 2004, at 11:57 AM, Douglas Paul Gregor wrote:

> Hi Jeremy,
> On Mon, 5 Apr 2004, Jeremy Siek wrote:
>> Hi Guys,
>> Here's some issues with this idea:
>> Currently the vertex_descriptor for adjacency_list has no
>> property-related type stuff in it, which allows
>> adjacency_list_traits to work... that is, it is possible
>> to determine the vertex_descriptor type without knowing the type of
>> the
>> vertex properties. This is important, for example, if you want an
>> internal property containing a vertex descriptor (this is a circular
>> dependency).
> If we ensure that naming an adjacency_list does not require
> instantiation
> of the City class, there is no problem, e.g.,
> class City;
> class Highway;
> typedef digraph<City, Highway> Map; // or an adjacency_list; no matter
> class City
> {
> public:
> graph_traits<Map>::vertex_descriptor rival;
> };
> class Highway
> {
> graph_traits<Map>::edge_descriptor other_direction;
> };
> Since the descriptors will be pointers, I _think_ we can be careful
> not to
> instantiate City and Highway within graph_traits. Worst case, we end up
> using a scoped_ptr<adjacency_list<...> > so that instantiating
> digraph<...> does not instantiate adjacency_list.

Okay, I can see how that might work.

>> 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.
>> Do you see solutions to these problems?
> Not this one. Do you really think this extra overhead is going to sink
> the
> idea?

Well, it's a pretty major overhead. We're talking an extra load from
every time you want to do anything with a vertex descriptor. For the
graph structures this is not significant, but this would change the fast
graph structures into slow ones.

Another idea I had was to make vertex_descriptor some kind of pointer
that defined operator-> to return City*.


Jeremy Siek <jsiek_at_[hidden]>
Ph.D. Student, Indiana University Bloomington
Graduating in August 2004 and looking for work
C++ Booster (

Boost list run by bdawes at, gregod at, cpdaniel at, john at