[Boost-users] [Graph] A* with heterogeneous heuristics

13 Nov 2014

      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 <unordered_map>
#include <vector>
#include <string>
#include <utility>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/astar_search.hpp>

typedef boost::adjacency_list<boost::vecS,
                               boost::vecS,
                               boost::bidirectionalS
                               > graph;

typedef boost::graph_traits<graph>::edge_iterator edge_iterator;

// Custom A* heuristic
template <class Graph, class CostType>
class bestmatch_heuristic : public boost::astar_heuristic<Graph, CostType>
{
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<char, std::size_t> 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<graph, int> h;

     // Predecessors
     std::vector<graph::vertex_descriptor> p(boost::num_vertices(g));

     try
     {
#if 0
         boost::astar_search_tree(// Graph
                                  g,
                                  // Start node
                                  letters['A'],
                                  // Heuristics
                                  bestmatch_heuristic<graph, int>(),
                                  // Predecessor map

boost::predecessor_map(boost::make_iterator_property_map(p.begin(), 
boost::get(boost::vertex_index, g))));
#endif
     }
     catch (end_astar e)
     {

     }

}

[Boost-users] [Graph] A* with heterogeneous heuristics

Sensei