Re: [Boost-users] graph peculiarities

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-03-14 16:46:03

On Mar 14, 2005, at 1:21 PM, Arias Brent-P96059 wrote:

> I've been looking over the graph library, and have found it curiously 
> designed.  I was hoping someone could provide a brief comment on the 
> rationale of the design (something I didn't spot in the 
> documentation).  For example, consider the adjacency_list:
>
> adjacency_list<OutEdgeList, VertexList, Directed, VertexProperties, 
> EdgeProperties, GraphProperties, EdgeList>
>
> I would have thought that the "VertexList" would be templated to 
> permit me to add whatever kind of node I'd like, something like this:
>
> adjacency_list<listS, vecS<myType>, bidirectionalS>
>
> But instead, there is a rather elaborate process of creating a user 
> defined "property" and installing that property.  What was the 
> rationale for that "install property" approach, rather than just a 
> templated parameter approach (as I suggested above)?

The "install property" approach has some advantages when creating 
property maps for internal properties. For instance, you can determine 
if there is an "edge_weight" property and use it, without poking into 
the user-supplied type for the edges. Additionally, the use of member 
pointers to create property maps (as is done for bundled properties) 
does carry a small performance penalty (that can be eliminated with 
some effort on the user's part).
I don't know the rationale for the original design, but I will also 
note that bundled properties don't (and can't) work on Visual C++ 6.0, 
a compiler that had to be supported when the BGL was released.

That said, we tend to like bundled properties better.

> Even with the improvement with the new "bundled properties" approach 
> of 1.32.0, I find myself still asking the same or similar questions.  
> For example, after an adjacency list is created, why do I need to 
> access the properties of the nodes (bundled or not), with 
> vertex_descriptors?  I mean, for example, the "std::map<string, int>" 
> type doesn't require that I make a seperate "vertex_descriptor" or 
> "definition_descriptor" to access an entry in the map.  Certainly 
> there was some rationale behind this "vertex descriptor" approach - 
> does anyone know what it was?

I'm not sure the std::map<string, int> analogy holds up well, because 
accessing the int for a given string requires logarithmic time, which 
would not be acceptable for a graph. Using vertex descriptors allows 
the library to reference vertices without regard to their storage (or 
storage of their properties). What were you expecting instead of vertex 
descriptors?

        Doug