[boost] Re: [BGL] forced client complexity

From: Johnny Yune (prosonance_at_[hidden])
Date: 2004-04-03 08:31:59

"Vesa Karvonen" <vesa_karvonen_at_[hidden]> 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/