Re: [Boost-users] graph peculiarities

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

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

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