Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search

Subject: Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search
From: W.P. McNeill (billmcn_at_[hidden])
Date: 2010-07-12 21:45:34

I would put a warning about not subclassing BGL components on the Boost
Graph Concepts page<http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/graph_concepts.html>
since
this is a point in the documentation that gives an overview of the way all
the graph concepts are implemented.  It is also a page that I personally
kept referring back to.  I guess the warning should mention that this
prohibition is an STL thing, and not specific to BGL.

I'll take a look at Boost.Program_options, Boost.Lexical_cast,
and Boost.Random.

Putting filtered_graph over a grid_graph does seem like the right way to go.
 However, I'm having problems doing this.  I can create a filtered version
of a grid graph, however I get build errors when I try to call graph concept
functions on it.  Here's a simple example:

#include <iostream>
#include <boost/graph/grid_graph.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <set>

using namespace boost;

#define RANK 2
typedef grid_graph<RANK> Graph;
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef graph_traits<Graph>::out_edge_iterator out_edge_iterator;

// Print vertices as (x, y).
std::ostream& operator<<(std::ostream& output, const vertex_descriptor& u) {
  return output << "(" << u[0] << ", " << u[1] << ")";
}

// Print edges as (x1, y1) -> (x2, y2).
std::ostream& operator<<(std::ostream& output, const edge_descriptor& e) {
  return output << e.first << "->" << e.second;
}

typedef std::set<vertex_descriptor> VertexSet;
typedef vertex_subset_compliment_filter<Graph, VertexSet>::type
        VertexFilteredGraph;

int main(int argc, char* argv[]) {
  array<std::size_t, RANK> lengths = { {3, 3} };
  Graph g(lengths);

  VertexSet omit;
  omit.insert(vertex(1, g)); // Filter vertex (1, 0) out of the graph.
  VertexFilteredGraph fg = make_vertex_subset_compliment_filter(g, omit);

  // Print the out edges coming from (0, 0) in the unfiltered and filtered
  // graphs.
  vertex_descriptor u = vertex(0, g);

  std::cout << "Unfiltered out edges from " << u << std::endl;
  out_edge_iterator oi, oi_end;
  for (tie(oi, oi_end) = out_edges(u, g); oi != oi_end; oi++)
    std::cout << *oi << std::endl;

  std::cout << "Filtered out edges from " << u << std::endl;
  for (tie(oi, oi_end) = out_edges(u, fg); oi != oi_end; oi++)
    std::cout << *oi << std::endl;

  return 0;
}

When I try to build this I get the following error, which is triggered by
the call to out_edges(u, fg):

g++ -g -O3 -Wall -I/src/boost-trunk   -c -o filter.o filter.cpp
/src/boost-trunk/boost/tuple/detail/tuple_basic.hpp: In member function
‘boost::tuples::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>&
boost::tuples::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8,
T9>::operator=(const std::pair<_U1, _U2>&) [with U1 =
boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all,
boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph,
boost::keep_all, boost::is_not_in_subset<VertexSet> > >,
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default, boost::use_default> >, U2 =
boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all,
boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph,
boost::keep_all, boost::is_not_in_subset<VertexSet> > >,
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default, boost::use_default> >, T0 =
out_edge_iterator&, T1 = out_edge_iterator&, T2 = boost::tuples::null_type,
T3 = boost::tuples::null_type, T4 = boost::tuples::null_type, T5 =
boost::tuples::null_type, T6 = boost::tuples::null_type, T7 =
boost::tuples::null_type, T8 = boost::tuples::null_type, T9 =
boost::tuples::null_type]’:
filter.cpp:47:   instantiated from here
/src/boost-trunk/boost/tuple/detail/tuple_basic.hpp:583: error: no match for
‘operator=’ in ‘((boost::tuples::tuple<out_edge_iterator&,
out_edge_iterator&, boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type,
boost::tuples::null_type>*)this)->boost::tuples::tuple<out_edge_iterator&,
out_edge_iterator&, boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type,
boost::tuples::null_type>::<anonymous>.boost::tuples::cons<out_edge_iterator&,
boost::tuples::cons<out_edge_iterator&, boost::tuples::null_type> >::head =
k->std::pair<boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all,
boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph,
boost::keep_all, boost::is_not_in_subset<VertexSet> > >,
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default, boost::use_default> >,
boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all,
boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph,
boost::keep_all, boost::is_not_in_subset<VertexSet> > >,
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default, boost::use_default> > >::first’
/src/boost-trunk/boost/iterator/transform_iterator.hpp:78: note: candidates
are:
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default, boost::use_default>&
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default,
boost::use_default>::operator=(const
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default, boost::use_default>&)
/src/boost-trunk/boost/tuple/detail/tuple_basic.hpp:584: error: no match for
‘operator=’ in ‘((boost::tuples::tuple<out_edge_iterator&,
out_edge_iterator&, boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type,
boost::tuples::null_type>*)this)->boost::tuples::tuple<out_edge_iterator&,
out_edge_iterator&, boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type, boost::tuples::null_type,
boost::tuples::null_type,
boost::tuples::null_type>::<anonymous>.boost::tuples::cons<out_edge_iterator&,
boost::tuples::cons<out_edge_iterator&, boost::tuples::null_type>
>::tail.boost::tuples::cons<out_edge_iterator&,
boost::tuples::null_type>::head =
k->std::pair<boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all,
boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph,
boost::keep_all, boost::is_not_in_subset<VertexSet> > >,
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default, boost::use_default> >,
boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all,
boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph,
boost::keep_all, boost::is_not_in_subset<VertexSet> > >,
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default, boost::use_default> > >::second’
/src/boost-trunk/boost/iterator/transform_iterator.hpp:78: note: candidates
are:
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default, boost::use_default>&
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default,
boost::use_default>::operator=(const
boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default,
boost::use_default>, boost::use_default, boost::use_default>&)
make: *** [filter.o] Error 1

