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

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 
memory
every time you want to do anything with a vertex descriptor. For the 
slow
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 
proxy
that defined operator-> to return City*.

Cheers,
Jeremy

_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Student, Indiana University Bloomington
Graduating in August 2004 and looking for work
C++ Booster (http://www.boost.org)
_______________________________________________