[Boost-users] A* search on Implicit graph (search tree)

Subject: [Boost-users] A* search on Implicit graph (search tree)
From: Nicholas Dahm (n.dahm_at_[hidden])
Date: 2014-09-01 01:07:07

Hi All,

I'm trying to run an A* search using boost's astar_search, but I'm running into issues with 'const'. I'm trying to add the
examine_vertex(my_vdesc_type &v, my_graph_type &g)
function, but of course boost says that I need to make it const like
examine_vertex(my_vdesc_type &v, const my_graph_type &g)
However since I'm searching an implicit graph, I need to call add_vertex(g) within this function. But then I of course get an error because i'm trying to do
add_vertex(const my_graph_type &g)
which is invalid.

I've read the example astar_maze.cpp which CLAIMS to be implicit but certainly doesn't appear to be. I've also seen the pdf at
http://cs.krisbeevers.com/research/astar_bgl04.pdf
which says you need to basically create non-const versions of a bunch of functions.

Considering that
http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/astar_search.html
says that "A* is particularly useful for searching implicit graphs", I'm assuming that boost ALREADY HAS some way of actually searching implicit graphs.

Any ideas?

cheers

Nick