Re: [Boost-users] [BGL] Finding the descriptor for a given vertex

Subject: Re: [Boost-users] [BGL] Finding the descriptor for a given vertex
From: Kelvin Chung (kelvSYC_at_[hidden])
Date: 2011-12-30 01:38:35

On 2011-12-29 15:00:10 +0000, Nicholas Mario Wardhana said:

> On 29 December 2011 15:16, Kelvin Chung <kelvSYC_at_[hidden]> wrote:
>> Suppose I have the following:
>> 
>> template <class T>
>> class Graph { Â  // Adapter class that I use for my purposes
>> Â  Â  Â  Â typedef typename boost::adjacency_list<boost::vecS, boost::vecS,
>> boost::directedS, T> innerGraph;
>> Â  Â  Â  Â typedef typename boost::graph_traits<innerGraph>::vertex_descriptor
>> VertexDescriptor;
>> 
>> Â  Â  Â  Â innerGraph G;
>> public:
>> Â  Â  Â  Â void addVertex(const T& vertex);
>> Â  Â  Â  Â bool containsVertex(const T& vertex) const;
>> 
>> Â  Â  Â  Â void addEdge(const T& from, const T& to);
>> Â  Â  Â  Â // More stuff here
>> };
>> 
>> The intent of this adapter class is to basically abstract out all the
>> mentions of stuff like the descriptors and such. Â So a good helper function
>> to this end would be a function that retrieves the VertexDescriptor for a
>> given T, if it exists. Â Is there such a function already in the BGL, or do I
>> have to manage that separately (ie. having an external map)?
>> 
>> 
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
> 
> How about storing the descriptor in the T object, by having a member like
> 
> VertexDescriptor descriptor;
> 
> ?
> 
> Constant-time retrieval is guaranteed, but then you have to typedef
> VertexDescriptor in your T. Alternatively, you can have it globally
> defined.

Wouldn't that impose a concept (or interface) requirement on T? (BTW, 
what are the current concept requirements for T?  Does changing the 
second template param to boost::setS to disallow parallel edges also 
implies that T must be less-than comparable?)  Or at least, present a 
chicken-and-egg problem regarding putting my T in a wrapper that also 
stores the VertexDescriptor?  (Not that keeping an external T to 
VertexDescriptor map is any different, mind you, but at least I know 
what the external map means for the concept/interface requirements for 
T.)

(Sometimes the language of the BGL documentation confuses me.  
Especially the fact that "Bundled Properties" seems to be a euphemism 
of "use a data structure that you like")