Dear all, I haven't given up in trying to implement an A* algorithm with BGL. My problem is theoretically simple, as in some previous posts. Given a graph of letters, and a word, find the path in the graph that minimizes the distance between the letters of the word and the nodes in the graph. It's best to show an example: /* * B H * / \ / * A---D---F---G---I * \ /\ * C E * * input: A E I O U * result: A D F G I */ With that graph, my heuristic should take into account not just the letter in the graph per se, but the *corresponding* one in the input word. So, starting with "AEIOU" the search will: - expand A (A in **A**EIOU) - find B, C, D - expand D (closest to E in A**E**IOU) - find D, F - expand F (closest to I in AE**I**OU) - find G - expand G (only one, closest to O in AEI**O**U) - find H, I - expand U (closest to U in AEIO**U**) This settings could also be more complicated, adding weights to edges, but for now I am happy with this problem. What I've done now? Implementing my own A* algorithm, by hand. Of course this might work, but I'd prefer using BGL's facilities. I must say that I am quite confused about BGL's data structures, as for instance in the A* cities example (1), we need to create a weight map, so what if I don't need weights? Moreover, predecessors and distances are instantiated with a std::vector, but what happens if I need to operate on a very large graph, for instance 200M nodes? Moreover, what will happen when I will distribute the graph over a cluster with Boost Parallel Graph? ... Ok maybe this is too ahead of the time! :) Basically, I'd need to replicate my A* ugly by-hand implementation with custom visitors and custom heuristics. Below you may find my failed attempt. I need some help with this, because I find the documentation a little bit hard to understand, especially when some newbie like me approaches Boost :) Failures in my code: I can't get to define a non-weighted graph, and the call to the A* search is cryptic: I don't have weights. Should I define fake ones for instance all equal to 1? I really hope you guys can help me in this, my code works, but using BGL would be best! Thanks! (1) http://www.boost.org/doc/libs/1_57_0/libs/graph/example/astar-cities.cpp #include <iostream> #include #include <vector> #include <string> #include <utility> #include #include #include #include typedef boost::adjacency_list graph; typedef boost::graph_traits<graph>::edge_iterator edge_iterator; // Custom A* heuristic template class bestmatch_heuristic : public boost::astar_heuristic { public: typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; bestmatch_heuristic() { }; CostType operator()(Vertex u) { std::cout << ">>>> h(" << u << ") = " << 1 << std::endl; return 1; } private: }; // Used to end the A* search algorithm struct end_astar { }; // Custom A* visitor template <class Vertex> class bestmatch_visitor : public boost::default_astar_visitor { public: bestmatch_visitor(Vertex goal) : destination_(goal) { }; template<class Graph> void discover_vertex(Vertex u, const Graph &g) { std::cout << "discover " << u << std::endl; } template <class Graph> void examine_vertex(Vertex u, Graph& g) { std::cout << "examine " << u << std::endl; if (u == destination_) throw end_astar(); } private: Vertex destination_; }; int main() { /* * B H * / \ / * A---D---F---G---I * \ /\ * C E * * input: A E I O U * result: A D F G I */ std::unordered_map letters; auto getletter = [](std::size_t i) -> char { return 'A' + i; }; for (int i = 'A'; i <= 'I'; i++) letters[i] = i - 'A'; graph g; boost::add_edge(letters['A'], letters['B'], g); boost::add_edge(letters['A'], letters['C'], g); boost::add_edge(letters['A'], letters['D'], g); boost::add_edge(letters['B'], letters['D'], g); boost::add_edge(letters['C'], letters['D'], g); boost::add_edge(letters['D'], letters['E'], g); boost::add_edge(letters['D'], letters['F'], g); boost::add_edge(letters['F'], letters['G'], g); boost::add_edge(letters['G'], letters['H'], g); boost::add_edge(letters['G'], letters['I'], g); edge_iterator ei, ee; for (boost::tie(ei, ee) = boost::edges(g); ei != ee; ei++) { std::cout << getletter(boost::source(*ei, g)) << " -> " << getletter(boost::target(*ei, g)) << std::endl; } // Heuristics bestmatch_heuristic h; // Predecessors std::vectorgraph::vertex_descriptor p(boost::num_vertices(g)); try { #if 0 boost::astar_search_tree(// Graph g, // Start node letters['A'], // Heuristics bestmatch_heuristic(), // Predecessor map boost::predecessor_map(boost::make_iterator_property_map(p.begin(), boost::get(boost::vertex_index, g)))); #endif } catch (end_astar e) { } }