Dear all, I am fiddling with the A* example on cities in order to learn how to use the A* search. Obviously, I cannot make it work :) The main goal is this, but I'm way too far from this: make A* fail when the path is longer, **not costlier**, than a constant. But right now I'd just like to have A* working on a graph. :) In order to see the different results, I've paired it with a Dijkstra search, and my A* heuristics is quite simple: constant. Dijkstra works fine, but A* stops at the first node, and the target isn't reached (but a path is available). What am I doing wrong? Forgive me if I'm making a stupid mistake bu I'm completely a newbie! If you need the graph, here's the link: https://dl.dropboxusercontent.com/u/15635416/g.txt Thanks! #include <cstdio> #include <cstdlib> #include <iostream> #include <utility> #include <algorithm> #include <numeric> #include <deque> #include <unordered_set> #include <vector> #include <fstream> #include <list> #include <boost/graph/graph_traits.hpp> #include <boost/graph/compressed_sparse_row_graph.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/graph/breadth_first_search.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/pending/indirect_cmp.hpp> #include <boost/range/irange.hpp> #include <boost/property_map/property_map.hpp> #include <boost/graph/astar_search.hpp> // Properties: weights are int typedef boost::property<boost::edge_weight_t, int> edge_weight; // The graph itself as a compressed sparse row matrix typedef boost::compressed_sparse_row_graph<boost::bidirectionalS, boost::no_property, edge_weight> boost_graph; // Vertex iterator typedef boost::graph_traits<boost_graph>::vertex_iterator vertex_iterator; // Edge iterator typedef boost::graph_traits<boost_graph>::edge_iterator edge_iterator; // Adjacent nodes iterator typedef boost::graph_traits<boost_graph>::adjacency_iterator adjacency_iterator; typedef boost::graph_traits<boost_graph>::out_edge_iterator outward_iterator; typedef boost::graph_traits<boost_graph>::in_edge_iterator inward_iterator; // Property maps typedef boost::property_map<boost_graph, boost::vertex_index_t>::type index_map; //typedef boost::property_map<boost_graph, boost::vertex_name_t> name_map; // Property iterators typedef boost::iterator_property_map<std::size_t*, index_map, std::size_t, std::size_t&> predecessor_map; typedef boost::iterator_property_map<std::size_t*, index_map, std::size_t, std::size_t&> distance_map; bool isValid(std::size_t index) { return (index >= 0) && (index <= 12); } // **************************************************************************** // A* heuristics template <class graph_type> class astar_heuristic : public boost::astar_heuristic<graph_type, std::size_t> { public: typedef typename boost::graph_traits<graph_type>::vertex_descriptor vertex_type; astar_heuristic(vertex_type goal) : goal_(goal) { }; std::size_t operator()(vertex_type u) { return 3; } private: vertex_type goal_; }; // Class to be used to terminate the A* algorithm class exit_astar { public: exit_astar(bool found) { }; }; // A* visitor that terminates when we find the goal template <class vertex_type> class astar_visitor : public boost::default_astar_visitor { public: astar_visitor(vertex_type goal) : goal_(goal) { }; template <class Graph> void examine_vertex(vertex_type u, Graph& g) { //std::cout << "EXAM: " << u << std::endl; if (u == goal_) throw exit_astar(true); } private: vertex_type goal_; }; // **************************************************************************** int main(int argc, const char * argv[]) { std::vector<std::pair<std::size_t, std::size_t>> graph_edges; std::vector<int> edge_weight; int n_nodes; int read_a, read_b, read_w; n_nodes = -1; std::ifstream igraph("/Users/senseiwa/Documents/Projects/scratch/tbb/g.txt"); while(igraph >> read_a >> read_b >> read_w) { if (read_a > n_nodes) n_nodes = read_a; if (read_b > n_nodes) n_nodes = read_b; read_a--; read_b--; graph_edges.push_back(std::make_pair(read_a, read_b)); edge_weight.push_back(read_w); } std::cout << "+++ READ # NODES: " << n_nodes << std::endl; // Create the graph boost_graph graph(boost::edges_are_unsorted_multi_pass, graph_edges.begin(), graph_edges.end(), edge_weight.data(), n_nodes); std::cout << "Graph statistics: " << std::endl; std::cout << "Nodes: " << boost::num_vertices(graph) << std::endl; std::cout << "Edges: " << graph_edges.size() << std::endl; edge_iterator ei, ee; std::size_t source_node = std::stoul(argv[1]); std::size_t destination_node = std::stoul(argv[2]); std::cout << ">> SOURCE NODE " << source_node << std::endl; std::cout << "Degrees in/out: " << source_node << std::endl; std::cout << boost::in_degree(boost::vertex(source_node, graph), graph) << std::endl; std::cout << boost::out_degree(boost::vertex(source_node, graph), graph) << std::endl; std::cout << "Degrees in/out: " << destination_node << std::endl; std::cout << boost::in_degree(boost::vertex(destination_node, graph), graph) << std::endl; std::cout << boost::out_degree(boost::vertex(destination_node, graph), graph) << std::endl; std::vector<std::size_t> preds(boost::num_vertices(graph)); std::vector<std::size_t> dists(boost::num_vertices(graph)); index_map idx_map = boost::get(boost::vertex_index, graph); predecessor_map pred_map(preds.data(), idx_map); distance_map dist_map(dists.data(), idx_map); boost::dijkstra_shortest_paths(graph, source_node, boost::distance_map(dist_map).predecessor_map(pred_map)); typedef std::vector<boost_graph::edge_descriptor> path_type; path_type spath; std::cout << ">> SOURCE NODE " << source_node << std::endl; std::cout << ">> DESTINATION NODE " << destination_node << std::endl; // ******* DIJKSTRA ******************************************************** std::size_t v = destination_node; // We want to start at the destination and work our way back to the source for(std::size_t u = pred_map[v]; // Start by setting 'u' to the destintaion node's predecessor u != v; // Keep tracking the path until we get to the source v = u, u = pred_map[v]) // Set the current vertex to the current predecessor, and the predecessor to one level up { std::pair<boost_graph::edge_descriptor, bool> edgePair = boost::edge(u, v, graph); boost_graph::edge_descriptor edge = edgePair.first; spath.push_back(edge); } // Write shortest path int totalDistance = 0; for(path_type::reverse_iterator pathIterator = spath.rbegin(); pathIterator != spath.rend(); ++pathIterator) { std::cout << boost::source(*pathIterator, graph) << " - " << boost::target(*pathIterator, graph) << " = " << boost::get(boost::edge_weight, graph, *pathIterator) << std::endl; totalDistance += boost::get(boost::edge_weight, graph, *pathIterator); } std::cout << "Shortest Dijkstra path from " << source_node << " to " << destination_node << " cost " << totalDistance << std::endl; // ******* A* ************************************************************** // A* search predecessor and cost std::vector<std::size_t> p(boost::num_vertices(graph)); std::vector<std::size_t> d(boost::num_vertices(graph)); try { // A* parameter interface astar_search(graph, source_node, astar_heuristic<boost_graph>(destination_node), boost::predecessor_map(&p[0]).distance_map(&d[0]).visitor(astar_visitor<std::size_t>(destination_node))); } catch(exit_astar fg) { std::list<std::size_t> shortest_path; for(std::size_t v = source_node; ; v = p[v]) { shortest_path.push_front(v); if(p[v] == v) break; } auto spi = shortest_path.begin(); std::cout << "node " << source_node << std::endl; for(++spi; spi != shortest_path.end(); ++spi) std::cout << "node " << *spi << std::endl; std::cout << "Shortest A* path from " << source_node << " to " << destination_node << " cost " << d[destination_node] << std::endl; std::cout << shortest_path.size() << std::endl; return 0; } std::cout << "Didn't find a path from " << source_node << "to" << destination_node << "!" << std::endl; return 0; } +++ READ # NODES: 200 Graph statistics: Nodes: 200 Edges: 4000

...

SOURCE NODE 1 Degrees in/out: 1 0 35 Degrees in/out: 192 39 1 SOURCE NODE 1 DESTINATION NODE 192 1 - 47 = 2 47 - 91 = 3 91 - 120 = 1 120 - 175 = 1 175 - 192 = 10 Shortest Dijkstra path from 1 to 192 cost 17 node 1 Shortest A* path from 1 to 192 cost 17 1