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

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? 

Yep.

     class vertex;

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

      private:
        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
        // http://www.boost.org/libs/graph/doc/graph_concepts.html

        // or, as you can see from
        // http://www.boost.org/libs/graph/doc/graph_traits.html,
        // these can go directly in your graph class
   };
   
   // Free functions required by one of the graph concepts at
   // http://www.boost.org/libs/graph/doc/graph_concepts.html

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

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com