Graph Library - bundled properties, internal & external properties
Hello everyone, this is my first post to the list so excuse me if I didn't get some concepts right. I have begun to learn the BGL as I was searching for a good graph library; I am a student in Computer Science and my thesis is about graph algorithms. I am impressed, it seems to be a good library. Plus, it has forced me at last to deepen my knowledge of STL, templates and generic programming. Now to my question: as I am a new user, when I read the documentation I decided to use the new bundled properties mechanism rather than the old properties map methods. It was recommended in the documentation (I would, btw, like to humbly point out that the documentation is not very clear on this. The bundled properties explanation page is not accessible from the content page and could confuse quite a lot of people), and anyway I found that a lot simpler. But now I am running into troubles. First, are bundled properties applicable to "external properties"? To be honest, I don't really get the difference between internal and external properties. Or do I have to use property maps (in the old way) for external properties? Second, with bundled properties I have troubles with constructors. I created a class myClass, that I will use as a struct for the bundled properties. This class contains reference members so it needs a constructor better than the default constructor without any arguments. Creating a graph with these bundled properties doesn't allow me to use another constructor than the default myClass() one, it seems. I think it would be very good if I could create an array of myClass and then point my Graph object to this array to use it as bundled properties. Then I could do all the initialization I want cleanly. Right now, it seems to me than the only way to modify these properties (prior to running a grpah algorithm for example), is to do some sort of: G[v].my_first_data_member =5; G[v].my_second_data_member = "test"; etc... with v moving over all the vertexes (or edges). This seems a little bit strange... and impossible to use reference data members with that, for exemple. My last problem is with the depth_first_search() algorithm... and of course bundled properties. This algorithm takes a const Graph &; but I want to be able to modify (while running the algorithm) the bundled properties!! That is the whole point of running this algorithm. I don't want to change the structure of the graph (the abstract graph - links from vertices to edges, etc), while running the algorithm, of course, but I do want to change when I want my bundled properties... that is not possible (at least, not without compiler warnings, which I don't like :-) due to the fact that depth_first_search expects a const graph. I think that will be all... if someone can enlighthen me on these topics I'll be happy!! Regards Jean-Noël
On Mar 8, 2005, at 7:43 AM, Elvanör wrote:
Hello everyone,
this is my first post to the list so excuse me if I didn't get some concepts right.
Welcome!
Now to my question: as I am a new user, when I read the documentation I decided to use the new bundled properties mechanism rather than the old properties map methods. It was recommended in the documentation (I would, btw, like to humbly point out that the documentation is not very clear on this. The bundled properties explanation page is not accessible from the content page and could confuse quite a lot of people), and anyway I found that a lot simpler.
Ok, we'll work on that.
But now I am running into troubles. First, are bundled properties applicable to "external properties"?
Bundled properties only apply to internal properties.
To be honest, I don't really get the difference between internal and external properties. Or do I have to use property maps (in the old way) for external properties?
Bundled properties don't change external properties at all.
Second, with bundled properties I have troubles with constructors. I created a class myClass, that I will use as a struct for the bundled properties. This class contains reference members so it needs a constructor better than the default constructor without any arguments. Creating a graph with these bundled properties doesn't allow me to use another constructor than the default myClass() one, it seems. I think it would be very good if I could create an array of myClass and then point my Graph object to this array to use it as bundled properties. Then I could do all the initialization I want cleanly.
I think that when you add an edge or vertex, you can just pass a myClass instance before the graph argument, e.g,, v = add_vertex(myClass(some_reference), g);
My last problem is with the depth_first_search() algorithm... and of course bundled properties. This algorithm takes a const Graph &; but I want to be able to modify (while running the algorithm) the bundled properties!! That is the whole point of running this algorithm. I don't want to change the structure of the graph (the abstract graph - links from vertices to edges, etc), while running the algorithm, of course, but I do want to change when I want my bundled properties... that is not possible (at least, not without compiler warnings, which I don't like :-) due to the fact that depth_first_search expects a const graph.
Yeah, this is an annoying problem. We'd like to be able to take either a const or a non-const graph, but doing so would require two overloads of the algorithm, which we really can't do (too much code!). I suggest that you put a non-const reference to the graph from within your visitor and use that instead of the graph that is passed to the event functions. Doug
Hi Doug, Could you please clarify this one to me ? You say "we really can't do (too much code !)" because of lack of time/resources to do it or because you think it is not the right thing to do ? Because in my opinion if it turns the library interface more convenient to use it seems like a good idea to do it. Thank you for your attention, Mauricio Gomes Pensar Digital phone: 55-11-4121-6287 mobile: 55-11-8319-9610 http://pensardigital.com On Mar 9, 2005, at 8:06 PM, Douglas Gregor wrote:
My last problem is with the depth_first_search() algorithm... and of course bundled properties. This algorithm takes a const Graph &; but I want to be able to modify (while running the algorithm) the bundled properties!! That is the whole point of running this algorithm. I don't want to change the structure of the graph (the abstract graph - links from vertices to edges, etc), while running the algorithm, of course, but I do want to change when I want my bundled properties... that is not possible (at least, not without compiler warnings, which I don't like :-) due to the fact that depth_first_search expects a const graph.
Yeah, this is an annoying problem. We'd like to be able to take either a const or a non-const graph, but doing so would require two overloads of the algorithm, which we really can't do (too much code!).
On Mar 10, 2005, at 2:25 PM, Mauricio Gomes wrote:
Could you please clarify this one to me ? You say "we really can't do (too much code !)" because of lack of time/resources to do it or because you think it is not the right thing to do ?
Because in my opinion if it turns the library interface more convenient to use it seems like a good idea to do it.
It's mainly lack of resources: we would essentially have to take every function in the graph library with a signature like "void foo(const Graph& g)", and do a few things: (1) Remove the "const" from "const Graph" wherever it appears in the algorithm, e.g., the signature becomes "void foo(Graph& g)" (2) Create a forwarding function "void foo(const Graph& g)" (with the same signature as the old one) that forwards all of its parameters to the non-constified version (the "const" will become part of the Graph type). (3) In each of the algorithms, use typename remove_const<Graph>::type instead of the type Graph, because graph_traits<const Graph> might not be provided even though "graph_traits<Graph>" is. I'm sure there are some portability issues that will crop up, because I know some compilers don't reliably order between the "const Graph&" and "Graph&" versions. It's a problem we can solve, of course, it's just a huge amount of effort. Doug
participants (4)
-
Douglas Gregor -
Elvanör -
Mauricio Gomes