<div>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 <font face="'courier new', monospace">astar_search_no_init</font>. �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.</div> <div><br></div><div>This code is a bastardization of some stuff from a game I'm working on (blatant plug: <a href="http://snarglequest.blogspot.com/">http://snarglequest.blogspot.com/</a>) 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.</div> <div><br></div><div>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.</div><div> <br> </div><div>Luke</div><div><br></div><div><font face="'courier new', monospace">/**</font></div><div><font face="'courier new', monospace">�* Example use of boost::astar_search_no_init on an infinite, implicitly-defined graph.</font></div> <div><font face="'courier new', monospace">�*</font></div><div><font face="'courier new', monospace">�* The graph type used here is XYGraph, representing an infinite grid of squares. �Each</font></div><div> <font face="'courier new', monospace">�* square is connected to its eight neighbors; however, the example shows how to use</font></div><div><font face="'courier new', monospace">�* boost::filtered_graph to make the search take place only along orthogonal edges.</font></div> <div><font face="'courier new', monospace">�*/</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">#include <iostream></font></div> <div><font face="'courier new', monospace">#include <list></font></div><div><font face="'courier new', monospace">#include <map></font></div><div><font face="'courier new', monospace">#include <set></font></div> <div><font face="'courier new', monospace">#include <utility></font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">#include <boost/graph/graph_traits.hpp></font></div> <div><font face="'courier new', monospace">#include <boost/graph/astar_search.hpp></font></div><div><font face="'courier new', monospace">#include <boost/graph/filtered_graph.hpp></font></div> <div> <font face="'courier new', monospace">#include <boost/operators.hpp></font></div><div><font face="'courier new', monospace">#include <boost/ref.hpp></font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">namespace Direction</font></div><div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">enum id</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � MIN = 0,</font></div><div><font face="'courier new', monospace">� � N = MIN, S, E, W, NW, NE, SE, SW, NONE</font></div> <div><font face="'courier new', monospace">};</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">struct XY : public boost::additive<XY,</font></div> <div><font face="'courier new', monospace">� � boost::totally_ordered<XY,</font></div><div><font face="'courier new', monospace">� � boost::equivalent<XY></font></div><div><font face="'courier new', monospace">� � > ></font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � typedef int X;</font></div><div><font face="'courier new', monospace">� � typedef int Y;</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � XY(X x = 0, Y y = 0);</font></div><div><font face="'courier new', monospace"><br></font></div> <div><font face="'courier new', monospace">� � // Same square counts.</font></div><div><font face="'courier new', monospace">� � bool adjacentTo(XY const& that) const;</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">� � XY & operator=(XY const& that);</font></div><div><font face="'courier new', monospace">� � XY & operator+=(XY const& that);</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � bool operator<(XY const& that) const;</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">� � X x;</font></div><div><font face="'courier new', monospace">� � Y y;</font></div><div><font face="'courier new', monospace"><br></font></div> <div><font face="'courier new', monospace">� � XY neighbor(Direction::id direction) const;</font></div><div><font face="'courier new', monospace">� � std::set<XY> allNeighbors() const;</font></div><div> <font face="'courier new', monospace">};</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">std::ostream & operator<<(std::ostream & os, XY const& xy);</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">struct neighbor_iterator;</font></div><div><font face="'courier new', monospace"><br></font></div> <div><font face="'courier new', monospace">/*</font></div><div><font face="'courier new', monospace">�* Model of:</font></div><div><font face="'courier new', monospace">�* �* Graph</font></div><div> <font face="'courier new', monospace">�* �* IncidenceGraph</font></div><div><font face="'courier new', monospace">�*/</font></div><div><font face="'courier new', monospace">struct XYGraph</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � XYGraph();</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � // Graph concept requirements</font></div> <div><font face="'courier new', monospace">� � typedef XY � � � � � � � � � � � � � � � �vertex_descriptor;</font></div><div><font face="'courier new', monospace">� � typedef std::pair<XY, XY> � � � � � � � � edge_descriptor;</font></div> <div><font face="'courier new', monospace">� � typedef boost::undirected_tag � � � � � � directed_category;</font></div><div><font face="'courier new', monospace">� � typedef boost::disallow_parallel_edge_tag edge_parallel_category;</font></div> <div><font face="'courier new', monospace">� � typedef boost::incidence_graph_tag � � � �traversal_category;</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � // IncidenceGraph concept requirements</font></div> <div><font face="'courier new', monospace">� � typedef neighbor_iterator � � � � �out_edge_iterator;</font></div><div><font face="'courier new', monospace">� � typedef int � � � � � � � � � � � �degree_size_type;</font></div> <div><font face="'courier new', monospace">};</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">namespace boost</font></div><div><font face="'courier new', monospace">{</font></div> <div><font face="'courier new', monospace">� � template <> struct graph_traits<XYGraph></font></div><div><font face="'courier new', monospace">� � {</font></div><div><font face="'courier new', monospace">� � � � typedef XYGraph G;</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � � � typedef G::vertex_descriptor � � �vertex_descriptor;</font></div><div><font face="'courier new', monospace">� � � � typedef G::edge_descriptor � � � �edge_descriptor;</font></div> <div><font face="'courier new', monospace">� � � � typedef G::out_edge_iterator � � �out_edge_iterator;</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � � � typedef G::directed_category � � �directed_category;</font></div> <div><font face="'courier new', monospace">� � � � typedef G::edge_parallel_category edge_parallel_category;</font></div><div><font face="'courier new', monospace">� � � � typedef G::traversal_category � � traversal_category;</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � � � typedef G::degree_size_type � � � degree_size_type;</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">� � � � typedef void in_edge_iterator;</font></div><div><font face="'courier new', monospace">� � � � typedef void vertex_iterator;</font></div><div> <font face="'courier new', monospace">� � � � typedef void vertices_size_type;</font></div><div><font face="'courier new', monospace">� � � � typedef void edge_iterator;</font></div><div><font face="'courier new', monospace">� � � � typedef void edges_size_type;</font></div> <div><font face="'courier new', monospace">� � };</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">// IncidenceGraph concept requirements</font></div> <div><font face="'courier new', monospace">std::pair<XYGraph::out_edge_iterator,�</font></div><div><font face="'courier new', monospace">XYGraph::out_edge_iterator> out_edges(XYGraph::vertex_descriptor v, XYGraph const& g);</font></div> <div><font face="'courier new', monospace">XYGraph::degree_size_type out_degree(XYGraph::vertex_descriptor v, XYGraph const& g);</font></div><div><font face="'courier new', monospace">XYGraph::vertex_descriptor source(XYGraph::edge_descriptor e, XYGraph const& g);</font></div> <div><font face="'courier new', monospace">XYGraph::vertex_descriptor target(XYGraph::edge_descriptor e, XYGraph const& g);</font></div><div><font face="'courier new', monospace"><br></font></div><div> <font face="'courier new', monospace">// Iterator</font></div><div><font face="'courier new', monospace">struct neighbor_iterator :�</font></div><div><font face="'courier new', monospace">� � public boost::iterator_facade<neighbor_iterator,</font></div> <div><font face="'courier new', monospace">� � � � � � � � � � � � � � � � � std::pair<XY,XY>,</font></div><div><font face="'courier new', monospace">� � � � � � � � � � � � � � � � � boost::forward_traversal_tag,</font></div> <div><font face="'courier new', monospace">� � � � � � � � � � � � � � � � � std::pair<XY,XY> ></font></div><div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">public:</font></div> <div><font face="'courier new', monospace">� � neighbor_iterator();</font></div><div><font face="'courier new', monospace">� � neighbor_iterator(XY xy, Direction::id direction);</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">� � neighbor_iterator & operator=(neighbor_iterator const& that);</font></div><div><font face="'courier new', monospace"><br></font></div><div> <font face="'courier new', monospace">� � std::pair<XY,XY> operator*() const;</font></div><div><font face="'courier new', monospace">� � void operator++();</font></div><div><font face="'courier new', monospace">� � bool operator==(neighbor_iterator const& that) const;</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � bool equal(neighbor_iterator const& that) const { return operator==(that); }</font></div><div> <font face="'courier new', monospace">� � void increment() { operator++(); }</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">private:</font></div> <div><font face="'courier new', monospace">� � XY xy;</font></div><div><font face="'courier new', monospace">� � Direction::id direction;</font></div><div><font face="'courier new', monospace">};</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">struct orthogonal_only;</font></div> <div><font face="'courier new', monospace">template <typename Graph> class distance_heuristic;</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">struct found_goal {}; // exception for termination</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">// visitor that terminates when we find the goal</font></div><div><font face="'courier new', monospace">class astar_goal_visitor : public boost::default_astar_visitor</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">public:</font></div><div><font face="'courier new', monospace">� � astar_goal_visitor(XY goal) : m_goal(goal) {}</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � virtual void examine_vertex(XY xy, XYGraph const& g) {</font></div><div><font face="'courier new', monospace">� � � � std::cout << "Exploring " << xy << "..." << std::endl;</font></div> <div><font face="'courier new', monospace">� � � � if(xy == m_goal)</font></div><div><font face="'courier new', monospace">� � � � � � throw found_goal();</font></div><div><font face="'courier new', monospace">� � }</font></div> <div><font face="'courier new', monospace">� � virtual void examine_vertex(XY xy, boost::filtered_graph<XYGraph, orthogonal_only> const& g) {</font></div><div><font face="'courier new', monospace">� � � � std::cout << "Exploring " << xy << "..." << std::endl;</font></div> <div><font face="'courier new', monospace">� � � � if(xy == m_goal)</font></div><div><font face="'courier new', monospace">� � � � � � throw found_goal();</font></div><div><font face="'courier new', monospace">� � }</font></div> <div><font face="'courier new', monospace">private:</font></div><div><font face="'courier new', monospace">� � XY m_goal;</font></div><div><font face="'courier new', monospace">};</font></div><div> <font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">template <typename K, typename V></font></div><div><font face="'courier new', monospace">class default_map</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">public:</font></div><div><font face="'courier new', monospace">� � typedef K key_type;</font></div> <div><font face="'courier new', monospace">� � typedef V data_type;</font></div><div><font face="'courier new', monospace">� � typedef std::pair<K,V> value_type;</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">� � default_map(V const& defaultValue)</font></div><div><font face="'courier new', monospace">� � � � : defaultValue(defaultValue)</font></div><div> <font face="'courier new', monospace">� � {}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � V & operator[](K const& k)</font></div> <div><font face="'courier new', monospace">� � {</font></div><div><font face="'courier new', monospace">� � � � if (m.find(k) == m.end())</font></div><div><font face="'courier new', monospace">� � � � {</font></div> <div><font face="'courier new', monospace">� � � � � � m[k] = defaultValue;</font></div><div><font face="'courier new', monospace">� � � � }</font></div><div><font face="'courier new', monospace">� � � � return m[k];</font></div> <div><font face="'courier new', monospace">� � }</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">private:</font></div><div><font face="'courier new', monospace">� � std::map<K,V> m;</font></div> <div><font face="'courier new', monospace">� � V const defaultValue;</font></div><div><font face="'courier new', monospace">};</font></div><div><font face="'courier new', monospace"><br></font></div> <div><font face="'courier new', monospace">struct PredecessorMap</font></div><div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � PredecessorMap() {}</font></div> <div><font face="'courier new', monospace">� � PredecessorMap(PredecessorMap const& that) : m(that.m) {}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � typedef XY key_type;</font></div> <div><font face="'courier new', monospace">� � typedef XY value_type;</font></div><div><font face="'courier new', monospace">� � typedef XY & reference_type;</font></div><div><font face="'courier new', monospace">� � typedef boost::read_write_property_map_tag category;</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � XY & operator[](XY xy) { return m[xy]; }</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">� � std::map<XY,XY> m;</font></div><div><font face="'courier new', monospace">};</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">XY get(PredecessorMap const& pm, XY xy)</font></div><div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � std::map<XY,XY>::const_iterator found = pm.m.find(xy);</font></div> <div><font face="'courier new', monospace">� � return (found != pm.m.end()) ? found->second : xy;</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">void put(PredecessorMap & pm, XY key, XY value)</font></div><div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � pm.m[key] = value;</font></div> <div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">// Filter used to traverse grid only along orthogonal (non-diagonal) edges.</font></div> <div><font face="'courier new', monospace">struct orthogonal_only</font></div><div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � typedef std::pair<XY,XY> Edge;</font></div> <div><font face="'courier new', monospace">� � bool operator()(Edge const& edge) const</font></div><div><font face="'courier new', monospace">� � {</font></div><div><font face="'courier new', monospace">� � � � return edge.first.x == edge.second.x || edge.first.y == edge.second.y;</font></div> <div><font face="'courier new', monospace">� � }</font></div><div><font face="'courier new', monospace">};</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">// Euclidean distance heuristic (square root omitted)</font></div> <div><font face="'courier new', monospace">template <typename Graph></font></div><div><font face="'courier new', monospace">class distance_heuristic : public boost::astar_heuristic<Graph, int></font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">public:</font></div><div><font face="'courier new', monospace">� � distance_heuristic(XY goal)</font></div> <div><font face="'courier new', monospace">� � � � : m_goal(goal) {}</font></div><div><font face="'courier new', monospace">� � unsigned operator()(XY xy)</font></div><div><font face="'courier new', monospace">� � {</font></div> <div><font face="'courier new', monospace">� � � � int dx = m_goal.x - xy.x;</font></div><div><font face="'courier new', monospace">� � � � int dy = m_goal.y - xy.y;</font></div><div><font face="'courier new', monospace">� � � � unsigned retval = static_cast<unsigned>(dx * dx + dy * dy);</font></div> <div><font face="'courier new', monospace">� � � � return retval;</font></div><div><font face="'courier new', monospace">� � }</font></div><div><font face="'courier new', monospace">private:</font></div> <div><font face="'courier new', monospace">� � XY m_goal;</font></div><div><font face="'courier new', monospace">};</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">int main(int argc, char **argv)</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � XYGraph baseGraph;</font></div><div><font face="'courier new', monospace">� � boost::filtered_graph<XYGraph, orthogonal_only> g(baseGraph, orthogonal_only());</font></div> <div><font face="'courier new', monospace">� � //BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< boost::filtered_graph<XYGraph, orthogonal_only> >));</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">� � XY start(0,0);</font></div><div><font face="'courier new', monospace">� � XY goal(5,7);</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">� � std::cout << "Start vertex: " << start << std::endl;</font></div><div><font face="'courier new', monospace">� � std::cout << "Goal vertex: " << goal << std::endl;</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � PredecessorMap p;</font></div><div><font face="'courier new', monospace">� � typedef boost::associative_property_map< default_map<XY,unsigned> > DistanceMap;</font></div> <div><font face="'courier new', monospace">� � typedef default_map<XY,unsigned> WrappedDistanceMap;</font></div><div><font face="'courier new', monospace">� � WrappedDistanceMap wrappedMap = WrappedDistanceMap(std::numeric_limits<unsigned>::max());</font></div> <div><font face="'courier new', monospace">� � wrappedMap[start] = 0;</font></div><div><font face="'courier new', monospace">� � DistanceMap d = DistanceMap(wrappedMap);</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">� � try {</font></div><div><font face="'courier new', monospace">� � � � astar_search_no_init(g,�</font></div><div><font face="'courier new', monospace">� � � � � � start,</font></div> <div><font face="'courier new', monospace">� � � � � � distance_heuristic<XYGraph>(goal)</font></div><div><font face="'courier new', monospace">� � � � � � , visitor(astar_goal_visitor(goal))</font></div> <div><font face="'courier new', monospace">� � � � � � . distance_map(d)</font></div><div><font face="'courier new', monospace">� � � � � � . predecessor_map(boost::ref(p))</font></div><div><font face="'courier new', monospace">� � � � � � . weight_map(boost::associative_property_map< default_map<std::pair<XY,XY>,unsigned> >(</font></div> <div><font face="'courier new', monospace">� � � � � � � � default_map<std::pair<XY,XY>,unsigned>(1)))</font></div><div><font face="'courier new', monospace">� � � � � � . vertex_index_map(boost::associative_property_map< std::map<XY,unsigned> >(std::map<XY,unsigned>()))</font></div> <div><font face="'courier new', monospace">� � � � � � . rank_map(boost::associative_property_map< std::map<XY,unsigned> >(std::map<XY,unsigned>()))</font></div><div><font face="'courier new', monospace">� � � � � � . color_map(boost::associative_property_map< std::map<XY,boost::default_color_type> >(</font></div> <div><font face="'courier new', monospace">� � � � � � � � std::map<XY,boost::default_color_type>()))</font></div><div><font face="'courier new', monospace">� � � � � � . distance_compare(std::less<unsigned>())</font></div> <div><font face="'courier new', monospace">� � � � � � . distance_combine(std::plus<unsigned>())</font></div><div><font face="'courier new', monospace">� � � � � � );</font></div><div><font face="'courier new', monospace">� � } catch(found_goal const&) { // found a path to the goal</font></div> <div><font face="'courier new', monospace">� � � � std::list<XY> shortest_path;</font></div><div><font face="'courier new', monospace">� � � � for(XY xy = goal;; xy = p[xy]) {</font></div><div><font face="'courier new', monospace">� � � � � � shortest_path.push_front(xy);</font></div> <div><font face="'courier new', monospace">� � � � � � if(p[xy] == xy)</font></div><div><font face="'courier new', monospace">� � � � � � � � break;</font></div><div><font face="'courier new', monospace">� � � � }</font></div> <div><font face="'courier new', monospace">� � � � std::cout << "Shortest path from " << start << " to "</font></div><div><font face="'courier new', monospace">� � � � � � << goal << ": ";</font></div> <div><font face="'courier new', monospace">� � � � std::list<XY>::iterator spi = shortest_path.begin();</font></div><div><font face="'courier new', monospace">� � � � std::cout << start;</font></div> <div><font face="'courier new', monospace">� � � � for(++spi; spi != shortest_path.end(); ++spi)�</font></div><div><font face="'courier new', monospace">� � � � � � std::cout << " -> " << (*spi);</font></div> <div><font face="'courier new', monospace">� � � � std::cout << std::endl;</font></div><div><font face="'courier new', monospace">� � � � return 0;</font></div><div><font face="'courier new', monospace">� � }</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � std::cout << "Didn't find a path from " << start << "to"</font></div> <div><font face="'courier new', monospace">� � � � << goal << "!" << std::endl;</font></div><div><font face="'courier new', monospace">� � return 0;</font></div><div><font face="'courier new', monospace">}</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">XYGraph::XYGraph()</font></div><div><font face="'courier new', monospace">{}</font></div><div> <font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">std::pair<XYGraph::out_edge_iterator, XYGraph::out_edge_iterator>�</font></div><div><font face="'courier new', monospace">out_edges(XYGraph::vertex_descriptor v,</font></div> <div><font face="'courier new', monospace">� � � � � XYGraph const& g)</font></div><div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � return std::make_pair(</font></div> <div><font face="'courier new', monospace">� � � � XYGraph::out_edge_iterator(v, Direction::MIN),�</font></div><div><font face="'courier new', monospace">� � � � XYGraph::out_edge_iterator(v, Direction::NONE) );</font></div> <div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">XYGraph::degree_size_type�</font></div> <div><font face="'courier new', monospace">out_degree(XYGraph::vertex_descriptor v,</font></div><div><font face="'courier new', monospace">� � � � � �XYGraph const& g)</font></div><div><font face="'courier new', monospace">{</font></div> <div><font face="'courier new', monospace">� � return v.allNeighbors().size();</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div> <div><font face="'courier new', monospace">XYGraph::vertex_descriptor�</font></div><div><font face="'courier new', monospace">source(XYGraph::edge_descriptor e,</font></div><div><font face="'courier new', monospace">� � � �XYGraph const& g)</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � return e.first;</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">XYGraph::vertex_descriptor target(</font></div><div><font face="'courier new', monospace">� � XYGraph::edge_descriptor e,</font></div><div><font face="'courier new', monospace">� � XYGraph const& g)</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � return e.second;</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">neighbor_iterator::neighbor_iterator()</font></div><div><font face="'courier new', monospace">{}</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">neighbor_iterator::neighbor_iterator(XY xy, Direction::id direction)</font></div><div><font face="'courier new', monospace">: xy(xy)</font></div><div> <font face="'courier new', monospace">, direction(direction)</font></div><div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">neighbor_iterator & neighbor_iterator::operator=(neighbor_iterator const& that)</font></div><div><font face="'courier new', monospace">{</font></div> <div><font face="'courier new', monospace">� � xy = that.xy;</font></div><div><font face="'courier new', monospace">� � direction = that.direction;</font></div><div><font face="'courier new', monospace">� � return *this;</font></div> <div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">std::pair<XY,XY> neighbor_iterator::operator*() const</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � std::pair<XY,XY> const retval = std::make_pair(xy, xy.neighbor(direction));</font></div><div><font face="'courier new', monospace">� � return retval;</font></div> <div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">void neighbor_iterator::operator++()</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � direction = static_cast<Direction::id>(int(direction) + 1);</font></div><div><font face="'courier new', monospace">}</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">bool neighbor_iterator::operator==(neighbor_iterator const& that) const</font></div><div><font face="'courier new', monospace">{</font></div> <div><font face="'courier new', monospace">� � return xy == that.xy && direction == that.direction;</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">XY::XY(X x, Y y)</font></div><div><font face="'courier new', monospace">: x(x)</font></div> <div><font face="'courier new', monospace">, y(y)</font></div><div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br> </font></div><div><font face="'courier new', monospace">bool XY::adjacentTo(XY const& that) const</font></div><div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � return abs(x - that.x) <= 1 && abs(y - that.y) <= 1;</font></div> <div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">XY & XY::operator=(XY const& that)</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � x = that.x;</font></div><div><font face="'courier new', monospace">� � y = that.y;</font></div> <div><font face="'courier new', monospace">� � return *this;</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">XY & XY::operator+=(XY const& that)</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � x += that.x;</font></div><div><font face="'courier new', monospace">� � y += that.y;</font></div> <div><font face="'courier new', monospace">� � return *this;</font></div><div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">bool XY::operator<(XY const& that) const</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � return x < that.x || (x == that.x && y < that.y);</font></div><div><font face="'courier new', monospace">}</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">std::ostream & operator<<(std::ostream & os, XY const& xy)</font></div><div><font face="'courier new', monospace">{</font></div> <div><font face="'courier new', monospace">� � os << "(" << xy.x << "," << xy.y << ")";</font></div><div><font face="'courier new', monospace">� � return os;</font></div> <div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">XY XY::neighbor(Direction::id direction) const</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � using namespace Direction;</font></div><div><font face="'courier new', monospace"><br></font></div> <div><font face="'courier new', monospace">� � int dx = 0, dy = 0;</font></div><div><font face="'courier new', monospace">� � switch (direction)</font></div><div><font face="'courier new', monospace">� � {</font></div> <div><font face="'courier new', monospace">� � case NW:</font></div><div><font face="'courier new', monospace">� � case W:</font></div><div><font face="'courier new', monospace">� � case SW:</font></div> <div><font face="'courier new', monospace">� � � � dx = -1;</font></div><div><font face="'courier new', monospace">� � � � break;</font></div><div><font face="'courier new', monospace">� � case NE:</font></div> <div><font face="'courier new', monospace">� � case E:</font></div><div><font face="'courier new', monospace">� � case SE:</font></div><div><font face="'courier new', monospace">� � � � dx = 1;</font></div> <div><font face="'courier new', monospace">� � }</font></div><div><font face="'courier new', monospace">� � switch (direction)</font></div><div><font face="'courier new', monospace">� � {</font></div> <div><font face="'courier new', monospace">� � case NW:</font></div><div><font face="'courier new', monospace">� � case N:</font></div><div><font face="'courier new', monospace">� � case NE:</font></div> <div><font face="'courier new', monospace">� � � � dy = -1; ��</font></div><div><font face="'courier new', monospace">� � � � break;</font></div><div><font face="'courier new', monospace">� � case SW:</font></div> <div><font face="'courier new', monospace">� � case S:</font></div><div><font face="'courier new', monospace">� � case SE:</font></div><div><font face="'courier new', monospace">� � � � dy = 1;</font></div> <div><font face="'courier new', monospace">� � }</font></div><div><font face="'courier new', monospace">� � XY const neighbor(x + dx, y + dy);</font></div><div><font face="'courier new', monospace">� � return neighbor;</font></div> <div><font face="'courier new', monospace">}</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">std::set<XY> XY::allNeighbors() const</font></div> <div><font face="'courier new', monospace">{</font></div><div><font face="'courier new', monospace">� � std::set<XY> neighbors;</font></div><div><font face="'courier new', monospace"><br></font></div> <div><font face="'courier new', monospace">� � for (int dx = -1; dx <= 1; ++dx)</font></div><div><font face="'courier new', monospace">� � � � for (int dy = -1; dy <= 1; ++dy)</font></div><div><font face="'courier new', monospace">� � � � � � neighbors.insert(XY(x+dx,y+dy));</font></div> <div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">� � return neighbors;</font></div><div><font face="'courier new', monospace">}</font></div><div> <br></div>