Re: [Boost-users] boost::graph issues.

From: David Abrahams (dave_at_[hidden])
Date: 2008-08-18 15:54:16

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