I would put a warning about not subclassing BGL components on the Boost Graph Concepts page 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@osl.iu.edu> 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@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users