on Mon Aug 18 2008, Raindog
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
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