It looks like missing assignment operators for some tuple structure, but
offhand I'm not sure what.

On Mon, Jul 12, 2010 at 1:12 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Mon, 12 Jul 2010, W.P. McNeill wrote:
>
>  I've got a working A-star maze solver.  The code is checked into the
>> github Astar-Maze-Solver project.  I've tried to put it into a format in
>> which it can be
>> added to the Boost examples directory.
>> A little post-mortem.  A certain amount of difficultly for a newcomer to
>> use the BGL is the price you pay for getting such a powerful and flexible
>> toolkit.
>>  However, I can identify three specific things that contributed to the
>> challenge of writing this sample:
>>  1. A lack of examples of running A-star search on implicit graphs.
>>  2. A-star search bugs in Boost 1.43 that are fixed in the latest source.
>>  3. My confusion about whether or not to subclass Boost Graph Library
>> structures.
>>
>
> One more that has hit other people is named parameters (especially the
> thing about using "." between arguments rather than ",").
>
>
>  (1) I hope this code can help other people with.
>>
>
> Yes, and thank you for doing the example.
>
>
>  (2) hit me because I'm developing on OS X and getting my Boost from
>> MacPorts, which currently only has released version 1.42.  It won't be an
>> issue for people building against the latest version.
>>
>
> OK.  I don't think anyone had tried astar_search with an implicit graph
> before the earliest bug report on the issue (the first one, though, was
> about implicit graphs that don't have num_vertices() and astar_search's
> failure on those).
>
>
>  (3) caused me to go down a few blind alleys.  I by trying to subclass
>> grid_graph, and when that didn't work made grid_graph a member of my own
>> maze class.  Later still, I found that what I really needed was a grid graph
>> from which I could selectively remove edges.  I would have liked to have
>> used grid_graph and just subclassed its out edge iterator, but since
>> subclassing BGL components is a bad idea I ended up writing my own grid
>> implementation.
>>
>
> The subclassing thing is based on STL; you are not supposed to subclass STL
> containers either.  If you want to selectively remove edges, look at
> boost::graph::filtered_graph (
> http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/filtered_graph.html).
> You should be able to wrap that on top of the existing grid_graph.
>
>
>  I've seen it mentioned elsewhere on this board, but I'll also suggest that
>> a warning about subclassing BGL components should be prominent in the
>> documentation.
>>
>
> Where do you think that should go?
>
>
>  Thanks for your help getting this and the implicit graph example into
>> shape.  If there are more tweaks that would make them more suitable for the
>> Boost examples directory, let me know.
>>
>
> One minor thing: maze_traversal_catetory should be maze_traversal_category.
>  I think using filtered_graph might replace all of that code, however.  You
> might also want to use iterator_property_map or shared_array_property_map
> instead of associative_property_map for performance.  If you want to really
> make the code Boost-like (and I'm not suggesting or requiring that you do
> this), you can also use Boost.Program_options, Boost.Lexical_cast and
> Boost.Random to replace the corresponding C functions that you are using
> now.  You are also free to use "using namespace std;" and/or "using
> namespace boost;" in examples; you can put those in if you think it will
> make the code more readable.
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>