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

From: martin f krafft (madduck_at_[hidden])
Date: 2005-06-14 09:08:54

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 or the get_property method...

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

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.

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

> > 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? If I look at
edge_desc_impl, I see that it derives from edge_base, which is
responsible for storing references to the source and target nodes.
If I replace edge descriptors with pointers to my own class
instances, I would need to amend the BGL API such that the source
and target information could be extracted from my class instances,
right?

> > From looking at the LEDA stuff, I guess the way to do this is to
> > modify the graph traits to replace edge and node descriptors
> > with custom classes. 
> 
> Don't modify the library.  But maybe you mean, "specialize the
> graph traits?"

Yeah, of course.

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

> 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

-- 
martin;              (greetings from the heart of the sun.)
  \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net_at_madduck
 
invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver!
spamtraps: madduck.bogus_at_[hidden]
 
"we are trapped in the belly of this horrible machine,
 and the machine is bleeding to death."
                                        -- godspeed you black emperor!