[BGL] overlaying a graph-like structure

newer
[bind / lambda] binding a factory...

older
[BGL] adding behaviour to nodes...

martin f krafft

14 Jun 2005 14 Jun '05

9:50 a.m.

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? From the code: typedef typename boost::ct_if_t::type vertex_descriptor; vertex descriptors are indices or pointers. And typedef detail::edge_desc_impl 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. 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. 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. 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? 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. 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. 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? Is it sensible to derive from detail::edge_desc_impl, or should detail::* stuff not be touched outside of BGL code? Thanks for any comments, thoughts, suggestions, pointers. -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net "i have smoked pot. it is a stupid business, like masturbation." -- thomas pynchon

Attachments:

signature.asc (application/pgp-signature — 189 bytes)

Show replies by date

David Abrahams

14 Jun 14 Jun

1:32 p.m.

martin f krafft 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::type vertex_descriptor;

vertex descriptors are indices or pointers. And

typedef detail::edge_desc_impl 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

martin f krafft

2:08 p.m.

also sprach David Abrahams [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@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net "we are trapped in the belly of this horrible machine, and the machine is bleeding to death." -- godspeed you black emperor!

Doug Gregor

6:46 p.m.

On Jun 14, 2005, at 9:08 AM, martin f krafft wrote:

...

also sprach David Abrahams [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

martin f krafft

7:49 p.m.

also sprach Doug Gregor [2005.06.14.2046 +0200]:

...

The quick tour describes the descriptors:

http://www.boost.org/libs/graph/doc/quick_tour.html

Their concept, yeah. Not necessarily how to extend them or use them in advanced cases.

...

...
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 does not explain to me what get_property does when called on an edge descriptor. If get_property is not to be used by me, then I wonder why it's not protected.

...

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.

Yes, they are. And I am only starting to learn to separate them, so thanks for your patience.

...

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.

Yes, this is essentially my problem.

...

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.

I truly appreciate your feedback and will let it settle for a while. I'll (probably) be back. -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net do micro$oft's total cost of operation calculations include total cost of downtime?

Doug Gregor

22 Jun 22 Jun

4:49 p.m.

On Jun 14, 2005, at 2:49 PM, martin f krafft wrote:

...

also sprach Doug Gregor [2005.06.14.2046 +0200]:

...
...
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 does not explain to me what get_property does when called on an edge descriptor. If get_property is not to be used by me, then I wonder why it's not protected.

Lots of things aren't private/protected because compiler's couldn't handle it when the BGL was written. Doug

David Abrahams

14 Jun 14 Jun

8:59 p.m.

martin f krafft 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

martin f krafft

10:22 p.m.

also sprach David Abrahams [2005.06.14.2259 +0200]:

...

...
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 did, but not here, since it's not boost. Most of it was in ##c++/irc.freenode.org, so it's not really archived. Surely, simple edges and nodes are easy. My challenge is that I wanted to make it configurable whether the node should keep a list of edges, only keep one of them (incoming or outgoing), or actually store both. You can see my current state at http://xrl.us/ge3a. I don't quite have it compiling yet, this is tomorrow's task. However, you can get the idea I was trying to go with: edge list policies, and EmptySequence to simulate a lacking edge list. The main problems I see with this approach are: - users are currently expected to derive from Node and Edge. Since they do not have a virtual destructor though, this could become a problem should they ever store objects by pointer to Node and Edge. My code never deletes anything it did not allocate, so there is no real problem. - even though it seems possible to mix nodes with different edge policies in a single graph, there is a compile-time dependency between the node and the edge to use. I would much rather prefer to have a single type of edge. I will have to investigate a BasicNode abstract base class similar to BasicEdge, which is to be hidden away behind the API such that users are never exposed to it. - the approach with the EmptySequence seems okay, but it has the flair of a hack. Unfortunately, I saw no other way to make nodes with and without edge lists interchangeable other than to replace the list implementation for those without lists with a mock object. There are possibly others; I have not used the code in four weeks.

...

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

Yeah, and it's simple to do with an adjacency list/matrix, it seems. If you look at my code, you'll see that circular dependencies are a major problem... -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net there are lies, statistics, and benchmarks.

7097

Age (days ago)

7105

Last active (days ago)

List overview

Download

7 comments

3 participants

participants (3)

David Abrahams
Doug Gregor
martin f krafft