Re: [Boost-users] [BGL] overlaying a graph-like structure

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

also sprach David Abrahams [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: http://www.boost.org/libs/graph/doc/quick_tour.html

or the get_property method...

The use of property maps is described here: http://www.boost.org/libs/graph/doc/using_property_maps.html

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. http://xrl.us/gev3

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