[Boost-commit] svn:boost r64063 - trunk/libs/graph/example

Subject: [Boost-commit] svn:boost r64063 - trunk/libs/graph/example
From: jewillco_at_[hidden]
Date: 2010-07-15 21:43:09

Author: jewillco
Date: 2010-07-15 21:43:08 EDT (Thu, 15 Jul 2010)
New Revision: 64063
URL: http://svn.boost.org/trac/boost/changeset/64063

Log:
Added implicit_graph and astar_maze examples from W. P. McNeill
Added:
   trunk/libs/graph/example/astar_maze.cpp   (contents, props changed)
   trunk/libs/graph/example/implicit_graph.cpp   (contents, props changed)
Text files modified: 
   trunk/libs/graph/example/Jamfile.v2 |     2 ++                                      
   1 files changed, 2 insertions(+), 0 deletions(-)

Modified: trunk/libs/graph/example/Jamfile.v2
==============================================================================
--- trunk/libs/graph/example/Jamfile.v2	(original)
+++ trunk/libs/graph/example/Jamfile.v2	2010-07-15 21:43:08 EDT (Thu, 15 Jul 2010)
@@ -27,3 +27,5 @@
 exe boykov_kolmogorov-eg : boykov_kolmogorov-eg.cpp ;
 exe ospf-example : ospf-example.cpp ../build//boost_graph ;
 # exe cc-internet : cc-internet.cpp ../build//boost_graph ;
+exe implicit_graph : implicit_graph.cpp ;
+exe astar_maze : astar_maze.cpp ;

