Boost logo

Boost Users :

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-06-14 13:46:40

On Jun 14, 2005, at 9:08 AM, martin f krafft wrote:

> also sprach David Abrahams <dave_at_[hidden]>
> [2005.06.14.1532 +0200]:
>> Don't look at the code; read the documentation. And don't do any
>> casting.
> Well, the documentation does not tell me anything about the edge
> descriptors

The quick tour describes the descriptors:

> or the get_property method...

The use of property maps is described here:

> It feels more proper to me in the context of my needs. I fail to see
> the object-orientedness of the BGL, really. I know that OO is often
> misunderstood and people attribute magic to it that it does not
> have. However, it does allow you to deal with objects and treat them
> as black boxes.

The BGL isn't (and isn't intended to be) an object-oriented library.
It's a generic library, and while OOP and generic programming share
some common notions of abstract data types and polymorphism, they are
different programming paradigms with different design strategies.

> It's all a question of perspective. The BGL treats the graph as the
> centre of the world and all algorithms start from it. I would like
> to be able to assume the perspective of a single node or edge and
> see the world from this point of view, ideally ignoring the fact
> that a graph exists per se.

One of the strengths of the generic programming paradigm is that you
can force a generic library to look at things the way you do. So if you
have a data structure that works well for your world-view, you can
write some simple adaptation code and then apply generic algorithms.
Examples in the BGL include reverse_graph (reverses the direction of
edges), filtered_graph (filters out vertices and edges), and the LEDA
adaptors (makes LEDA graphs work with BGL algorithms).

>>> Thanks for any comments, thoughts, suggestions, pointers.
>> It sounds to me like, if a Node really needs to have access to its
>> edges, *and* if you only are only looking at the BGL for its graph
>> representation and not for its algorithms, that the BGL can't help
>> you.
> Well, that's part of the reason. The other part was that I wanted to
> stay compatible to the BGL just in case we need graph algorithms
> later on. After all, we are in research where those unexpected needs
> arise all the time.

This you can definitely do. The LEDA adaptors are perhaps the best
example within the BGL.

>> It's pretty easy to build the kind of graph structure you want by
>> hand,
> The other reason is that your claim is not true. It *sounds* easy,
> and it's really easy to get wrong. I tried several days before
> giving in and looking at the BGL.
> Then again, my implementation tried to be generic wrt to the types
> you store for each edge or node *and* to avoid polymorphism for
> space efficiency reasons. This led me into several problems [0],
> which I was hoping to evade with the BGL.
> 0.

Your post on c.l.c++.m actually reminded me of the other reason that
properties can't be embedded into the vertex and edge descriptors:
circular references. In the BGL adjacency_list, vertex descriptors
can't have property type information in them, because the property type
might rely on the type of the vertex descriptor.

So, I think there's a fundamental issue here with an OO design for
graphs. The Vertex type needs to know the Edge type (so that one can
enumerate out-edges) and the Edge type needs to know the Vertex type
(so we get can source/target information). We can break the circular
dependency by adding another layer of abstraction (using pointers to
edges/vertices or abstract base classes), but that layer of abstraction
makes our solution less efficient. The BGL descriptors get around this
problem by leaving the information connecting vertices and edges in the
graph type. So when you write, e.g., g[e].weight = 17.0, "e" does not
know the property type but "g" does. If we try to take out the graph
type and put the property information in e (so that we could write,
e.g., "e->weight = 17.0"), we reintroduce the circular dependency.

So, here's how I see it. You can definitely write your own
(non-generic) graph type however it makes the most sense for your
application. Then if you want to use BGL algorithms, you can write the
interface code a la the LEDA adaptors. If you try to make that graph
type too generic, you're going to run into the circular reference
problem again. Or, you could use the BGL's graph types, which may not
fit as cleanly in your application but are already implemented and play
nicely with the rest of the BGL.


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at