# Boost Users :

Subject: [Boost-users] [Graph] Example: astar_search_no_init over an infinite, implicit graph
From: Luke Meyers (n.luke.meyers_at_[hidden])
Date: 2012-03-20 02:17:26

Having finally gotten this working, I wanted to share it. As the topic
states, this is an implementation of an infinite, implicit graph, and an
example that searches the graph with astar_search_no_init. I didn't find
any examples out there of anyone doing this particular thing, so I hope it
may be helpful to my fellow travelers.

This code is a bastardization of some stuff from a game I'm working on
(blatant plug: http://snarglequest.blogspot.com/) and the "city search"
example code from the BGL docs. I'm sure it could be more concise, but I
hope you'll find it accessible.

Oh, and critiques would of course be welcome. I said it's working, not
perfect; I'm sure there are many things I could be doing in better ways,
and I'd love to know about them.

Luke

/**
* Example use of boost::astar_search_no_init on an infinite,
implicitly-defined graph.
*
* The graph type used here is XYGraph, representing an infinite grid of
squares. Each
* square is connected to its eight neighbors; however, the example shows
how to use
* boost::filtered_graph to make the search take place only along
orthogonal edges.
*/

#include <iostream>
#include <list>
#include <map>
#include <set>
#include <utility>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/operators.hpp>
#include <boost/ref.hpp>

namespace Direction
{
enum id
{
MIN = 0,
N = MIN, S, E, W, NW, NE, SE, SW, NONE
};
}

boost::totally_ordered<XY,
boost::equivalent<XY>
> >
{
typedef int X;
typedef int Y;

XY(X x = 0, Y y = 0);

// Same square counts.

XY & operator=(XY const& that);
XY & operator+=(XY const& that);

bool operator<(XY const& that) const;

X x;
Y y;

XY neighbor(Direction::id direction) const;
std::set<XY> allNeighbors() const;
};

std::ostream & operator<<(std::ostream & os, XY const& xy);

struct neighbor_iterator;

/*
* Model of:
* * Graph
* * IncidenceGraph
*/
struct XYGraph
{
XYGraph();

// Graph concept requirements
typedef XY vertex_descriptor;
typedef std::pair<XY, XY> edge_descriptor;
typedef boost::undirected_tag directed_category;
typedef boost::disallow_parallel_edge_tag edge_parallel_category;
typedef boost::incidence_graph_tag traversal_category;

// IncidenceGraph concept requirements
typedef neighbor_iterator out_edge_iterator;
typedef int degree_size_type;
};

namespace boost
{
template <> struct graph_traits<XYGraph>
{
typedef XYGraph G;

typedef G::vertex_descriptor vertex_descriptor;
typedef G::edge_descriptor edge_descriptor;
typedef G::out_edge_iterator out_edge_iterator;

typedef G::directed_category directed_category;
typedef G::edge_parallel_category edge_parallel_category;
typedef G::traversal_category traversal_category;

typedef G::degree_size_type degree_size_type;

typedef void in_edge_iterator;
typedef void vertex_iterator;
typedef void vertices_size_type;
typedef void edge_iterator;
typedef void edges_size_type;
};
}

// IncidenceGraph concept requirements
std::pair<XYGraph::out_edge_iterator,
XYGraph::out_edge_iterator> out_edges(XYGraph::vertex_descriptor v, XYGraph
const& g);
XYGraph::degree_size_type out_degree(XYGraph::vertex_descriptor v, XYGraph
const& g);
XYGraph::vertex_descriptor source(XYGraph::edge_descriptor e, XYGraph
const& g);
XYGraph::vertex_descriptor target(XYGraph::edge_descriptor e, XYGraph
const& g);

// Iterator
struct neighbor_iterator :
std::pair<XY,XY>,
boost::forward_traversal_tag,
std::pair<XY,XY> >
{
public:
neighbor_iterator();
neighbor_iterator(XY xy, Direction::id direction);

neighbor_iterator & operator=(neighbor_iterator const& that);

std::pair<XY,XY> operator*() const;
void operator++();
bool operator==(neighbor_iterator const& that) const;

bool equal(neighbor_iterator const& that) const { return
operator==(that); }
void increment() { operator++(); }

private:
XY xy;
Direction::id direction;
};

struct orthogonal_only;
template <typename Graph> class distance_heuristic;

struct found_goal {}; // exception for termination

// visitor that terminates when we find the goal
class astar_goal_visitor : public boost::default_astar_visitor
{
public:
astar_goal_visitor(XY goal) : m_goal(goal) {}

virtual void examine_vertex(XY xy, XYGraph const& g) {
std::cout << "Exploring " << xy << "..." << std::endl;
if(xy == m_goal)
throw found_goal();
}
virtual void examine_vertex(XY xy, boost::filtered_graph<XYGraph,
orthogonal_only> const& g) {
std::cout << "Exploring " << xy << "..." << std::endl;
if(xy == m_goal)
throw found_goal();
}
private:
XY m_goal;
};

template <typename K, typename V>
class default_map
{
public:
typedef K key_type;
typedef V data_type;
typedef std::pair<K,V> value_type;

default_map(V const& defaultValue)
: defaultValue(defaultValue)
{}

V & operator[](K const& k)
{
if (m.find(k) == m.end())
{
m[k] = defaultValue;
}
return m[k];
}

private:
std::map<K,V> m;
V const defaultValue;
};

struct PredecessorMap
{
PredecessorMap() {}
PredecessorMap(PredecessorMap const& that) : m(that.m) {}

typedef XY key_type;
typedef XY value_type;
typedef XY & reference_type;

XY & operator[](XY xy) { return m[xy]; }

std::map<XY,XY> m;
};

XY get(PredecessorMap const& pm, XY xy)
{
std::map<XY,XY>::const_iterator found = pm.m.find(xy);
return (found != pm.m.end()) ? found->second : xy;
}

void put(PredecessorMap & pm, XY key, XY value)
{
pm.m[key] = value;
}

// Filter used to traverse grid only along orthogonal (non-diagonal) edges.
struct orthogonal_only
{
typedef std::pair<XY,XY> Edge;
bool operator()(Edge const& edge) const
{
return edge.first.x == edge.second.x || edge.first.y ==
edge.second.y;
}
};

// Euclidean distance heuristic (square root omitted)
template <typename Graph>
class distance_heuristic : public boost::astar_heuristic<Graph, int>
{
public:
distance_heuristic(XY goal)
: m_goal(goal) {}
unsigned operator()(XY xy)
{
int dx = m_goal.x - xy.x;
int dy = m_goal.y - xy.y;
unsigned retval = static_cast<unsigned>(dx * dx + dy * dy);
return retval;
}
private:
XY m_goal;
};

int main(int argc, char **argv)
{
XYGraph baseGraph;
boost::filtered_graph<XYGraph, orthogonal_only> g(baseGraph,
orthogonal_only());
//BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<
boost::filtered_graph<XYGraph, orthogonal_only> >));

