"Vesa Karvonen" <vesa_karvonen@hotmail.com> wrote: {snipped throughout}

The design employed by BGL makes it possible to provide faster lookups than what is possible with hash tables. The cost is, as you have noticed, tougher requirements for the client.

That is the conclusion that I am drawing, also.

...

If, instead, it is a synthesized construct for communication between a graph and the algorithm operating over it, why should the client be responsible for its maintenance instead of the framework? What are the advantages of this approach?

The advantage is that the client can choose how nodes are mapped to indices. The client can, in particular, provide a significantly faster mapping method. For example, the color of a node could be stored in the node itself, which would mean that accessing the color property would be a very fast O(1) operation. It could easily be an order of magnitude faster than a hash table lookup.

We�re using the word �color� in an ill-defined context here, but I am assuming that we�re talking about an attribute used to tag a node in calculating chromatic numbers. That said, why would a coloring algorithm operating over the graph need to utilize the mapping of internal indexes to user-defined nodes? Again, this seems parallel to a red-black BST requiring that its value_type know about its color. If I had to write set<propertymap<int,color>> instead of set<int>, I�d feel the same distress. Of course, for things that are natural attributes of a node, like data from which a weight attribute can be generated, there would be no escaping the lookup cost.

It should also be possible for a graph algorithm to internally convert a graph to an isomorphic copy that allows essentially optimal accesses (it should be doable in O(V+E) time and space in most cases). However, the time and space required by the conversion would probably make such a conversion useless except for graph algorithms whose complexity is significantly higher than O(V+E).

That sounds reasonable. I don�t see how it is applicable, though. How does maintaining a mapping between internal and external structures for a public interface hinder internal manipulation?

The disadvantage of requiring only hashing and equality comparison from the client is that sometimes there are significantly more efficient ways to associate information with nodes and the opportunity to take advantage of those more efficient ways is lost.

Uncompromising performance at the expense of clarity or usability is a common feature of C/C++ code. It may be ample justification for the complexity of BGL use � especially since measures of clarity and usability are probably more subjective than measures of performance.

...

This is the type of design issue that I intended to question with my initial post.

Does this answer your question?

I think that it may. Thank you for helping me to reveal some differences between possible approaches. __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/