boost::graph issues.
Hello, This will be the 2nd time I've tried to use boost::graph in a project, the first time I ended up scrapping the effort and using a different graph implementation because of performance reasons, but I was also considering scrapping it for the reasons I have listed here. My newest project will be using much smaller graphs. First, I *want* to use bgl, the problem I have is that it is by far the most complex and difficult to use library I have ever seen. I equate it to something harder than COM using only C. The majority of my difficulties with BGL are related to the extensive use of template magic that does two things for me: makes code impossible to follow and secondly, it makes debugging even more difficult. For example, someone tell me from looking at this, what *values* will actually be passed to astar_search: astar_search (g, s, h, choose_param(get_param(params, graph_visitor), make_astar_visitor(null_visitor())), choose_param(get_param(params, vertex_predecessor), p_map), cost, distance, weight, index_map, color, choose_param(get_param(params, distance_compare_t()), std::less<C>()), choose_param(get_param(params, distance_combine_t()), closed_plus<C>()), choose_param(get_param(params, distance_inf_t()), std::numeric_limits<C>::max BOOST_PREVENT_MACRO_SUBSTITUTION ()), choose_param(get_param(params, distance_zero_t()), C())); } I would be hard pressed to believe that anyone can answer that in a short amount of time even assuming you have memorized all of the template parameters of g and s and even h. On with more issues. One of the biggest issues I have is that the the property_map concept is exceptionally vague and exceedingly difficult to work with. For example, I have created a graph, it's concise typedef: typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_name_t, Ogre::Vector3>, boost::property<boost::edge_weight3_t, edge_cost> > GraphT; Because of the use of free functions, it's hard to quickly distinguish "get" calls on a property_map from "get" calls on a graph. Additionally, the property_map installation and retrieval to and from a BGL graph is also hard to follow. One might see the following code in the examples directory of bgl: typename property_map<Graph, edge_mycapacity_t>::const_type capacity = get(edge_mycapacity, G); typename property_map<Graph, edge_myflow_t>::const_type flow = get(edge_myflow, G); Where "edge_mycapacity" is an enum; and how exactly enums of the same value can be used to look up different property_maps from the graph is a gaping hole left in the documentation and I still have no idea how it works. Another example is the following: get(vertex_color_t(), g, vertex(2,g)) Here we seem to be left to our imaginations as to how this works. "get" in this case is obviously operating on a graph in this call, but why are we no longer using an enum and instead constructing a temporary "vertex_color_t". Looking at the definition of "get", we see the following: template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty, typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle, typename Key> inline T get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS> const & g, const Key& key) { return get(get(p, g), key); } Hmm, looks like we'll need to look further. I personally am not knowledgeable enough in template magic to make sense of the majority of the BGL source, for me there are way too many things to keep track of in order to be able to completely follow the code. I can't follow very well 100 character variable declarations. So, for some real questions and to end the rant. 1. What language mechanism is allowing property_maps to be stored and retrieved from an instance of a graph? How does "BOOST_DEF_PROPERTY(edge, index)" work exactly? 2. What *is* the required interface for a property_map? get,put, operator[] of course, but the BGL properties appear to function nothing like the example given in the documentation. 3. Why is using get(p,g) better than using myPropMap.get_from(myGraph) and myGraph.get_property_map(prop_map_type) and myGraph.get_edge(edge_descriptor). What benefit does the chosen method provide? 4. The edge property example contains the following: typedef property<edge_mycapacity_t, int> Cap; typedef property<edge_myflow_t, int, Cap> Flow; typedef adjacency_list<vecS, vecS, bidirectionalS, no_property, Flow> Graph; But accesses the Cap property_map as if it is directly associated with the graph, not a nested property of Flow: typename property_map<Graph, edge_mycapacity_t>::const_type capacity = get(edge_mycapacity, G); Can someone explain how that works in better detail? Thanks, Josh PS. This is the 4rd time i've attempted to send this message as I've not seen it yet appear on the list. The 1st 2 attempts were rejected as I had not yet completed subscription process.
on Sun Aug 17 2008, Raindog <raindog-AT-macrohmasheen.com> wrote:
Hello,
This will be the 2nd time I've tried to use boost::graph in a project, the first time I ended up scrapping the effort and using a different graph implementation because of performance reasons,
Note that it is one of the BGL's main features that if for any reason you need your own graph data structure, you can still use BGL's algorithms by retroactively and non-intrusively adapting your structure to the BGL's graph concepts. So from what you're saying above I wouldn't necessarily conclude that you couldn't use BGL.
but I was also considering scrapping it for the reasons I have listed here. My newest project will be using much smaller graphs. First, I *want* to use bgl,
Just curious: why? What do you value about this library?
the problem I have is that it is by far the most complex and difficult to use library I have ever seen. I equate it to something harder than COM using only C.
The majority of my difficulties with BGL are related to the extensive use of template magic that does two things for me: makes code impossible to follow and secondly, it makes debugging even more difficult. For example, someone tell me from looking at this, what *values* will actually be passed to astar_search:
astar_search (g, s, h, choose_param(get_param(params, graph_visitor), make_astar_visitor(null_visitor())), choose_param(get_param(params, vertex_predecessor), p_map), cost, distance, weight, index_map, color, choose_param(get_param(params, distance_compare_t()), std::less<C>()), choose_param(get_param(params, distance_combine_t()), closed_plus<C>()), choose_param(get_param(params, distance_inf_t()), std::numeric_limits<C>::max BOOST_PREVENT_MACRO_SUBSTITUTION ()), choose_param(get_param(params, distance_zero_t()), C())); }
I would be hard pressed to believe that anyone can answer that in a short amount of time even assuming you have memorized all of the template parameters of g and s and even h.
The answer to that depends on how you called astar_search in the first place. Show me your call, and I can easily tell you the answer. But I wouldn't need to know the answer in order to use the library. Anyway, if tracing that code (which is an implementation detail of the graph library) bothers you, then you have several choices other than dropping the BGL again: 1. don't used the named-parameter interface. Just use the overload of astar_search at http://svn.boost.org/trac/boost/browser/trunk/boost/graph/astar_search.hpp#L... 2. Keep using the named parameter interface and set a breakpoint at the line I indicated. It is eventually called by the code you're quoting anyway. In any case, if you want to be effective with Boost libraries I strongly suggest you don't use reading their implementation code as the primary way of understanding how to use them. Most Boost libraries are very carefully constructed so that they are usable just by reading the documentation.
On with more issues.
One of the biggest issues I have is that the the property_map concept is exceptionally vague
I would like to know in what way it is vague. You don't say below.
and exceedingly difficult to work with. For example, I have created a graph, it's concise typedef:
typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_name_t, Ogre::Vector3>, boost::property<boost::edge_weight3_t, edge_cost> > GraphT;
You might consider whether bundled properties would save you some effort here (http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/bundles.html). I'm not sure they would, on reflection, but it might be worth looking into.
Because of the use of free functions, it's hard to quickly distinguish "get" calls on a property_map from "get" calls on a graph.
The use of the same name for both functions is an annoying design decision (partially my fault for encouraging it way back when), but I don't think using member functions would make a huge difference. One of the reasons it's hard to understand is that the latter kind of "get" is just a special "convenience" feature of boost::graph::adjacency_list, so you can't really use it in generic algorithms, while the former is actually part of the property map concept. In any case, the use of free functions in generic libraries is essential for allowing the non-intrusive concept adaptation I mentioned above.
Additionally, the property_map installation and retrieval to and from a BGL graph is also hard to follow. One might see the following code in the examples directory of bgl:
typename property_map<Graph, edge_mycapacity_t>::const_type capacity = get(edge_mycapacity, G); typename property_map<Graph, edge_myflow_t>::const_type flow = get(edge_myflow, G);
Where "edge_mycapacity" is an enum; and how exactly enums of the same value can be used to look up different property_maps from the graph is a gaping hole left in the documentation and I still have no idea how it works.
It uses the fact that the two enums are values of different types (imagine overloads on int and long -- 0 and 0L could select different property maps). But what you're looking at is, I think, an outdated approach. It still needs to be supported for backward compatibility, but IIUC you should use bundled properties now.
Another example is the following:
get(vertex_color_t(), g, vertex(2,g))
Here we seem to be left to our imaginations as to how this works.
How it works is not important if you're just trying to use the library. You know what it's supposed to do, don't you?
"get" in this case is obviously operating on a graph in this call, but why are we no longer using an enum and instead constructing a temporary "vertex_color_t". Looking at the definition of "get", we see the following:
template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty, typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle, typename Key> inline T get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS> const & g, const Key& key) { return get(get(p, g), key); }
Don't look at the implementation. That's not even the overload of get that you're calling in the line you quoted.
So, for some real questions and to end the rant.
1. What language mechanism is allowing property_maps to be stored and retrieved from an instance of a graph?
The question is too broad to answer usefully. The BGL uses many of the language's mechanisms in any given bit of code.
How does "BOOST_DEF_PROPERTY(edge, index)" work exactly?
My advice: don't ask. I don't know the answer, but it doesn't inhibit my ability to use the library.
2. What *is* the required interface for a property_map? get,put, operator[] of course, but the BGL properties appear to function nothing like the example given in the documentation.
The exact requirements are documented at http://www.boost.org/doc/libs/1_35_0/libs/property_map/property_map.html
3. Why is using get(p,g) better than using myPropMap.get_from(myGraph) and myGraph.get_property_map(prop_map_type) and myGraph.get_edge(edge_descriptor). What benefit does the chosen method provide?
An arbitrary type that has the functional _capabilities_ of a property map can be non-intrusively adapted so that it actually *is* a property map just by defining the appropriate free functions and traits specializations. That's how, for example, std::vector can be a property map with an integer key type.
4. The edge property example contains the following: typedef property<edge_mycapacity_t, int> Cap; typedef property<edge_myflow_t, int, Cap> Flow; typedef adjacency_list<vecS, vecS, bidirectionalS, no_property, Flow> Graph;
But accesses the Cap property_map as if it is directly associated with the graph, not a nested property of Flow:
typename property_map<Graph, edge_mycapacity_t>::const_type capacity = get(edge_mycapacity, G);
Can someone explain how that works in better detail?
It's only "nested" in a type sense. Logically, these properties are both at the top level of the graph. It's just the old way of "chaining" properties so you can attach multiple ones to edges or vertices. See http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/property.html HTH, -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams <dave <at> boostpro.com> writes:
In any case, if you want to be effective with Boost libraries I strongly suggest you don't use reading their implementation code as the primary way of understanding how to use them. Most Boost libraries are very carefully constructed so that they are usable just by reading the documentation.
[...]
How it works is not important if you're just trying to use the library.
I agree. The docs in general are high quality and sufficient (except python and debugging w/o static linkage ;-)). OTOH I believe that the development of boost has brought some techniques to life that are useful in general, so some meta-docs, some kind of extended rationale or some "The Design and Evolution of Boost" would boost the development of boost itself. The developer ML shows messages saying "This has been more elegantly solved in boost::x, check the source code there." And poor progranmmers then look at BOOST_MACRO_MAKES_ME_PORTABLE stuff mixed with the original technique. "Take it, don't ask" is OK for users, since boost is well-thought, well-done and well-documented, but this is only half of the truth. We all not only are users, but also writers of code. The value of boost not only lies in its interface and abstraction level, but also in the knowledge behind it. My favourite example of how things should be is Eric Niebler's slow motion explanation in his splendid article about abusing ternary operator ?: to achieve a no-overhead-BOOST_FOREACH. (http://www.artima.com/cppsource/foreach.html) I have learned that one by heart. I have it in my head. It will help me one day. Another issue I think is the fact that it is not transparent to the world, whether there is some development or not going on in some portion of boost. E.g. boost::graph: Since years and years there is a Delaunay Triangulation anounced in the future plans of boost::graph (http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/challenge.html), but I do not believe that oneanymore, especially since CGAL (http://www.cgal.org/) went open source. So I considered boost::graph as DeadProject(TM). OTOH I found by chance (digging into the wiki) that someone is working on the named parameter scheme and some Summer of Code projects on graph algos. So what's its state? Same thing with bind: It is a big boost FAQ which version of bind (original, ll::bind, tr1::bind, fusion::bind, phoenix::bind, spirit2::bind, ...) to be used and the answer depends on which month you ask and whether it is Joel or someone else answering (I like Joel's answer ;-)). I think we could tag BLL as "not recommended" in future boost versions. ... and regular expressions: I feel not able to find best choice among boost::regexp, tr1::regexp, xpressive and spirit semantic actions and happened to give a try to all of those (except tr1) in the same project. One could argue that this is normal for a fast evolving project to have concurrent engineering everywhere, but from user's point of view you sometimes cannot know your mass from a black hole anymore due to the number of choices (which again is good, but makes it hard for first time users). In short: I would like to propose some finer grained tagging of boost libraries. It is no longer "The Boost Library", but "The Boost Libraries". See sf.net as reference, from which I'd lend at least - activity ranking + history - maturity level (peer-reviewed is *not* mature) - detailed and frequently reworked future plans - alternative boost libraries with similar or superior functionality and/or "deprecated" tag, like for BLL Markus
Comments inline, commentary at bottom. David Abrahams wrote:
on Sun Aug 17 2008, Raindog <raindog-AT-macrohmasheen.com> wrote:
Hello,
This will be the 2nd time I've tried to use boost::graph in a project, the first time I ended up scrapping the effort and using a different graph implementation because of performance reasons,
Note that it is one of the BGL's main features that if for any reason you need your own graph data structure, you can still use BGL's algorithms by retroactively and non-intrusively adapting your structure to the BGL's graph concepts. So from what you're saying above I wouldn't necessarily conclude that you couldn't use BGL.
but I was also considering scrapping it for the reasons I have listed here. My newest project will be using much smaller graphs. First, I *want* to use bgl,
Just curious: why? What do you value about this library?
I value boost because of its general high quality and I did not necessarily want to bring more dependencies to my project. Additionally I wanted to use a well known library that others I may work with might use or already be familiar with.
the problem I have is that it is by far the most complex and difficult to use library I have ever seen. I equate it to something harder than COM using only C.
The majority of my difficulties with BGL are related to the extensive use of template magic that does two things for me: makes code impossible to follow and secondly, it makes debugging even more difficult. For example, someone tell me from looking at this, what *values* will actually be passed to astar_search:
astar_search (g, s, h, choose_param(get_param(params, graph_visitor), make_astar_visitor(null_visitor())), choose_param(get_param(params, vertex_predecessor), p_map), cost, distance, weight, index_map, color, choose_param(get_param(params, distance_compare_t()), std::less<C>()), choose_param(get_param(params, distance_combine_t()), closed_plus<C>()), choose_param(get_param(params, distance_inf_t()), std::numeric_limits<C>::max BOOST_PREVENT_MACRO_SUBSTITUTION ()), choose_param(get_param(params, distance_zero_t()), C())); }
I would be hard pressed to believe that anyone can answer that in a short amount of time even assuming you have memorized all of the template parameters of g and s and even h.
The answer to that depends on how you called astar_search in the first place. Show me your call, and I can easily tell you the answer. But I wouldn't need to know the answer in order to use the library.
Anyway, if tracing that code (which is an implementation detail of the graph library) bothers you, then you have several choices other than dropping the BGL again:
1. don't used the named-parameter interface. Just use the overload of astar_search at http://svn.boost.org/trac/boost/browser/trunk/boost/graph/astar_search.hpp#L...
It just occurred to me what all that hubbub does now, which is far more understandable, but still increases debugging difficulty simply because of all the parameters that must be passed to the function.
2. Keep using the named parameter interface and set a breakpoint at the line I indicated. It is eventually called by the code you're quoting anyway.
In any case, if you want to be effective with Boost libraries I strongly suggest you don't use reading their implementation code as the primary way of understanding how to use them. Most Boost libraries are very carefully constructed so that they are usable just by reading the documentation.
I'm able to use every other boost library that I have tried quite effectively, and they've assisted me greatly in solving various problems in an efficient manner.
On with more issues.
One of the biggest issues I have is that the the property_map concept is exceptionally vague
I would like to know in what way it is vague. You don't say below.
and exceedingly difficult to work with. For example, I have created a graph, it's concise typedef:
typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_name_t, Ogre::Vector3>, boost::property<boost::edge_weight3_t, edge_cost> > GraphT;
You might consider whether bundled properties would save you some effort here (http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/bundles.html). I'm not sure they would, on reflection, but it might be worth looking into.
I had looked at the bundled properties and had at the time decided to write my own property which took me a very long time to do.
Because of the use of free functions, it's hard to quickly distinguish "get" calls on a property_map from "get" calls on a graph.
The use of the same name for both functions is an annoying design decision (partially my fault for encouraging it way back when), but I don't think using member functions would make a huge difference. One of the reasons it's hard to understand is that the latter kind of "get" is just a special "convenience" feature of boost::graph::adjacency_list, so you can't really use it in generic algorithms, while the former is actually part of the property map concept.
In any case, the use of free functions in generic libraries is essential for allowing the non-intrusive concept adaptation I mentioned above.
I must be missing something here, as concepts to me seem just like policies. In Loki, where I first learned of policies, policies are required to implement certain member functions, such as Clone and Release for the Ownership policy. Perhaps there is some lookup magic that I don't understand that requires free functions.
Additionally, the property_map installation and retrieval to and from a BGL graph is also hard to follow. One might see the following code in the examples directory of bgl:
typename property_map<Graph, edge_mycapacity_t>::const_type capacity = get(edge_mycapacity, G); typename property_map<Graph, edge_myflow_t>::const_type flow = get(edge_myflow, G);
Where "edge_mycapacity" is an enum; and how exactly enums of the same value can be used to look up different property_maps from the graph is a gaping hole left in the documentation and I still have no idea how it works.
It uses the fact that the two enums are values of different types (imagine overloads on int and long -- 0 and 0L could select different property maps). But what you're looking at is, I think, an outdated approach. It still needs to be supported for backward compatibility, but IIUC you should use bundled properties now.
Another example is the following:
get(vertex_color_t(), g, vertex(2,g))
Here we seem to be left to our imaginations as to how this works.
How it works is not important if you're just trying to use the library. You know what it's supposed to do, don't you?
The reason I brought that specific example up was that it seemed default constructing a property that is then used to retrieve a property_map from the graph which is then used to look up a property on a vertex, the construction of the vertex_color_t makes one believe that it is somehow efficient to do this for each property retrieval. Secondly, it appears to have different semantics than using get(property,graph); get(key,property); A key thing I find hard to track is how expensive are these operations. It seems that some properties can be stored and retrieved in O(1) space/time, yet others are obviously more expensive to work with. After going through the bgl documentation again
So, for some real questions and to end the rant.
1. What language mechanism is allowing property_maps to be stored and retrieved from an instance of a graph?
The question is too broad to answer usefully. The BGL uses many of the language's mechanisms in any given bit of code.
How does "BOOST_DEF_PROPERTY(edge, index)" work exactly?
My advice: don't ask. I don't know the answer, but it doesn't inhibit my ability to use the library.
It inhibited my understanding of how to best go about creating my own property.
2. What *is* the required interface for a property_map? get,put, operator[] of course, but the BGL properties appear to function nothing like the example given in the documentation.
The exact requirements are documented at http://www.boost.org/doc/libs/1_35_0/libs/property_map/property_map.html
3. Why is using get(p,g) better than using myPropMap.get_from(myGraph) and myGraph.get_property_map(prop_map_type) and myGraph.get_edge(edge_descriptor). What benefit does the chosen method provide?
An arbitrary type that has the functional _capabilities_ of a property map can be non-intrusively adapted so that it actually *is* a property map just by defining the appropriate free functions and traits specializations. That's how, for example, std::vector can be a property map with an integer key type.
4. The edge property example contains the following: typedef property<edge_mycapacity_t, int> Cap; typedef property<edge_myflow_t, int, Cap> Flow; typedef adjacency_list<vecS, vecS, bidirectionalS, no_property, Flow> Graph;
But accesses the Cap property_map as if it is directly associated with the graph, not a nested property of Flow:
typename property_map<Graph, edge_mycapacity_t>::const_type capacity = get(edge_mycapacity, G);
Can someone explain how that works in better detail?
It's only "nested" in a type sense. Logically, these properties are both at the top level of the graph. It's just the old way of "chaining" properties so you can attach multiple ones to edges or vertices. See http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/property.html
HTH,
Thanks for responding. To put some more context behind my usage of bgl, I was writing an application that would read in a terrain height map and produce a navigation mesh that could be used for pathfinding. The resolution of the graph was about 4 units distance between each node and a maximum degree of 8. The terrain file was about 35k x 35k units in size so before any of the weeding of non-navigable nodes took place, the graph was quite sizable. The main grid was broken down into a grid of a grid of a grid IE: Outer grid (A) of 16x16 and each grid there was another grid of (B)16x16 and that grid was again broken into another grid (C) of 16x16. Each cell in grid A was stored in a separate file for optimization reasons so that only portions of the terrain had to be loaded at a time. This also made for a complex but efficient way of operating on the graphs nodes when it was loaded; it enabled integer arithmetic to be used for astar searches and then that path could be converted to through additional calculations based on a property associated with each node, into its actual floating point location. Similarly, given a 3d vector in world coordinates, an operation could be performed that would quickly locate the nearest node in the graph and additionally it could be used to determine which files needed to be loaded. It all worked somewhat like how a paging table is used to translate a 32 bit virtual memory address into a physical memory address. The reason I was unable to just "use" the bgl as you mentioned was because of the performance issues I was having. I needed to know why for example, so many copies of 400,000 element vectors were being made, which required better understandings of the implementation details of BGL. Thanks.
on Mon Aug 18 2008, Raindog <raindog-AT-macrohmasheen.com> wrote:
Because of the use of free functions, it's hard to quickly distinguish "get" calls on a property_map from "get" calls on a graph.
The use of the same name for both functions is an annoying design decision (partially my fault for encouraging it way back when), but I don't think using member functions would make a huge difference. One of the reasons it's hard to understand is that the latter kind of "get" is just a special "convenience" feature of boost::graph::adjacency_list, so you can't really use it in generic algorithms, while the former is actually part of the property map concept.
In any case, the use of free functions in generic libraries is essential for allowing the non-intrusive concept adaptation I mentioned above.
A small request: if you could leave a blank line between the text you're quoting and your newly-inserted stuff, it would greatly aid readability (for me).
I must be missing something here, as concepts to me seem just like policies.
They're totally different categories. A concept is an abstract set of requirements (http://www.generic-programming.org/about/glossary.php?term=concept, http://www.boost.org/community/generic_programming.html#concept) and not even a language construct today (it will be in C++0x). They arise out of looking at families of algorithms and abstracting away the common requirements. Policies are type arguments to a class template that contribute (orthogonal) parts of the resulting class' interface or behavior (http://en.wikipedia.org/wiki/Policy-based_design#Overview).
In Loki, where I first learned of policies, policies are required to implement certain member functions, such as Clone and Release for the Ownership policy.
Yes. One could use concepts to describe the constraints and requirements on a class template's policy parameters.
Perhaps there is some lookup magic that I don't understand that requires free functions.
Suppose you want to write a family of algorithms that operate on whole Containers. Let's say you choose the STL container interface for getting at their iterators (begin/end member functions). // a toy algorithm template <class C, class T> T const* find(C const& c, T const& value) { T const* b = c.begin(); for (T const* e = c.end(); b != e; ++b) if (*b == value) break; return b; } Then you realize that built-in arrays should be perfectly good Containers, but they don't have member functions, and you can't add any: int a[] = { 1, 3, 7... }; find(a, 12); // <== error, a.begin() is illegal. The same problem goes for your third-party container that doesn't expose iterators but can be indexed by size_t values. If you had defined your Container concept using free functions instead: // a toy algorithm template <class C, class T> T const* find(C const& c, T const& value) { T const* b = begin(c); for (T const* e = end(c); b != e; ++b) if (*b == value) break; return b; } then you could easily and non-intrusively write these begin/end overloads: template <class T, std::size_t N> T const* begin(T (&a)[N]) { return a; } template <class T, std::size_t N> T const* end(T (&a)[N]) { return a + N; } and now builtin arrays satisfy the Container requirements and can be used with your algorithms.
Another example is the following:
get(vertex_color_t(), g, vertex(2,g))
Here we seem to be left to our imaginations as to how this works.
How it works is not important if you're just trying to use the library. You know what it's supposed to do, don't you?
The reason I brought that specific example up was that it seemed default constructing a property
vertex_color_t is just a "property identifier."
that is then used to retrieve a property_map from the graph which is then used to look up a property on a vertex, the construction of the vertex_color_t makes one believe that it is somehow efficient to do this for each property retrieval.
It is. In fact, it's basically free.
Secondly, it appears to have different semantics than using get(property,graph); get(key,property);
How so?
A key thing I find hard to track is how expensive are these operations. It seems that some properties can be stored and retrieved in O(1) space/time, yet others are obviously more expensive to work with.
Generally speaking, property access should be at most O(log N).
After going through the bgl documentation again
??
How does "BOOST_DEF_PROPERTY(edge, index)" work exactly?
My advice: don't ask. I don't know the answer, but it doesn't inhibit my ability to use the library.
It inhibited my understanding of how to best go about creating my own property.
One problem you may be running into is that the BGL book hasn't been updated since bundled properties were added to the library. <schnipp>
Thanks for responding. To put some more context behind my usage of bgl, I was writing an application that would read in a terrain height map and produce a navigation mesh that could be used for pathfinding. The resolution of the graph was about 4 units distance between each node and a maximum degree of 8. The terrain file was about 35k x 35k units in size so before any of the weeding of non-navigable nodes took place, the graph was quite sizable. The main grid was broken down into a grid of a grid of a grid IE: Outer grid (A) of 16x16 and each grid there was another grid of (B)16x16 and that grid was again broken into another grid (C) of 16x16. Each cell in grid A was stored in a separate file for optimization reasons so that only portions of the terrain had to be loaded at a time. This also made for a complex but efficient way of operating on the graphs nodes when it was loaded; it enabled integer arithmetic to be used for astar searches and then that path could be converted to through additional calculations based on a property associated with each node, into its actual floating point location. Similarly, given a 3d vector in world coordinates, an operation could be performed that would quickly locate the nearest node in the graph and additionally it could be used to determine which files needed to be loaded. It all worked somewhat like how a paging table is used to translate a 32 bit virtual memory address into a physical memory address.
The reason I was unable to just "use" the bgl as you mentioned was because of the performance issues I was having. I needed to know why for example, so many copies of 400,000 element vectors were being made, which required better understandings of the implementation details of BGL.
Nothing in the BGL that I know of would make *any* copies of vectors. If you need a paging structure like the one you described, you certainly don't want to use boost::graph::adjacency_list as your top-level graph structure, but you should be able to build a conforming model of the BGL graph concepts that does what you need and still works with the BGL algorithms. HTH, -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Mon Aug 18 2008, Raindog <raindog-AT-macrohmasheen.com> wrote:
Because of the use of free functions, it's hard to quickly distinguish "get" calls on a property_map from "get" calls on a graph.
The use of the same name for both functions is an annoying design decision (partially my fault for encouraging it way back when), but I don't think using member functions would make a huge difference. One of the reasons it's hard to understand is that the latter kind of "get" is just a special "convenience" feature of boost::graph::adjacency_list, so you can't really use it in generic algorithms, while the former is actually part of the property map concept.
In any case, the use of free functions in generic libraries is essential for allowing the non-intrusive concept adaptation I mentioned above.
A small request: if you could leave a blank line between the text you're quoting and your newly-inserted stuff, it would greatly aid readability (for me).
ok
Perhaps there is some lookup magic that I don't understand that requires free functions.
[snip]
then you could easily and non-intrusively write these begin/end overloads:
template <class T, std::size_t N> T const* begin(T (&a)[N]) { return a; }
template <class T, std::size_t N> T const* end(T (&a)[N]) { return a + N; }
and now builtin arrays satisfy the Container requirements and can be used with your algorithms.
Ahh, this seems obvious now...
Another example is the following:
get(vertex_color_t(), g, vertex(2,g)) [snip] Secondly, it appears to have different semantics than using get(property,graph); get(key,property);
How so?
Because in the 3 argument get, you construct an object, in the 2 arg call that operates on a property_map, you pass in an enum.
A key thing I find hard to track is how expensive are these operations. It seems that some properties can be stored and retrieved in O(1) space/time, yet others are obviously more expensive to work with.
Generally speaking, property access should be at most O(log N).
After going through the bgl documentation again
Meant to say that I had realized that I could have implemented a property_map and property that were O(1) in size/time
How does "BOOST_DEF_PROPERTY(edge, index)" work exactly?
My advice: don't ask. I don't know the answer, but it doesn't inhibit my ability to use the library.
It inhibited my understanding of how to best go about creating my own property.
One problem you may be running into is that the BGL book hasn't been updated since bundled properties were added to the library.
<schnipp>
[snip]
The reason I was unable to just "use" the bgl as you mentioned was because of the performance issues I was having. I needed to know why for example, so many copies of 400,000 element vectors were being made, which required better understandings of the implementation details of BGL.
Nothing in the BGL that I know of would make *any* copies of vectors. If you need a paging structure like the one you described, you certainly don't want to use boost::graph::adjacency_list as your top-level graph structure, but you should be able to build a conforming model of the BGL graph concepts that does what you need and still works with the BGL algorithms.
I believe now that the copies were created by calls to a* in that it apparently needed to create temporaries for whatever purpose, or perhaps it needed to create some separate lists in order to track visited nodes, either way, it was a very long pause in execution when under the debugger. Thanks, Josh
Raindog wrote:
Hello,
This will be the 2nd time I've tried to use boost::graph in a project, the first time I ended up scrapping the effort and using a different graph implementation because of performance reasons, but I was also considering scrapping it for the reasons I have listed here. My newest project will be using much smaller graphs. First, I *want* to use bgl, the problem I have is that it is by far the most complex and difficult to use library I have ever seen. I equate it to something harder than COM using only C.
Did you read the BGL book? I and my coworkers read it and it was helpful. (As with the MPL book) --John
John C. Femiani wrote:
Raindog wrote:
Hello,
This will be the 2nd time I've tried to use boost::graph in a project, the first time I ended up scrapping the effort and using a different graph implementation because of performance reasons, but I was also considering scrapping it for the reasons I have listed here. My newest project will be using much smaller graphs. First, I *want* to use bgl, the problem I have is that it is by far the most complex and difficult to use library I have ever seen. I equate it to something harder than COM using only C.
Did you read the BGL book? I and my coworkers read it and it was helpful. (As with the MPL book)
--John _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Yes. After reading David's reply, I think the majority of my issue revolves around the fact that using OOTB bgl was not quite sufficient in my mind and required me to dig a bit deeper and upon doing that digging, I felt that I had wholly inadequate information available to me.
participants (5)
-
David Abrahams -
John C. Femiani -
Markus Werle -
Raindog -
Robert Jones