XY start(0,0);
XY goal(5,7);

std::cout << "Start vertex: " << start << std::endl;
std::cout << "Goal vertex: " << goal << std::endl;

PredecessorMap p;
typedef boost::associative_property_map< default_map<XY,unsigned> >
DistanceMap;
typedef default_map<XY,unsigned> WrappedDistanceMap;
WrappedDistanceMap wrappedMap =
WrappedDistanceMap(std::numeric_limits<unsigned>::max());
wrappedMap[start] = 0;
DistanceMap d = DistanceMap(wrappedMap);

try {
astar_search_no_init(g,
start,
distance_heuristic<XYGraph>(goal)
, visitor(astar_goal_visitor(goal))
. distance_map(d)
. predecessor_map(boost::ref(p))
. weight_map(boost::associative_property_map<
default_map<std::pair<XY,XY>,unsigned> >(
default_map<std::pair<XY,XY>,unsigned>(1)))
. vertex_index_map(boost::associative_property_map<
std::map<XY,unsigned> >(std::map<XY,unsigned>()))
. rank_map(boost::associative_property_map<
std::map<XY,unsigned> >(std::map<XY,unsigned>()))
. color_map(boost::associative_property_map<
std::map<XY,boost::default_color_type> >(
std::map<XY,boost::default_color_type>()))
. distance_compare(std::less<unsigned>())
. distance_combine(std::plus<unsigned>())
);
} catch(found_goal const&) { // found a path to the goal
std::list<XY> shortest_path;
for(XY xy = goal;; xy = p[xy]) {
shortest_path.push_front(xy);
if(p[xy] == xy)
break;
}
std::cout << "Shortest path from " << start << " to "
<< goal << ": ";
std::list<XY>::iterator spi = shortest_path.begin();
std::cout << start;
for(++spi; spi != shortest_path.end(); ++spi)
std::cout << " -> " << (*spi);
std::cout << std::endl;
return 0;
}

