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@osl.iu.edu> 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) _______________________________________________