[boost] Re: [BGL] forced client complexity

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2004-04-02 10:14:45

Provisional Dissonance:
>What I was looking for, really, was dialog on existing design
>strategies. It sounds like your issues with property maps mirror my
>confusion with the library design, though. While I can fully appreciate
>the desire to write generic code, it feels like BGL has pushed the
>complexity of creating and enforcing coupling between the generic
>graph/node/visitor/algorithm/etc onto the client. [...]

A graph algorithm must be able to associate information on the elements of
the graph. For instance, depth-first search needs to know whether it has
already discovered a specific node or not (and more).

In the graph utilities we implemented as part of a school project in Java,
we basically relied on the hashCode() and equals() methods that every Java
Object provides. The algorithm templates then internally use HashMaps for
associating information on node and edge objects. This means that each
time an algorithm needs to access some information (that the algorithm
requires internally) on a node, a hash table lookup is performed. Assuming
a good hash function, hash table lookups are O(1), but they are still
slower than a direct array accesses, or accessing a member of a structure.

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.

[...]
>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.

>What are the disadvantages of simplifying things for the client?

The minimal information needed by graph algorithms, assuming best
asymptotic complexity guarantees are desired, is that the client provides
hashing and equality comparison functions for nodes and edges.

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.

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).

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

Does this answer your question?

Regards,
  Vesa Karvonen

_________________________________________________________________
MSN 8 helps eliminate e-mail viruses. Get 2 months FREE*. 
http://join.msn.com/?page=features/virus