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