Boost logo

Boost Users :

From: David Abrahams (dave_at_[hidden])
Date: 2005-06-14 15:59:14

martin f krafft <madduck_at_[hidden]> writes:

>> > In the context of my application, I know have two options: adopt the
>> > graph-centric perspective of BGL, in which the graph object is
>> > needed to answer any questions about the graph, even about single
>> > components therein, or to strap a layer on top of all this to
>> > return to proper object encapsulation:
>> >
>> > - where a node knows about its incident edges
>> > - where an edge knows about its source and target vertices
>> > - where both give access to the associated properties.
>> Why is that more "proper?"
> It feels more proper to me in the context of my needs.

Fair enough.

>> > Does anyone have any experience with folding BGL into an existing
>> > graph-like structure?
>> Yes, it has been done many times.
> Do you have pointers to examples?

I think the LEDA graph adapter is probably a good one.

>> > My ideal solution would be my neuron and synapse classes derived
>> > from the vertex and edge descriptors, such that I can treat them
>> > like components of the graph as well as neural components.
>> I'm not sure precisely what your situation is, but it's certainly
>> possible to build a graph wherein you have vertex and edge "objects"
>> by using pointers to edges and vertices as descriptors.
> This is an interesting thought. Nevertheless, in order to get
> adjacent objects, I still need access to the graph object.
> Or am I misunderstanding something here?


     class vertex;

     class edge
        edge(vertex* s, vertex* d)
          : s(s), t(t) {}
        // ... your stuff here

        vertex *s, *t;

     class vertex
         // ... your stuff here...
         std::vector<edge> edges;

     class graph
         std::list<vertex> vertices;

Now satisfy the graph requirements, something like:

   template <>
   struct graph_traits<graph>
        // types required by one of the graph concepts at

        // or, as you can see from
        // these can go directly in your graph class
   // Free functions required by one of the graph concepts at

There probably ought to be a tutorial example in the docs that walks
through this in detail.

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

Maybe you should have asked for help with _that_ project. It
*really* shouldn't be too hard.

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

Avoiding runtime polymorphism is pretty natural with BGL-conformant

Dave Abrahams
Boost Consulting

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