libs/graph/example/astar-cities.cpp

   1
   2
   3 //
   4 //=======================================================================
   5 // Copyright (c) 2004 Kristopher Beevers
   6 //
   7 // Distributed under the Boost Software License, Version 1.0. (See
   8 // accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10 //=======================================================================
  11 //
  12
  13
  14 #include <boost/graph/astar_search.hpp>
  15 #include <boost/graph/adjacency_list.hpp>
  16 #include <boost/graph/random.hpp>
  17 #include <boost/random.hpp>
  18 #include <boost/graph/graphviz.hpp>
  19 #include <sys/time.h>
  20 #include <vector>
  21 #include <list>
  22 #include <iostream>
  23 #include <fstream>
  24 #include <math.h>    // for sqrt
  25
  26 using namespace boost;
  27 using namespace std;
  28
  29
  30 // auxiliary types
  31 struct location
  32 {
  33   float y, x; // lat, long
  34 };
  35 typedef float cost;
  36
  37 template <class Name, class LocMap>
  38 class city_writer {
  39 public:
  40   city_writer(Name n, LocMap l, float _minx, float _maxx,
  41               float _miny, float _maxy,
  42               unsigned int _ptx, unsigned int _pty)
  43     : name(n), loc(l), minx(_minx), maxx(_maxx), miny(_miny),
  44       maxy(_maxy), ptx(_ptx), pty(_pty) {}
  45   template <class Vertex>
  46   void operator()(ostream& out, const Vertex& v) const {
  47     float px = 1 - (loc[v].x - minx) / (maxx - minx);
  48     float py = (loc[v].y - miny) / (maxy - miny);
  49     out << "[label=\"" << name[v] << "\", pos=\""
  50         << static_cast<unsigned int>(ptx * px) << ","
  51         << static_cast<unsigned int>(pty * py)
  52         << "\", fontsize=\"11\"]";
  53   }
  54 private:
  55   Name name;
  56   LocMap loc;
  57   float minx, maxx, miny, maxy;
  58   unsigned int ptx, pty;
  59 };
  60
  61 template <class WeightMap>
  62 class time_writer {
  63 public:
  64   time_writer(WeightMap w) : wm(w) {}
  65   template <class Edge>
  66   void operator()(ostream &out, const Edge& e) const {
  67     out << "[label=\"" << wm[e] << "\", fontsize=\"11\"]";
  68   }
  69 private:
  70   WeightMap wm;
  71 };
  72
  73
  74 // euclidean distance heuristic
  75 template <class Graph, class CostType, class LocMap>
  76 class distance_heuristic : public astar_heuristic<Graph, CostType>
  77 {
  78 public:
  79   typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  80   distance_heuristic(LocMap l, Vertex goal)
  81     : m_location(l), m_goal(goal) {}
  82   CostType operator()(Vertex u)
  83   {
  84     CostType dx = m_location[m_goal].x - m_location[u].x;
  85     CostType dy = m_location[m_goal].y - m_location[u].y;
  86     return ::sqrt(dx * dx + dy * dy);
  87   }
  88 private:
  89   LocMap m_location;
  90   Vertex m_goal;
  91 };
  92
  93
  94 struct found_goal {}; // exception for termination
  95
  96 // visitor that terminates when we find the goal
  97 template <class Vertex>
  98 class astar_goal_visitor : public boost::default_astar_visitor
  99 {
 100 public:
 101   astar_goal_visitor(Vertex goal) : m_goal(goal) {}
 102   template <class Graph>
 103   void examine_vertex(Vertex u, Graph& g) {
 104     if(u == m_goal)
 105       throw found_goal();
 106   }
 107 private:
 108   Vertex m_goal;
 109 };
 110
 111
 112 int main(int argc, char **argv)
 113 {
 114
 115   // specify some types
 116   typedef adjacency_list<listS, vecS, undirectedS, no_property,
 117     property<edge_weight_t, cost> > mygraph_t;
 118   typedef property_map<mygraph_t, edge_weight_t>::type WeightMap;
 119   typedef mygraph_t::vertex_descriptor vertex;
 120   typedef mygraph_t::edge_descriptor edge_descriptor;
 121   typedef std::pair<int, int> edge;
 122
 123   // specify data
 124   enum nodes {
 125     Troy, LakePlacid, Plattsburgh, Massena, Watertown, Utica,
 126     Syracuse, Rochester, Buffalo, Ithaca, Binghamton, Woodstock,
 127     NewYork, N
 128   };
 129   const char *name[] = {
 130     "Troy", "Lake Placid", "Plattsburgh", "Massena",
 131     "Watertown", "Utica", "Syracuse", "Rochester", "Buffalo",
 132     "Ithaca", "Binghamton", "Woodstock", "New York"
 133   };
 134   location locations[] = { // lat/long
 135     {42.73, 73.68}, {44.28, 73.99}, {44.70, 73.46},
 136     {44.93, 74.89}, {43.97, 75.91}, {43.10, 75.23},
 137     {43.04, 76.14}, {43.17, 77.61}, {42.89, 78.86},
 138     {42.44, 76.50}, {42.10, 75.91}, {42.04, 74.11},
 139     {40.67, 73.94}
 140   };
 141   edge edge_array[] = {
 142     edge(Troy,Utica), edge(Troy,LakePlacid),
 143     edge(Troy,Plattsburgh), edge(LakePlacid,Plattsburgh),
 144     edge(Plattsburgh,Massena), edge(LakePlacid,Massena),
 145     edge(Massena,Watertown), edge(Watertown,Utica),
 146     edge(Watertown,Syracuse), edge(Utica,Syracuse),
 147     edge(Syracuse,Rochester), edge(Rochester,Buffalo),
 148     edge(Syracuse,Ithaca), edge(Ithaca,Binghamton),
 149     edge(Ithaca,Rochester), edge(Binghamton,Troy),
 150     edge(Binghamton,Woodstock), edge(Binghamton,NewYork),
 151     edge(Syracuse,Binghamton), edge(Woodstock,Troy),
 152     edge(Woodstock,NewYork)
 153   };
 154   unsigned int num_edges = sizeof(edge_array) / sizeof(edge);
 155   cost weights[] = { // estimated travel time (mins)
 156     96, 134, 143, 65, 115, 133, 117, 116, 74, 56,
 157     84, 73, 69, 70, 116, 147, 173, 183, 74, 71, 124
 158   };
 159
 160
 161   // create graph
 162   mygraph_t g(N);
 163   WeightMap weightmap = get(edge_weight, g);
 164   for(std::size_t j = 0; j < num_edges; ++j) {
 165     edge_descriptor e; bool inserted;
 166     boost::tie(e, inserted) = add_edge(edge_array[j].first,
 167                                        edge_array[j].second, g);
 168     weightmap[e] = weights[j];
 169   }
 170
 171
 172   // pick random start/goal
 173   boost::mt19937 gen(time(0));
 174   vertex start = random_vertex(g, gen);
 175   vertex goal = random_vertex(g, gen);
 176
 177
 178   cout << "Start vertex: " << name[start] << endl;
 179   cout << "Goal vertex: " << name[goal] << endl;
 180
 181   ofstream dotfile;
 182   dotfile.open("test-astar-cities.dot");
 183   write_graphviz(dotfile, g,
 184                  city_writer<const char **, location*>
 185                   (name, locations, 73.46, 78.86, 40.67, 44.93,
 186                    480, 400),
 187                  time_writer<WeightMap>(weightmap));
 188
 189
 190   vector<mygraph_t::vertex_descriptor> p(num_vertices(g));
 191   vector<cost> d(num_vertices(g));
 192   try {
 193     // call astar named parameter interface
 194     astar_search_tree
 195       (g, start,
 196        distance_heuristic<mygraph_t, cost, location*>
 197         (locations, goal),
 198        predecessor_map(make_iterator_property_map(p.begin(), get(vertex_index, g))).
 199        distance_map(make_iterator_property_map(d.begin(), get(vertex_index, g))).
 200        visitor(astar_goal_visitor<vertex>(goal)));
 201
 202
 203   } catch(found_goal fg) { // found a path to the goal
 204     list<vertex> shortest_path;
 205     for(vertex v = goal;; v = p[v]) {
 206       shortest_path.push_front(v);
 207       if(p[v] == v)
 208         break;
 209     }
 210     cout << "Shortest path from " << name[start] << " to "
 211          << name[goal] << ": ";
 212     list<vertex>::iterator spi = shortest_path.begin();
 213     cout << name[start];
 214     for(++spi; spi != shortest_path.end(); ++spi)
 215       cout << " -> " << name[*spi];
 216     cout << endl << "Total travel time: " << d[goal] << endl;
 217     return 0;
 218   }
 219
 220   cout << "Didn't find a path from " << name[start] << "to"
 221        << name[goal] << "!" << endl;
 222   return 0;
 223
 224 }