Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at