std::cout << "Didn't find a path from " << start << "to"
<< goal << "!" << std::endl;
return 0;
}

XYGraph::XYGraph()
{}

std::pair<XYGraph::out_edge_iterator, XYGraph::out_edge_iterator>
out_edges(XYGraph::vertex_descriptor v,
XYGraph const& g)
{
return std::make_pair(
XYGraph::out_edge_iterator(v, Direction::MIN),
XYGraph::out_edge_iterator(v, Direction::NONE) );
}

XYGraph::degree_size_type
out_degree(XYGraph::vertex_descriptor v,
XYGraph const& g)
{
return v.allNeighbors().size();
}

XYGraph::vertex_descriptor
source(XYGraph::edge_descriptor e,
XYGraph const& g)
{
return e.first;
}

XYGraph::vertex_descriptor target(
XYGraph::edge_descriptor e,
XYGraph const& g)
{
return e.second;
}

neighbor_iterator::neighbor_iterator()
{}

neighbor_iterator::neighbor_iterator(XY xy, Direction::id direction)
: xy(xy)
, direction(direction)
{
}

neighbor_iterator & neighbor_iterator::operator=(neighbor_iterator const&
that)
{
xy = that.xy;
direction = that.direction;
return *this;
}

std::pair<XY,XY> neighbor_iterator::operator*() const
{
std::pair<XY,XY> const retval = std::make_pair(xy,
xy.neighbor(direction));
return retval;
}

void neighbor_iterator::operator++()
{
direction = static_cast<Direction::id>(int(direction) + 1);
}

bool neighbor_iterator::operator==(neighbor_iterator const& that) const
{
return xy == that.xy && direction == that.direction;
}

XY::XY(X x, Y y)
: x(x)
, y(y)
{
}

{
return abs(x - that.x) <= 1 && abs(y - that.y) <= 1;
}

XY & XY::operator=(XY const& that)
{
x = that.x;
y = that.y;
return *this;
}

XY & XY::operator+=(XY const& that)
{
x += that.x;
y += that.y;
return *this;
}

bool XY::operator<(XY const& that) const
{
return x < that.x || (x == that.x && y < that.y);
}

std::ostream & operator<<(std::ostream & os, XY const& xy)
{
os << "(" << xy.x << "," << xy.y << ")";
return os;
}

XY XY::neighbor(Direction::id direction) const
{
using namespace Direction;

int dx = 0, dy = 0;
switch (direction)
{
case NW:
case W:
case SW:
dx = -1;
break;
case NE:
case E:
case SE:
dx = 1;
}
switch (direction)
{
case NW:
case N:
case NE:
dy = -1;
break;
case SW:
case S:
case SE:
dy = 1;
}
XY const neighbor(x + dx, y + dy);
return neighbor;
}

std::set<XY> XY::allNeighbors() const
{
std::set<XY> neighbors;

for (int dx = -1; dx <= 1; ++dx)
for (int dy = -1; dy <= 1; ++dy)
neighbors.insert(XY(x+dx,y+dy));

return neighbors;
}