Boost logo

Boost :

From: Johnny Yune (prosonance_at_[hidden])
Date: 2004-04-02 20:01:07

Jeremy Siek" <jsiek_at_[hidden]> wrote in message news:
> 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?

That probably restates my question more succinctly
than I would be able to.
> The BGL graph interface was designed so that many
> graph data structures could be uniformly
> It sounds like the data structure that you are most
> with is where each node is an object, and the
> structure of the graph is represented with pointers.

For my naïve endeavors, I most often use adjacency

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

That seems like an intuitive way for the back-end to
work. Why should I, as a client, need to concern
myself with those details, though? I’m sorry if I
sound critical, but I just don’t understand. To me,
it feels like using some sort of balanced tree
container and having to concern myself with whether a
node is red or black – why do I need to know?
> The vertex_descriptor abstraction provides an opaque
> to a "vertex", whatever that may be for the data
> For one graph type that may be node*, for another
> The purpose of the property map interface is to
provide a
> uniform way for an algorithm to access data that is
> with a node or edge. Again, there are many ways that
> 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
> 3. Data is in a hash table, somehow keyed on the
> Now, the problem you're pointing out is that the
> 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)

Actually, what I really wanted clarification on was
why the task of managing this mapping was left to the
client instead of the underlying graph structure. The
differences in syntax, above, are only indications of
my confusion about the semantics. To wit, given your
examples, I wouldn’t necessarily expect v->color to
have anything to do with the color_map. v->color
looks like a property of a vertex, while
get(color_map, v) looks like a property of a graph.

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

Well, this does make things a lot more complex. The
need for such mappings is quite clear to me – the need
for the client to “set them up” as opposed to the
graph is unclear to me, though. If I were to ask an
algorithm to generate a chromatic number over a graph,
I could envision having a property map of some
possible coloring returned to me. Why I would have to
set one up or pass one in, though, I am unclear on.

In reviewing my post, I am realizing just how astute
you were to identify the property map as a major
source of confusion for me – I am only beginning to be
able to articulate why it “feels” unnatural for me. I
guess the big question, then, is “why use property
maps instead of functors?” Would not functors also
allow communication between arbitrary user-defined
vertex types, the graphs that store them (even if only
by lookup mapping to some arbitrary internal data
type), and the algorithms that operate over them? My
gut tells me that it is so. It also seems like using
functors would be a natural way to help preserve
clarity – if an algorithm requires that every vertex
have an index or a name or a color et cetera, mightn’t
it be natural to pass in a functor that can extract,
generate, or synthesize the required property? Such
functors may also be good candidates for being
defaulted, which could significantly help to simplify
client code. Isn’t that, after all, the model that
our beloved standard library follows with its

Thanks, again, for entertaining my questions. I am
highly pleased to be soliciting rationale and intent
instead of the rabid defensiveness or dismissal that I
probably deserve.

Do you Yahoo!?
Yahoo! Small Business $15K Web Design Giveaway

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