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

From: Douglas Paul Gregor (gregod_at_[hidden])
Date: 2004-04-05 11:57:21

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.

> 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?

        Doug