From: Johnny Yune (prosonance_at_[hidden])
Date: 2004-04-03 08:31:59
"Vesa Karvonen" <vesa_karvonen_at_[hidden]> wrote:
> 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.
Were using the word color in an ill-defined context
here, but I am assuming that were 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>,
Id 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 dont 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
> >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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk