[Boost-users] [Graph] Example: astar_search_no_init over an infinite, implicit graph

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
};
}

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

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

    // Same square counts.
    bool adjacentTo(XY const& that) const;

    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 :
    public boost::iterator_facade<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;
    typedef boost::read_write_property_map_tag category;

    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)
{
}

bool XY::adjacentTo(XY const& that) const
{
    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;
}