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

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:

        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