[Boost-users] [Graph] Newbie on A*

Subject: [Boost-users] [Graph] Newbie on A*
From: Sensei (senseiwa_at_[hidden])
Date: 2014-05-28 03:30:13

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