Re: [boost] Re: Re: [BGL] forced client complexity

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-04-02 10:44:52

Hi,

On Apr 2, 2004, at 6:48 AM, Provisional Dissonance wrote:
> of the framework?  What are the advantages of this
> approach?  What are the disadvantages of simplifying
> things for the client?  This is the type of design
> issue that I intended to question with my initial
> post.

So I think your question can be boiled down to two
questions, why does the BGL use vertex descriptors?
and why does the BGL use property maps?

The BGL graph interface was designed so that many different
graph data structures could be uniformly manipulated.
It sounds like the data structure that you are most familiar
with is where each node is an object, and the connecting
structure of the graph is represented with pointers. However,
another important graph data structure is the adjacency list
representation, where there are no node objects. Instead there
is just an array of lists of integers. An integer n is associated
with each node, and the out-edge list for a node is at offset
n in the array.

The vertex_descriptor abstraction provides an opaque handle
to a "vertex", whatever that may be for the data structure.
For one graph type that may be node*, for another int.

The purpose of the property map interface is to provide a
uniform way for an algorithm to access data that is associated
with a node or edge. Again, there are many ways that such
an association can be implemented, with various time, space,
and convenience tradeoffs. Here are some examples:

1. Associated data is a member of a struct
2. Data is in an array, organized by vertex index offset
3. Data is in a hash table, somehow keyed on the vertex.

Now, the problem you're pointing out is that the extra
level of indirection of the property map makes the
syntax rather unwieldy for accessing data. For
example, instead of:

v->color

one must write:

get(color_map, v)

(not to mention the trouble of setting up the color_map
  to begin with)

Perhaps with some cleverness, we can get closer to
the syntax of v->color, while retaining the flexibility
an uniformity provided by property maps? I'll put
my thinking cap on.

Cheers,
Jeremy

_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Student, Indiana University Bloomington
Graduating in August 2004 and looking for work
C++ Booster (http://www.boost.org)
_______________________________________________