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

From: Raindog (raindog_at_[hidden])
Date: 2008-08-18 07:16:08

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