[Boost-users] boost::graph issues.

From: Raindog (raindog_at_[hidden])
Date: 2008-08-17 19:05:43

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.