Added: trunk/libs/graph/example/astar_maze.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/astar_maze.cpp	2010-07-15 21:43:08 EDT (Thu, 15 Jul 2010)
@@ -0,0 +1,311 @@
+
+//          Copyright W.P. McNeill 2010.
+// Distributed under the Boost Software License, Version 1.0.
+//    (See accompanying file LICENSE_1_0.txt or copy at
+//          http://www.boost.org/LICENSE_1_0.txt)
+
+
+// This program uses the A-star search algorithm in the Boost Graph Library to
+// solve a maze.  It is an example of how to apply Boost Graph Library
+// algorithms to implicit graphs.
+//
+// This program generates a random maze and then tries to find the shortest
+// path from the lower left-hand corner to the upper right-hand corner.  Mazes
+// are represented by two-dimensional grids where a cell in the grid may
+// contain a barrier.  You may move up, down, right, or left to any adjacent
+// cell that does not contain a barrier.
+//
+// Once a maze solution has been attempted, the maze is printed.  If a
+// solution was found it will be shown in the maze printout and its length
+// will be returned.  Note that not all mazes have solutions.
+//
+// The default maze size is 20x10, though different dimensions may be
+// specified on the command line.
+
+
+#include <boost/graph/astar_search.hpp>
+#include <boost/graph/filtered_graph.hpp>
+#include <boost/graph/grid_graph.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/random/uniform_int.hpp>
+#include <boost/random/variate_generator.hpp>
+#include <boost/unordered_map.hpp>
+#include <boost/unordered_set.hpp>
+#include <ctime>
+#include <iostream>
+
+boost::mt19937 random_generator;
+
+// Distance traveled in the maze
+typedef double distance;
+
+#define GRID_RANK 2
+typedef boost::grid_graph<GRID_RANK> grid;
+typedef boost::graph_traits<grid>::vertex_descriptor vertex_descriptor;
+typedef boost::graph_traits<grid>::vertices_size_type vertices_size_type;
+
+// A hash function for vertices.
+struct vertex_hash:std::unary_function<vertex_descriptor, std::size_t> {
+  std::size_t operator()(vertex_descriptor const& u) const {
+    std::size_t seed = 0;
+    boost::hash_combine(seed, u[0]);
+    boost::hash_combine(seed, u[1]);
+    return seed;
+  }
+};
+
+typedef boost::unordered_set<vertex_descriptor, vertex_hash> vertex_set;
+typedef boost::vertex_subset_complement_filter<grid, vertex_set>::type
+        filtered_grid;
+
+// A searchable maze
+//
+// The maze is grid of locations which can either be empty or contain a
+// barrier.  You can move to an adjacent location in the grid by going up,
+// down, left and right.  Moving onto a barrier is not allowed.  The maze can
+// be solved by finding a path from the lower-left-hand corner to the
+// upper-right-hand corner.  If no open path exists between these two
+// locations, the maze is unsolvable.
+//
+// The maze is implemented as a filtered grid graph where locations are
+// vertices.  Barrier vertices are filtered out of the graph.
+//
+// A-star search is used to find a path through the maze. Each edge has a
+// weight of one, so the total path length is equal to the number of edges
+// traversed.
+class maze {
+public:
+  friend std::ostream& operator<<(std::ostream&, const maze&);
+  friend maze random_maze(std::size_t, std::size_t);
+
+  maze():m_grid(create_grid(0, 0)),m_barrier_grid(create_barrier_grid()) {};
+  maze(std::size_t x, std::size_t y):m_grid(create_grid(x, y)),
+       m_barrier_grid(create_barrier_grid()) {};
+
+  // The length of the maze along the specified dimension.
+  vertices_size_type length(std::size_t d) const {return m_grid.length(d);}
+
+  bool has_barrier(vertex_descriptor u) const {
+    return m_barriers.find(u) != m_barriers.end();
+  }
+
+  // Try to find a path from the lower-left-hand corner source (0,0) to the
+  // upper-right-hand corner goal (x-1, y-1).
+  vertex_descriptor source() const {return vertex(0, m_grid);}
+  vertex_descriptor goal() const {
+    return vertex(num_vertices(m_grid)-1, m_grid);
+  }
+
+  bool solve();
+  bool solved() const {return !m_solution.empty();}
+  bool solution_contains(vertex_descriptor u) const {
+    return m_solution.find(u) != m_solution.end();
+  }
+
+private:
+  // Create the underlying rank-2 grid with the specified dimensions.
+  grid create_grid(std::size_t x, std::size_t y) {
+    boost::array<std::size_t, GRID_RANK> lengths = { {x, y} };
+    return grid(lengths);
+  }
+
+  // Filter the barrier vertices out of the underlying grid.
+  filtered_grid create_barrier_grid() {
+    return boost::make_vertex_subset_complement_filter(m_grid, m_barriers);
+  }
+
+  // The grid underlying the maze
+  grid m_grid;
+  // The underlying maze grid with barrier vertices filtered out
+  filtered_grid m_barrier_grid;
+  // The barriers in the maze
+  vertex_set m_barriers;
+  // The vertices on a solution path through the maze
+  vertex_set m_solution;
+  // The length of the solution path
+  distance m_solution_length;
+};
+
+
+// Euclidean heuristic for a grid
+//
+// This calculates the Euclidean distance between a vertex and a goal
+// vertex.
+class euclidean_heuristic:
+      public boost::astar_heuristic<filtered_grid, double>
+{
+public:
+  euclidean_heuristic(vertex_descriptor goal):m_goal(goal) {};
+
+  double operator()(vertex_descriptor v) {
+    return sqrt(pow(m_goal[0] - v[0], 2) + pow(m_goal[1] - v[1], 2));
+  }
+
+private:
+  vertex_descriptor m_goal;
+};
+
+// Exception thrown when the goal vertex is found
+struct found_goal {};
+
+// Visitor that terminates when we find the goal vertex
+struct astar_goal_visitor:public boost::default_astar_visitor {
+  astar_goal_visitor(vertex_descriptor goal):m_goal(goal) {};
+
+  void examine_vertex(vertex_descriptor u, const filtered_grid&) {
+    if (u == m_goal)
+      throw found_goal();
+  }
+
+private:
+  vertex_descriptor m_goal;
+};
+
+// Solve the maze using A-star search.  Return true if a solution was found.
+bool maze::solve() {
+  boost::static_property_map<distance> weight(1);
+  // The predecessor map is a vertex-to-vertex mapping.
+  typedef boost::unordered_map<vertex_descriptor,
+                               vertex_descriptor,
+                               vertex_hash> pred_map;
+  pred_map predecessor;
+  boost::associative_property_map<pred_map> pred_pmap(predecessor);
+  // The distance map is a vertex-to-distance mapping.
+  typedef boost::unordered_map<vertex_descriptor,
+                               distance,
+                               vertex_hash> dist_map;
+  dist_map distance;
+  boost::associative_property_map<dist_map> dist_pmap(distance);
+
+  vertex_descriptor s = source();
+  vertex_descriptor g = goal();
+  euclidean_heuristic heuristic(g);
+  astar_goal_visitor visitor(g);
+
+  try {
+    astar_search(m_barrier_grid, s, heuristic,
+                 boost::weight_map(weight).
+                 predecessor_map(pred_pmap).
+                 distance_map(dist_pmap).
+                 visitor(visitor) );
+  } catch(found_goal fg) {
+    // Walk backwards from the goal through the predecessor chain adding
+    // vertices to the solution path.
+    for (vertex_descriptor u = g; u != s; u = predecessor[u])
+      m_solution.insert(u);
+    m_solution.insert(s);
+    m_solution_length = distance[g];
+    return true;
+  }
+
+  return false;
+}
+
+
+#define BARRIER "#"
+// Print the maze as an ASCII map.
+std::ostream& operator<<(std::ostream& output, const maze& m) {
+  // Header
+  for (vertices_size_type i = 0; i < m.length(0)+2; i++)
+    output << BARRIER;
+  output << std::endl;
+  // Body
+  for (int y = m.length(1)-1; y >= 0; y--) {
+    // Enumerate rows in reverse order and columns in regular order so that
+    // (0,0) appears in the lower left-hand corner.  This requires that y be
+    // int and not the unsigned vertices_size_type because the loop exit
+    // condition is y==-1.
+    for (vertices_size_type x = 0; x < m.length(0); x++) {
+      // Put a barrier on the left-hand side.
+      if (x == 0)
+        output << BARRIER;
+      // Put the character representing this point in the maze grid.
+      vertex_descriptor u = {{x, y}};
+      if (m.solution_contains(u))
+        output << ".";
+      else if (m.has_barrier(u))
+        output << BARRIER;
+      else
+        output << " ";
+      // Put a barrier on the right-hand side.
+      if (x == m.length(0)-1)
+        output << BARRIER;
+    }
+    // Put a newline after every row except the last one.
+    output << std::endl;
+  }
+  // Footer
+  for (vertices_size_type i = 0; i < m.length(0)+2; i++)
+    output << BARRIER;
+  if (m.solved())
+    output << std::endl << "Solution length " << m.m_solution_length;
+  return output;
+}
+
+// Return a random integer in the interval [a, b].
+std::size_t random_int(std::size_t a, std::size_t b) {
+  if (b < a)
+    b = a;
+  boost::uniform_int<> dist(a, b);
+  boost::variate_generator<boost::mt19937&, boost::uniform_int<> >
+  generate(random_generator, dist);
+  return generate();
+}
+
+// Generate a maze with a random assignment of barriers.
+maze random_maze(std::size_t x, std::size_t y) {
+  maze m(x, y);
+  vertices_size_type n = num_vertices(m.m_grid);
+  vertex_descriptor s = m.source();
+  vertex_descriptor g = m.goal();
+  // One quarter of the cells in the maze should be barriers.
+  int barriers = n/4;
+  while (barriers > 0) {
+    // Choose horizontal or vertical direction.
+    std::size_t direction = random_int(0, 1);
+    // Walls range up to one quarter the dimension length in this direction.
+    vertices_size_type wall = random_int(1, m.length(direction)/4);
+    // Create the wall while decrementing the total barrier count.
+    vertex_descriptor u = vertex(random_int(0, n-1), m.m_grid);
+    while (wall) {
+      // Start and goal spaces should never be barriers.
+      if (u != s && u != g) {
+        wall--;
+        if (!m.has_barrier(u)) {
+          m.m_barriers.insert(u);
+          barriers--;
+        }
+      }
+      vertex_descriptor v = m.m_grid.next(u, direction);
+      // Stop creating this wall if we reached the maze's edge.
+      if (u == v)
+        break;
+      u = v;
+    }
+  }
+  return m;
+}
+
+
+int main (int argc, char const *argv[]) {
+  // The default maze size is 20x10.  A different size may be specified on
+  // the command line.
+  std::size_t x = 20;
+  std::size_t y = 10;
+
+  if (argc == 3) {
+    x = boost::lexical_cast<std::size_t>(argv[1]);
+    y = boost::lexical_cast<std::size_t>(argv[2]);
+  }
+
+  random_generator.seed(std::time(0));
+  maze m = random_maze(x, y);
+
+  if (m.solve())
+    std::cout << "Solved the maze." << std::endl;
+  else
+    std::cout << "The maze is not solvable." << std::endl;
+  std::cout << m << std::endl;
+  return 0;
+}

