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