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

Subject: Re: [Boost-users] [BGL] Finding the descriptor for a given vertex
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-12-30 14:28:14

On Thu, 29 Dec 2011, Kelvin Chung wrote:

> 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.)

You can use the adjacency_list_traits class (documented in the 
adjacency_list documentation) to get the descriptor types to use in your 
bundled property type.

> (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")

That is exactly what it is for -- using your own data structure for 
properties.

-- Jeremiah Willcock