Added: trunk/libs/graph/example/implicit_graph.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/implicit_graph.cpp	2010-07-15 21:43:08 EDT (Thu, 15 Jul 2010)
@@ -0,0 +1,544 @@
+
+//          Copyright W.P. McNeill 2010.
+// Distributed under the Boost Software License, Version 1.0.
+//    (See accompanying file LICENSE_1_0.txt or copy at
+//          http://www.boost.org/LICENSE_1_0.txt)
+
+
+#include <boost/graph/adjacency_iterator.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/iterator/counting_iterator.hpp>
+#include <boost/iterator/iterator_facade.hpp>
+#include <boost/lexical_cast.hpp>
+#include <iostream>
+#include <utility>
+
+
+/*
+This file defines a simple example of a read-only implicit weighted graph
+built using the Boost Graph Library. It can be used as a starting point for
+developers creating their own implicit graphs.
+
+The graph models the following concepts:
+  Graph
+  IncidenceGraph
+  BidirectionalGraph
+  AdjacencyGraph
+  VertexListGraph
+  EdgeListGraph
+  AdjacencyMatrix
+  ReadablePropertyGraph
+
+The graph defined here is a ring graph, a graph whose vertices are arranged in
+a ring so that each vertex has exactly two neighbors. For example, here is a
+ring graph with five nodes.
+
+                                    0
+                                  /   \
+                                4      1
+                                |      |
+                                3 ---- 2
+
+The edges of this graph are undirected and each has a weight that is a
+function of its position in the graph.
+
+The vertices indexed are by integer and arranged sequentially so that each
+vertex i is adjacent to i-1 for i>0 and i+1 for i<n-1.  Vertex 0 is also
+adjacent to vertex n-1.  Edges are indexed by pairs of vertex indices.
+
+Various aspects of the graph are modeled by the following classes:
+
+  ring_graph
+    The graph class instantiated by a client. This defines types for the
+    concepts that this graph models and keeps track of the number of vertices
+    in the graph.
+
+  ring_incident_edge_iterator
+    This is an iterator that ranges over edges incident on a given vertex. The
+    behavior of this iterator defines the ring topology. Other iterators that
+    make reference to the graph structure are defined in terms of this one.
+
+  edge_weight_map
+    This defines a property map between edges and weights. Here edges have a
+    weight equal to the average of their endpoint vertex indices, i.e. edge
+    (2,3) has weight 2.5, edge (0,4) has weight 2, etc.
+
+  boost::property_map<graph, boost::edge_weight_t>
+    This tells Boost to associate the edges of the ring graph with the edge
+    weight map.
+
+Along with these classes, the graph concepts are modeled by various valid
+expression functions defined below.  This example also defines a
+get(boost::vertex_index_t, const ring_graph&) function which isn’t part of a
+graph concept, but is used for Dijkstra search.
+
+Apart from graph, client code should not instantiate the model classes
+directly. Instead it should access them and their properties via
+graph_traits<...> and property_traits<...> lookups. For convenience,
+this example defines short names for all these properties that client code can
+use.
+*/
+
+// Forward declarations
+class ring_graph;
+class ring_incident_edge_iterator;
+class ring_adjacency_iterator;
+class ring_edge_iterator;
+struct edge_weight_map;
+
+// ReadablePropertyGraph associated types
+namespace boost {
+  template<>
+  struct property_map< ring_graph, edge_weight_t > {
+    typedef edge_weight_map type;
+    typedef edge_weight_map const_type;
+  };
+}
+
+// Tag values that specify the traversal type in graph::traversal_category.
+struct ring_traversal_catetory:
+  virtual public boost::bidirectional_graph_tag,
+  virtual public boost::adjacency_graph_tag,
+  virtual public boost::vertex_list_graph_tag,
+  virtual public boost::edge_list_graph_tag
+  {};
+
+
+/*
+Undirected graph of vertices arranged in a ring shape.
+
+Vertices are indexed by integer, and edges connect vertices with consecutive
+indices.  Vertex 0 is also adjacent to the vertex n-1.
+*/
+class ring_graph {
+public:
+  // Graph associated types
+  typedef std::size_t vertex_descriptor;
+  typedef boost::undirected_tag directed_category;
+  typedef boost::disallow_parallel_edge_tag edge_parallel_category;
+  typedef ring_traversal_catetory traversal_category;
+
+  // IncidenceGraph associated types
+  typedef std::pair<vertex_descriptor, vertex_descriptor> edge_descriptor;
+  typedef ring_incident_edge_iterator out_edge_iterator;
+  typedef std::size_t degree_size_type;
+
+  // BidirectionalGraph associated types
+  // Note that undirected graphs make no distinction between in- and out-
+  // edges.
+  typedef ring_incident_edge_iterator in_edge_iterator;
+
+  // AdjacencyGraph associated types
+  typedef ring_adjacency_iterator adjacency_iterator;
+
+  // VertexListGraph associated types
+  typedef boost::counting_iterator<vertex_descriptor> vertex_iterator;
+  typedef std::size_t vertices_size_type;
+
+  // EdgeListGraph associated types
+  typedef ring_edge_iterator edge_iterator;
+  typedef std::size_t edges_size_type;
+
+  // This type is not part of a graph concept, but is used to return the
+  // default vertex index map used by the Dijkstra search algorithm.
+  typedef vertex_descriptor vertex_property_type;
+
+  ring_graph(std::size_t n):m_n(n) {};
+  std::size_t n() const {return m_n;}
+private:
+  // The number of vertices in the graph.
+  std::size_t m_n;
+};
+
+// Use these graph_traits parameterizations to refer to the associated
+// graph types.
+typedef boost::graph_traits<ring_graph>::vertex_descriptor vertex_descriptor;
+typedef boost::graph_traits<ring_graph>::edge_descriptor edge_descriptor;
+typedef boost::graph_traits<ring_graph>::out_edge_iterator out_edge_iterator;
+typedef boost::graph_traits<ring_graph>::in_edge_iterator in_edge_iterator;
+typedef boost::graph_traits<ring_graph>::adjacency_iterator adjacency_iterator;
+typedef boost::graph_traits<ring_graph>::degree_size_type degree_size_type;
+typedef boost::graph_traits<ring_graph>::vertex_iterator vertex_iterator;
+typedef boost::graph_traits<ring_graph>::vertices_size_type vertices_size_type;
+typedef boost::graph_traits<ring_graph>::edge_iterator edge_iterator;
+typedef boost::graph_traits<ring_graph>::edges_size_type edges_size_type;
+
+
+// Tag values passed to an iterator constructor to specify whether it should
+// be created at the start or the end of its range.
+struct iterator_position {};
+struct iterator_start:virtual public iterator_position {};
+struct iterator_end:virtual public iterator_position {};
+
+/*
+Iterator over edges incident on a vertex in a ring graph.
+
+For vertex i, this returns edge (i, i+1) and then edge (i, i-1), wrapping
+around the end of the ring as needed.
+
+Because this is an undirected graph, the edge <x,y> is equivalent to <y,x>.
+For clarity's sake, however, this iterator always returns an edge descriptor
+with the smaller vertex index first.
+
+It is implemented with the boost::iterator_adaptor class, adapting an
+offset into the dereference::ring_offset array.
+*/
+class ring_incident_edge_iterator:public boost::iterator_adaptor <
+    ring_incident_edge_iterator,
+    boost::counting_iterator<std::size_t>,
+    edge_descriptor,
+    boost::use_default,
+    edge_descriptor > {
+public:
+  ring_incident_edge_iterator():
+    ring_incident_edge_iterator::iterator_adaptor_(0),m_n(0),m_u(0) {};
+  explicit ring_incident_edge_iterator(const ring_graph& g,
+                                       vertex_descriptor u,
+                                       iterator_start):
+    ring_incident_edge_iterator::iterator_adaptor_(0),
+    m_n(g.n()),m_u(u) {};
+  explicit ring_incident_edge_iterator(const ring_graph& g,
+                                       vertex_descriptor u,
+                                       iterator_end):
+    // A graph with one vertex only has a single self-loop.  A graph with
+    // two vertices has a single edge between them.  All other graphs have
+    // two edges per vertex.
+    ring_incident_edge_iterator::iterator_adaptor_(g.n() > 2 ? 2:1),
+    m_n(g.n()),m_u(u) {};
+
+private:
+  friend class boost::iterator_core_access;
+
+  edge_descriptor dereference() const {
+    static const int ring_offset[] = {1, -1};
+    vertex_descriptor v;
+
+    std::size_t p = *this->base_reference();
+    if (m_u == 0 && p == 1)
+      v = m_n-1; // Vertex n-1 precedes vertex 0.
+    else
+      v = (m_u+ring_offset[p]) % m_n;
+    return edge_descriptor(m_u, v);
+  }
+
+  std::size_t m_n; // Size of the graph
+  vertex_descriptor m_u; // Vertex whose out edges are iterated
+};
+
+
+// IncidenceGraph valid expressions
+vertex_descriptor source(edge_descriptor e, const ring_graph&) {
+  // The first vertex in the edge pair is the source.
+  return e.first;
+}
+
+
+vertex_descriptor target(edge_descriptor e, const ring_graph&) {
+ // The second vertex in the edge pair is the target.
+ return e.second;
+}
+
+std::pair<out_edge_iterator, out_edge_iterator>
+out_edges(vertex_descriptor u, const ring_graph& g) {
+  return std::pair<out_edge_iterator, out_edge_iterator>(
+    out_edge_iterator(g, u, iterator_start()),
+    out_edge_iterator(g, u, iterator_end()) );
+}
+
+
+degree_size_type out_degree(vertex_descriptor, const ring_graph&) {
+  // All vertices in a ring graph have two neighbors.
+  return 2;
+}
+
+
+// BidirectionalGraph valid expressions
+std::pair<in_edge_iterator, in_edge_iterator>
+in_edges(vertex_descriptor u, const ring_graph& g) {
+  // The in-edges and out-edges are the same in an undirected graph.
+  return out_edges(u, g);
+}
+
+degree_size_type in_degree(vertex_descriptor u, const ring_graph& g) {
+  // The in-degree and out-degree are both equal to the number of incident
+  // edges in an undirected graph.
+  return out_degree(u, g);
+}
+
+degree_size_type degree(vertex_descriptor u, const ring_graph& g) {
+  // The in-degree and out-degree are both equal to the number of incident
+  // edges in an undirected graph.
+  return out_degree(u, g);
+}
+
+
+/*
+Iterator over vertices adjacent to a given vertex.
+
+This iterates over the target vertices of all the incident edges.
+*/
+class ring_adjacency_iterator:public boost::adjacency_iterator_generator<
+  ring_graph,
+  vertex_descriptor,
+  out_edge_iterator>::type {
+  // The parent class is an iterator_adpator that turns an iterator over
+  // out edges into an iterator over adjacent vertices.
+  typedef boost::adjacency_iterator_generator<
+    ring_graph,
+    vertex_descriptor,
+    out_edge_iterator>::type parent_class;
+public:
+  ring_adjacency_iterator() {};
+  ring_adjacency_iterator(vertex_descriptor u,
+                          const ring_graph& g,
+                          iterator_start):
+    parent_class(out_edge_iterator(g, u, iterator_start()), &g) {};
+  ring_adjacency_iterator(vertex_descriptor u,
+                          const ring_graph& g,
+                          iterator_end):
+    parent_class(out_edge_iterator(g, u, iterator_end()), &g) {};
+};
+
+
+// AdjacencyGraph valid expressions
+std::pair<adjacency_iterator, adjacency_iterator>
+adjacent_vertices(vertex_descriptor u, const ring_graph& g) {
+  return std::pair<adjacency_iterator, adjacency_iterator>(
+    adjacency_iterator(u, g, iterator_start()),
+    adjacency_iterator(u, g, iterator_end()));
+}
+
+
+// VertexListGraph valid expressions
+vertices_size_type num_vertices(const ring_graph& g) {
+  return g.n();
+};
+
+std::pair<vertex_iterator, vertex_iterator> vertices(const ring_graph& g) {
+  return std::pair<vertex_iterator, vertex_iterator>(
+    vertex_iterator(0),                 // The first iterator position
+    vertex_iterator(num_vertices(g)) ); // The last iterator position
+}
+
+
+/*
+Iterator over edges in a ring graph.
+
+This object iterates over all the vertices in the graph, then for each
+vertex returns its first outgoing edge.
+
+It is implemented with the boost::iterator_adaptor class, because it is
+essentially a vertex_iterator with a customized deference operation.
+*/
+class ring_edge_iterator:public boost::iterator_adaptor<
+  ring_edge_iterator,
+  vertex_iterator,
+  edge_descriptor,
+  boost::use_default,
+  edge_descriptor > {
+public:
+  ring_edge_iterator():
+    ring_edge_iterator::iterator_adaptor_(0),m_g(NULL) {};
+  explicit ring_edge_iterator(const ring_graph& g, iterator_start):
+    ring_edge_iterator::iterator_adaptor_(vertices(g).first),m_g(&g) {};
+  explicit ring_edge_iterator(const ring_graph& g, iterator_end):
+    ring_edge_iterator::iterator_adaptor_(
+      // Size 2 graphs have a single edge connecting the two vertices.
+      g.n() == 2 ? ++(vertices(g).first) : vertices(g).second ),
+    m_g(&g) {};
+
+private:
+  friend class boost::iterator_core_access;
+
+  edge_descriptor dereference() const {
+    // The first element in the incident edge list of the current vertex.
+    return *(out_edges(*this->base_reference(), *m_g).first);
+  }
+
+  // The graph being iterated over
+  const ring_graph *m_g;
+};
+
+// EdgeListGraph valid expressions
+std::pair<edge_iterator, edge_iterator> edges(const ring_graph& g) {
+  return std::pair<edge_iterator, edge_iterator>(
+    ring_edge_iterator(g, iterator_start()),
+    ring_edge_iterator(g, iterator_end()) );
+}
+
+edges_size_type num_edges(const ring_graph& g) {
+  // There are as many edges as there are vertices, except for size 2
+  // graphs, which have a single edge connecting the two vertices.
+  return g.n() == 2 ? 1:g.n();
+}
+
+
+// AdjacencyMatrix valid expressions
+std::pair<edge_descriptor, bool>
+edge(vertex_descriptor u, vertex_descriptor v, const ring_graph& g) {
+  if (abs(u-v) == 1 &&
+      u >= 0 && u < num_vertices(g) && v >= 0 && v < num_vertices(g))
+    return std::pair<edge_descriptor, bool>(edge_descriptor(u, v), true);
+  else
+    return std::pair<edge_descriptor, bool>(edge_descriptor(), false);
+}
+
+
+/*
+Map from edges to weight values
+*/
+struct edge_weight_map {
+  typedef double value_type;
+  typedef value_type reference;
+  typedef edge_descriptor key_type;
+  typedef boost::readable_property_map_tag category;
+
+  // Edges have a weight equal to the average of their endpoint indexes.
+  reference operator[](key_type e) const {
+    return (e.first + e.second)/2.0;
+  }
+};
+
+// Use these propety_map and property_traits parameterizations to refer to
+// the associated property map types.
+typedef boost::property_map<ring_graph,
+                            boost::edge_weight_t>::const_type
+        const_edge_weight_map;
+typedef boost::property_traits<const_edge_weight_map>::reference
+        edge_weight_map_value_type;
+typedef boost::property_traits<const_edge_weight_map>::key_type
+        edge_weight_map_key;
+
+// PropertyMap valid expressions
+edge_weight_map_value_type
+get(const_edge_weight_map pmap, edge_weight_map_key e) {
+  return pmap[e];
+}
+
+
+// ReadablePropertyGraph valid expressions
+const_edge_weight_map get(boost::edge_weight_t, const ring_graph&) {
+  return const_edge_weight_map();
+}
+
+edge_weight_map_value_type get(boost::edge_weight_t tag,
+                               const ring_graph& g,
+                               edge_weight_map_key e) {
+  return get(tag, g)[e];
+}
+
+
+// This expression is not part of a graph concept, but is used to return the
+// default vertex index map used by the Dijkstra search algorithm.
+boost::identity_property_map get(boost::vertex_index_t, const ring_graph&) {
+  // The vertex descriptors are already unsigned integer indices, so just
+  // return an identity map.
+  return boost::identity_property_map();
+}
+
+
+int main (int argc, char const *argv[]) {
+  using namespace boost;
+  // Check the concepts that graph models.  This is included to demonstrate
+  // how concept checking works, but is not required for a working program
+  // since Boost algorithms do their own concept checking.
+  function_requires< BidirectionalGraphConcept<ring_graph> >();
+  function_requires< AdjacencyGraphConcept<ring_graph> >();
+  function_requires< VertexListGraphConcept<ring_graph> >();
+  function_requires< EdgeListGraphConcept<ring_graph> >();
+  function_requires< AdjacencyMatrixConcept<ring_graph> >();
+  function_requires<
+    ReadablePropertyMapConcept<const_edge_weight_map, edge_descriptor> >();
+  function_requires<
+    ReadablePropertyGraphConcept<ring_graph, edge_descriptor, edge_weight_t> >();
+
+  // Specify the size of the graph on the command line, or use a default size
+  // of 5.
+  std::size_t n = argc == 2 ? boost::lexical_cast<std::size_t>(argv[1]) : 5;
+
+  // Create a small ring graph.
+  ring_graph g(n);
+  const_edge_weight_map m = get(edge_weight, g);
+
+  // Print the outgoing edges of all the vertices.  For n=5 this will print:
+  //
+  // Vertices, outgoing edges, and adjacent vertices
+  // Vertex 0: <0, 1>  <0, 4>   Adjacent vertices 1 4
+  // Vertex 1: <1, 2>  <1, 0>   Adjacent vertices 2 0
+  // Vertex 2: <2, 3>  <2, 1>   Adjacent vertices 3 1
+  // Vertex 3: <3, 4>  <3, 2>   Adjacent vertices 4 2
+  // Vertex 4: <4, 0>  <4, 3>   Adjacent vertices 0 3
+  // 5 vertices
+  std::cout << "Vertices, outgoing edges, and adjacent vertices" << std::endl;
+  vertex_iterator vi, vi_end;
+  for (tie(vi, vi_end) = vertices(g); vi != vi_end; vi++) {
+    vertex_descriptor u = *vi;
+    std::cout << "Vertex " << u << ": ";
+    // Adjacenct edges
+    out_edge_iterator ei, ei_end;
+    for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ei++) {
+      edge_descriptor e = *ei;
+      std::cout << "<" << e.first << ", " << e.second << ">" << "  ";
+    }
+    std::cout << " Adjacent vertices ";
+    // Adjacent vertices
+    // Here we want our adjacency_iterator and not boost::adjacency_iterator.
+    ::adjacency_iterator ai, ai_end;
+    for (tie(ai, ai_end) = adjacent_vertices(u, g); ai != ai_end; ai++) {
+      std::cout << *ai << " ";
+    }
+    std::cout << std::endl;
+  }
+  std::cout << num_vertices(g) << " vertices" << std::endl << std::endl;
+
+  // Print all the edges in the graph along with their weights.  For n=5 this
+  // will print:
+  //
+  // Edges and weights
+  // <0, 1> weight 0.5
+  // <1, 2> weight 1.5
+  // <2, 3> weight 2.5
+  // <3, 4> weight 3.5
+  // <4, 0> weight 2
+  // 5 edges
+  std::cout << "Edges and weights" << std::endl;
+  edge_iterator ei, ei_end;
+  for (tie(ei, ei_end) = edges(g); ei != ei_end; ei++) {
+    edge_descriptor e = *ei;
+    std::cout << "<" << e.first << ", " << e.second << ">"
+              << " weight " << get(edge_weight, g, e) << std::endl;
+  }
+  std::cout << num_edges(g) << " edges"  << std::endl;
+
+  if (n>0) {
+    std::cout << std::endl;
+    // Do a Dijkstra search from vertex 0.  For n=5 this will print:
+    //
+    // Dijkstra search from vertex 0
+    // Vertex 0: parent 0, distance 0
+    // Vertex 1: parent 0, distance 0.5
+    // Vertex 2: parent 1, distance 2
+    // Vertex 3: parent 2, distance 4.5
+    // Vertex 4: parent 0, distance 2
+    vertex_descriptor source = 0;
+    std::vector<vertex_descriptor> pred(num_vertices(g));
+    std::vector<edge_weight_map_value_type> dist(num_vertices(g));
+
+    dijkstra_shortest_paths(g, source,
+                            predecessor_map(&pred[0]).
+                            distance_map(&dist[0]) );
+
+    std::cout << "Dijkstra search from vertex " << source << std::endl;
+    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
+      vertex_descriptor u = *vi;
+      std::cout << "Vertex " << u << ": "
+                << "parent "<< pred[*vi] << ", "
+                << "distance " << dist[u]
+                << std::endl;
+    }
+  }
+
+  return 0;
+}