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

From: David Abrahams (dave_at_[hidden])
Date: 2005-06-14 08:32:37

martin f krafft <madduck_at_[hidden]> writes:

> I am looking at the possibility to use BGL for the structural
> representation of an artificial neural network: nodes would be
> neurons, edges would be synapses. The advantage for me would be that
> I don't have to worry about complexity of the graph structure.
>
> For this to work, I need to be able to strap behaviour and data onto
> the edges and nodes. The bundled properties interfaces seems to be
> a good way to do this, but there is something fundamental that I am
> apparently not understanding: What is an edge descriptor, what is
> a vertex descriptor?

Just think of them as some arbitrary datatype whose value is a unique
identifier for an edge or vertex, respectively.

> From the code:
>
>     typedef typename boost::ct_if_t<is_rand_access,
>       std::size_t, vertex_ptr>::type vertex_descriptor;
>
> vertex descriptors are indices or pointers. And
>
>     typedef detail::edge_desc_impl<directed_category, vertex_descriptor>
>       edge_descriptor;
>
> and edge is actually a struct containing source and target vertex, and a
> property pointer (void*). There does not seem to be a way to get the
> property object from an edge descriptor without casting to the
> expected type.

Don't look at the code; read the documentation.  And don't do any
casting.

> Thus, vertex and edge descriptors are really just minimal and
> provide absolutely no way to access the relevant data through their
> interface. Instead, BGL expects people to have access to the
> containing graph object, to be able to call functions like target(),
> out_edges(), or operator[] to get at the downstream vertex/edge, or
> a vertex'/edge's properties.

Correct.

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

The BGL's view is appropriate for any truly generic graph library.
Many commonly-used graph representations don't have edge and vertex
"objects."  If the library is to work with those structures, it can't
expect nodes to "know about" edges.

> If I wanted to go the latter way, I'd have to store an additional
> 8 bytes (descriptor + graph references) with each object, which is
> just a waste if you ask me. However, there seems to be no other way
> as I cannot derive from vertex/edge descriptors.
>
> Does anyone have any experience with folding BGL into an existing
> graph-like structure? 

Yes, it has been done many times.

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

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

> If I take care to model the behaviour of the existing edge and node
> descriptors wrt their interfaces, I shouldn't actually need to
> override the public Graph API, right?

That's starting to sound right.

> Is it sensible to derive from detail::edge_desc_impl, or should
> detail::* stuff not be touched outside of BGL code?

That's right; detail:: stuff is not for user consumption.

> 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.  It's pretty easy to build the kind of graph structure you want
by hand, and it's possible to make it fit the Adjacency Graph concept
(http://www.boost-consulting.com/boost/libs/graph/doc/AdjacencyGraph.html)
so that you can use it with BGL algorithms, but AFAIK BGL doesn't
supply a graph structure that has the attributes you're describing.

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