Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r55473 - in trunk: boost/graph libs/graph/doc libs/graph/doc/figs libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-08-08 14:58:10

Author: jewillco
Date: 2009-08-08 14:58:07 EDT (Sat, 08 Aug 2009)
New Revision: 55473
URL: http://svn.boost.org/trac/boost/changeset/55473

Log:
Added grid graph from Michael Hansen
Added:
   trunk/boost/graph/grid_graph.hpp (contents, props changed)
   trunk/libs/graph/doc/figs/grid_graph_indexed.png (contents, props changed)
   trunk/libs/graph/doc/figs/grid_graph_indexed.svg (contents, props changed)
   trunk/libs/graph/doc/figs/grid_graph_unindexed.svg (contents, props changed)
   trunk/libs/graph/doc/figs/grid_graph_unwrapped.png (contents, props changed)
   trunk/libs/graph/doc/figs/grid_graph_wrapped.png (contents, props changed)
   trunk/libs/graph/doc/grid_graph.html (contents, props changed)
   trunk/libs/graph/example/grid_graph_example.cpp (contents, props changed)
   trunk/libs/graph/test/grid_graph_cc.cpp (contents, props changed)
   trunk/libs/graph/test/grid_graph_test.cpp (contents, props changed)
Text files modified:
   trunk/libs/graph/doc/table_of_contents.html | 3 +++
   trunk/libs/graph/example/Jamfile.v2 | 1 +
   trunk/libs/graph/test/Jamfile.v2 | 2 ++
   3 files changed, 6 insertions(+), 0 deletions(-)

Added: trunk/boost/graph/grid_graph.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/grid_graph.hpp 2009-08-08 14:58:07 EDT (Sat, 08 Aug 2009)
@@ -0,0 +1,840 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen, Andrew Lumsdaine
+//
+// 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)
+//=======================================================================
+
+#ifndef BOOST_GRAPH_GRID_GRAPH_HPP
+#define BOOST_GRAPH_GRID_GRAPH_HPP
+
+#include <cmath>
+#include <functional>
+#include <numeric>
+
+#include <boost/array.hpp>
+#include <boost/bind.hpp>
+#include <boost/limits.hpp>
+#include <boost/make_shared.hpp>
+#include <boost/graph/adjacency_iterator.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/iterator/counting_iterator.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/property_map/property_map.hpp>
+
+#define BOOST_GRID_GRAPH_TEMPLATE_PARAMS \
+ std::size_t DimensionsT, typename VertexIndexT, \
+ typename EdgeIndexT
+
+#define BOOST_GRID_GRAPH_TYPE \
+ grid_graph<DimensionsT, VertexIndexT, EdgeIndexT>
+
+#define BOOST_GRID_GRAPH_TRAITS_T \
+ typename graph_traits<BOOST_GRID_GRAPH_TYPE>
+
+namespace boost {
+
+ // Class prototype for grid_graph
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ class grid_graph;
+
+ //===================
+ // Index Property Map
+ //===================
+
+ template <typename Graph,
+ typename Descriptor,
+ typename Index>
+ struct grid_graph_index_map {
+ public:
+ typedef Index value_type;
+ typedef Index reference_type;
+ typedef reference_type reference;
+ typedef Descriptor key_type;
+ typedef readable_property_map_tag category;
+
+ grid_graph_index_map() { }
+
+ grid_graph_index_map(const Graph& graph) :
+ m_graph(make_shared<Graph>(graph)) { }
+
+ value_type operator[](key_type key) const {
+ return (m_graph->index_of(key));
+ }
+
+ protected:
+ shared_ptr<Graph> m_graph;
+ };
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ struct property_map<BOOST_GRID_GRAPH_TYPE, vertex_index_t> {
+ typedef grid_graph_index_map<BOOST_GRID_GRAPH_TYPE,
+ BOOST_GRID_GRAPH_TRAITS_T::vertex_descriptor,
+ BOOST_GRID_GRAPH_TRAITS_T::vertices_size_type> type;
+ typedef type const_type;
+ };
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ struct property_map<BOOST_GRID_GRAPH_TYPE, edge_index_t> {
+ typedef grid_graph_index_map<BOOST_GRID_GRAPH_TYPE,
+ BOOST_GRID_GRAPH_TRAITS_T::edge_descriptor,
+ BOOST_GRID_GRAPH_TRAITS_T::edges_size_type> type;
+ typedef type const_type;
+ };
+
+ //===========
+ // Grid Graph
+ //===========
+
+ template <std::size_t Dimensions,
+ typename VertexIndex = std::size_t,
+ typename EdgeIndex = VertexIndex>
+ class grid_graph {
+
+ private:
+ typedef boost::array<bool, Dimensions> WrapDimensionArray;
+ grid_graph() { };
+
+ public:
+
+ typedef grid_graph<Dimensions, VertexIndex, EdgeIndex> type;
+
+ // sizes
+ typedef VertexIndex vertices_size_type;
+ typedef EdgeIndex edges_size_type;
+ typedef EdgeIndex degree_size_type;
+
+ // descriptors
+ typedef boost::array<VertexIndex, Dimensions> vertex_descriptor;
+ typedef std::pair<vertex_descriptor, vertex_descriptor> edge_descriptor;
+
+ // vertex_iterator
+ typedef counting_iterator<vertices_size_type> vertex_index_iterator;
+ typedef boost::function<vertex_descriptor (vertices_size_type)> vertex_function;
+ typedef transform_iterator<vertex_function, vertex_index_iterator> vertex_iterator;
+
+ // edge_iterator
+ typedef counting_iterator<edges_size_type> edge_index_iterator;
+ typedef boost::function<edge_descriptor (edges_size_type)> edge_function;
+ typedef transform_iterator<edge_function, edge_index_iterator> edge_iterator;
+
+ // out_edge_iterator
+ typedef counting_iterator<degree_size_type> degree_iterator;
+ typedef boost::function<edge_descriptor (degree_size_type)> degree_function;
+ typedef transform_iterator<degree_function, degree_iterator> out_edge_iterator;
+
+ // in_edge_iterator
+ typedef transform_iterator<degree_function, degree_iterator> in_edge_iterator;
+
+ // adjacency_iterator
+ typedef typename adjacency_iterator_generator<type,
+ vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
+
+ // categories
+ typedef undirected_tag directed_category;
+ typedef disallow_parallel_edge_tag edge_parallel_category;
+ struct traversal_category : virtual public incidence_graph_tag,
+ virtual public adjacency_graph_tag,
+ virtual public vertex_list_graph_tag,
+ virtual public edge_list_graph_tag,
+ virtual public bidirectional_graph_tag,
+ virtual public adjacency_matrix_tag { };
+
+ static inline vertex_descriptor null_vertex()
+ {
+ vertex_descriptor maxed_out_vertex;
+ std::fill(maxed_out_vertex.begin(), maxed_out_vertex.end(),
+ (std::numeric_limits<vertices_size_type>::max)());
+
+ return (maxed_out_vertex);
+ }
+
+ // Constructor that defaults to no wrapping for all dimensions.
+ grid_graph(vertex_descriptor dimension_lengths) :
+ m_dimension_lengths(dimension_lengths) {
+
+ std::fill(m_wrap_dimension.begin(),
+ m_wrap_dimension.end(), false);
+
+ precalculate();
+ }
+
+ // Constructor that allows for wrapping to be specified for all
+ // dimensions at once.
+ grid_graph(vertex_descriptor dimension_lengths,
+ bool wrap_all_dimensions) :
+ m_dimension_lengths(dimension_lengths) {
+
+ std::fill(m_wrap_dimension.begin(),
+ m_wrap_dimension.end(),
+ wrap_all_dimensions);
+
+ precalculate();
+ }
+
+ // Constructor that allows for individual dimension wrapping to be
+ // specified.
+ grid_graph(vertex_descriptor dimension_lengths,
+ WrapDimensionArray wrap_dimension) :
+ m_dimension_lengths(dimension_lengths),
+ m_wrap_dimension(wrap_dimension) {
+
+ precalculate();
+ }
+
+ // Returns the number of dimensions in the graph
+ inline std::size_t dimensions() const {
+ return (Dimensions);
+ }
+
+ // Returns the length of dimension [dimension_index]
+ inline vertices_size_type length(std::size_t dimension) const {
+ return (m_dimension_lengths[dimension]);
+ }
+
+ // Returns a value indicating if dimension [dimension_index] wraps
+ inline bool wrapped(std::size_t dimension) const {
+ return (m_wrap_dimension[dimension]);
+ }
+
+ // Gets the vertex that is [distance] units ahead of [vertex] in
+ // dimension [dimension_index].
+ vertex_descriptor next
+ (vertex_descriptor vertex,
+ std::size_t dimension_index,
+ vertices_size_type distance = 1) const {
+
+ vertices_size_type new_position =
+ vertex[dimension_index] + distance;
+
+ if (wrapped(dimension_index)) {
+ new_position %= length(dimension_index);
+ }
+ else {
+ // Stop at the end of this dimension if necessary.
+ new_position =
+ (std::min)(new_position,
+ length(dimension_index) - 1);
+ }
+
+ vertex[dimension_index] = new_position;
+
+ return (vertex);
+ }
+
+ // Gets the vertex that is [distance] units behind [vertex] in
+ // dimension [dimension_index].
+ vertex_descriptor previous
+ (vertex_descriptor vertex,
+ std::size_t dimension_index,
+ vertices_size_type distance = 1) const {
+
+ // We're assuming that vertices_size_type is unsigned, so we
+ // need to be careful about the math.
+ vertex[dimension_index] =
+ (distance > vertex[dimension_index]) ?
+ (wrapped(dimension_index) ?
+ (length(dimension_index) - (distance % length(dimension_index))) : 0) :
+ vertex[dimension_index] - distance;
+
+ return (vertex);
+ }
+
+ protected:
+
+ // Returns the number of vertices in the graph
+ inline vertices_size_type num_vertices() const {
+ return (m_num_vertices);
+ }
+
+ // Returns the number of edges in the graph
+ inline edges_size_type num_edges() const {
+ return (m_num_edges);
+ }
+
+ // Returns the number of edges in dimension [dimension_index]
+ inline edges_size_type num_edges
+ (std::size_t dimension_index) const {
+ return (m_edge_count[dimension_index]);
+ }
+
+ // Returns the index of [vertex] (See also vertex_at)
+ vertices_size_type index_of(vertex_descriptor vertex) const {
+
+ vertices_size_type vertex_index = 0;
+ vertices_size_type index_multiplier = 1;
+
+ for (std::size_t dimension_index = 0;
+ dimension_index < Dimensions;
+ ++dimension_index) {
+
+ vertex_index += (vertex[dimension_index] * index_multiplier);
+ index_multiplier *= length(dimension_index);
+ }
+
+ return (vertex_index);
+ }
+
+ // Returns the vertex whose index is [vertex_index] (See also
+ // index_of(vertex_descriptor))
+ vertex_descriptor vertex_at
+ (vertices_size_type vertex_index) const {
+
+ array<vertices_size_type, Dimensions> vertex;
+ vertices_size_type index_divider = 1;
+
+ for (std::size_t dimension_index = 0;
+ dimension_index < Dimensions;
+ ++dimension_index) {
+
+ vertex[dimension_index] = (vertex_index / index_divider) %
+ length(dimension_index);
+
+ index_divider *= length(dimension_index);
+ }
+
+ return (vertex);
+ }
+
+ // Returns the edge whose index is [edge_index] (See also
+ // index_of(edge_descriptor)). NOTE: The index mapping is
+ // dependent upon dimension wrapping.
+ edge_descriptor edge_at(edges_size_type edge_index) const {
+
+ // Edge indicies are sorted into bins by dimension
+ std::size_t dimension_index = 0;
+ edges_size_type dimension_edges = num_edges(0);
+
+ while (edge_index >= dimension_edges) {
+ edge_index -= dimension_edges;
+ ++dimension_index;
+ dimension_edges = num_edges(dimension_index);
+ }
+
+ vertex_descriptor vertex_source, vertex_target;
+ bool is_forward = ((edge_index / (num_edges(dimension_index) / 2)) == 0);
+
+ if (wrapped(dimension_index)) {
+ vertex_source = vertex_at(edge_index % num_vertices());
+ vertex_target = is_forward ?
+ next(vertex_source, dimension_index) :
+ previous(vertex_source, dimension_index);
+ }
+ else {
+
+ // Dimensions can wrap arbitrarily, so an index needs to be
+ // computed in a more complex manner. This is done by
+ // grouping the edges for each dimension together into "bins"
+ // and considering [edge_index] as an offset into the bin.
+ // Each bin consists of two parts: the "forward" looking edges
+ // and the "backward" looking edges for the dimension.
+
+ edges_size_type vertex_offset = edge_index % num_edges(dimension_index);
+
+ // Consider vertex_offset an index into the graph's vertex
+ // space but with the dimension [dimension_index] reduced in
+ // size by one.
+ vertices_size_type index_divider = 1;
+
+ for (std::size_t dimension_index_iter = 0;
+ dimension_index_iter < Dimensions;
+ ++dimension_index_iter) {
+
+ std::size_t dimension_length = (dimension_index_iter == dimension_index) ?
+ length(dimension_index_iter) - 1 :
+ length(dimension_index_iter);
+
+ vertex_source[dimension_index_iter] = (vertex_offset / index_divider) %
+ dimension_length;
+
+ index_divider *= dimension_length;
+ }
+
+ if (is_forward) {
+ vertex_target = next(vertex_source, dimension_index);
+ }
+ else {
+ // Shift forward one more unit in the dimension for backward
+ // edges since the algorithm above will leave us one behind.
+ vertex_target = vertex_source;
+ ++vertex_source[dimension_index];
+ }
+
+ } // if (wrapped(dimension_index))
+
+ return (std::make_pair(vertex_source, vertex_target));
+ }
+
+ // Returns the index for [edge] (See also edge_at)
+ edges_size_type index_of(edge_descriptor edge) const {
+ vertex_descriptor source_vertex = source(edge, *this);
+ vertex_descriptor target_vertex = target(edge, *this);
+
+ // Determine the dimension where the source and target vertices
+ // differ (should only be one if this is a valid edge).
+ std::size_t different_dimension_index = 0;
+
+ while (source_vertex[different_dimension_index] ==
+ target_vertex[different_dimension_index]) {
+
+ ++different_dimension_index;
+ }
+
+ edges_size_type edge_index = 0;
+
+ // Offset the edge index into the appropriate "bin" (see edge_at
+ // for a more in-depth description).
+ for (std::size_t dimension_index = 0;
+ dimension_index < different_dimension_index;
+ ++dimension_index) {
+
+ edge_index += num_edges(dimension_index);
+ }
+
+ // Get the position of both vertices in the differing dimension.
+ vertices_size_type source_position = source_vertex[different_dimension_index];
+ vertices_size_type target_position = target_vertex[different_dimension_index];
+
+ // Determine if edge is forward or backward
+ bool is_forward = true;
+
+ if (wrapped(different_dimension_index)) {
+
+ // If the dimension is wrapped, an edge is going backward if
+ // either A: its target precedes the source in the differing
+ // dimension and the vertices are adjacent or B: its source
+ // precedes the target and they're not adjacent.
+ if (((target_position < source_position) &&
+ ((source_position - target_position) == 1)) ||
+ ((source_position < target_position) &&
+ ((target_position - source_position) > 1))) {
+
+ is_forward = false;
+ }
+ }
+ else if (target_position < source_position) {
+ is_forward = false;
+ }
+
+ // "Backward" edges are in the second half of the bin.
+ if (!is_forward) {
+ edge_index += (num_edges(different_dimension_index) / 2);
+ }
+
+ // Finally, apply the vertex offset
+ if (wrapped(different_dimension_index)) {
+ edge_index += index_of(source_vertex);
+ }
+ else {
+ vertices_size_type index_multiplier = 1;
+
+ if (!is_forward) {
+ --source_vertex[different_dimension_index];
+ }
+
+ for (std::size_t dimension_index = 0;
+ dimension_index < Dimensions;
+ ++dimension_index) {
+
+ edge_index += (source_vertex[dimension_index] * index_multiplier);
+ index_multiplier *= (dimension_index == different_dimension_index) ?
+ length(dimension_index) - 1 :
+ length(dimension_index);
+ }
+ }
+
+ return (edge_index);
+ }
+
+ // Returns the number of out-edges for [vertex]
+ degree_size_type out_degree(vertex_descriptor vertex) const {
+
+ degree_size_type out_edge_count = 0;
+
+ for (std::size_t dimension_index = 0;
+ dimension_index < Dimensions;
+ ++dimension_index) {
+
+ // If the vertex is on the edge of this dimension, then its
+ // number of out edges is dependent upon whether the dimension
+ // wraps or not.
+ if ((vertex[dimension_index] == 0) ||
+ (vertex[dimension_index] == (length(dimension_index) - 1))) {
+ out_edge_count += (wrapped(dimension_index) ? 2 : 1);
+ }
+ else {
+ // Next and previous edges, regardless or wrapping
+ out_edge_count += 2;
+ }
+ }
+
+ return (out_edge_count);
+ }
+
+ // Returns an out-edge for [vertex] by index. Indicies are in the
+ // range [0, out_degree(vertex)).
+ edge_descriptor out_edge_at
+ (vertex_descriptor vertex,
+ degree_size_type out_edge_index) const {
+
+ edges_size_type edges_left = out_edge_index + 1;
+ std::size_t dimension_index = 0;
+ bool is_forward = false;
+
+ // Walks the out edges of [vertex] and accommodates for dimension
+ // wrapping.
+ while (edges_left > 0) {
+
+ if (!wrapped(dimension_index)) {
+ if (!is_forward && (vertex[dimension_index] == 0)) {
+ is_forward = true;
+ continue;
+ }
+ else if (is_forward &&
+ (vertex[dimension_index] == (length(dimension_index) - 1))) {
+ is_forward = false;
+ ++dimension_index;
+ continue;
+ }
+ }
+
+ --edges_left;
+
+ if (edges_left > 0) {
+ is_forward = !is_forward;
+
+ if (!is_forward) {
+ ++dimension_index;
+ }
+ }
+ }
+
+ return (std::make_pair(vertex, is_forward ?
+ next(vertex, dimension_index) :
+ previous(vertex, dimension_index)));
+ }
+
+ // Returns the number of in-edges for [vertex]
+ inline degree_size_type in_degree(vertex_descriptor vertex) const {
+ return (out_degree(vertex));
+ }
+
+ // Returns an in-edge for [vertex] by index. Indicies are in the
+ // range [0, in_degree(vertex)).
+ edge_descriptor in_edge_at
+ (vertex_descriptor vertex,
+ edges_size_type in_edge_index) const {
+
+ edge_descriptor out_edge = out_edge_at(vertex, in_edge_index);
+ return (std::make_pair(target(out_edge, *this), source(out_edge, *this)));
+
+ }
+
+ // Pre-computes the number of vertices and edges
+ void precalculate() {
+ m_num_vertices =
+ std::accumulate(m_dimension_lengths.begin(),
+ m_dimension_lengths.end(), 1,
+ std::multiplies<vertices_size_type>());
+
+ // Calculate number of edges in each dimension
+ m_num_edges = 0;
+
+ for (std::size_t dimension_index = 0;
+ dimension_index < Dimensions;
+ ++dimension_index) {
+
+ if (wrapped(dimension_index)) {
+ m_edge_count[dimension_index] = num_vertices() * 2;
+ }
+ else {
+ m_edge_count[dimension_index] =
+ (num_vertices() - (num_vertices() / length(dimension_index))) * 2;
+ }
+
+ m_num_edges += num_edges(dimension_index);
+ }
+ }
+
+ const vertex_descriptor m_dimension_lengths;
+ WrapDimensionArray m_wrap_dimension;
+ vertices_size_type m_num_vertices;
+
+ boost::array<edges_size_type, Dimensions> m_edge_count;
+ edges_size_type m_num_edges;
+
+ public:
+
+ //================
+ // VertexListGraph
+ //================
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline std::pair<vertex_iterator, vertex_iterator>
+ vertices(const BOOST_GRID_GRAPH_TYPE& graph) {
+
+ typedef boost::function<vertex_descriptor (vertices_size_type)>
+ vertex_function;
+
+ vertex_function transform_function =
+ boost::bind(&BOOST_GRID_GRAPH_TYPE::vertex_at, boost::cref(graph), _1);
+
+ return (std::make_pair
+ (vertex_iterator(vertex_index_iterator(0), transform_function),
+ vertex_iterator(vertex_index_iterator(graph.num_vertices()),
+ transform_function)));
+ }
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline vertices_size_type
+ num_vertices(const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (graph.num_vertices());
+ }
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline vertex_descriptor
+ vertex(vertices_size_type vertex_index,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
+
+ return (graph.vertex_at(vertex_index));
+ }
+
+ //===============
+ // IncidenceGraph
+ //===============
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline std::pair<out_edge_iterator, out_edge_iterator>
+ out_edges(vertex_descriptor vertex,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
+
+ typedef boost::function<edge_descriptor (degree_size_type)>
+ out_edge_at_function;
+
+ out_edge_at_function transform_function =
+ boost::bind(&BOOST_GRID_GRAPH_TYPE::out_edge_at,
+ boost::cref(graph), vertex, _1);
+
+ return (std::make_pair
+ (out_edge_iterator(degree_iterator(0), transform_function),
+ out_edge_iterator(degree_iterator(graph.out_degree(vertex)),
+ transform_function)));
+ }
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline degree_size_type out_degree
+ (vertex_descriptor vertex, const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (graph.out_degree(vertex));
+ }
+
+ //===============
+ // AdjacencyGraph
+ //===============
+
+ template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend typename std::pair<adjacency_iterator, adjacency_iterator>
+ adjacent_vertices (vertex_descriptor vertex,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
+
+ out_edge_iterator out_edge_start, out_edge_end;
+ tie(out_edge_start, out_edge_end) = out_edges(vertex, graph);
+
+ return (std::make_pair
+ (adjacency_iterator(out_edge_start, &graph),
+ adjacency_iterator(out_edge_end, &graph)));
+ }
+
+ //==============
+ // EdgeListGraph
+ //==============
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline edges_size_type
+ num_edges(const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (graph.num_edges());
+ }
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline edge_descriptor
+ edge_at(edges_size_type edge_index,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (graph.edge_at(edge_index));
+ }
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline std::pair<edge_iterator, edge_iterator>
+ edges(const BOOST_GRID_GRAPH_TYPE& graph) {
+
+ typedef boost::function<edge_descriptor (edges_size_type)>
+ edge_at_function;
+
+ edge_at_function transform_function =
+ boost::bind(&BOOST_GRID_GRAPH_TYPE::edge_at, boost::cref(graph), _1);
+
+ return (std::make_pair
+ (edge_iterator(edge_index_iterator(0), transform_function),
+ edge_iterator(edge_index_iterator(graph.num_edges()),
+ transform_function)));
+ }
+
+ //===================
+ // BiDirectionalGraph
+ //===================
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline std::pair<in_edge_iterator, in_edge_iterator>
+ in_edges(vertex_descriptor vertex,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
+
+ typedef boost::function<edge_descriptor (degree_size_type)>
+ in_edge_at_function;
+
+ in_edge_at_function transform_function =
+ boost::bind(&BOOST_GRID_GRAPH_TYPE::in_edge_at,
+ boost::cref(graph), vertex, _1);
+
+ return (std::make_pair
+ (in_edge_iterator(degree_iterator(0), transform_function),
+ in_edge_iterator(degree_iterator(graph.in_degree(vertex)),
+ transform_function)));
+ }
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline degree_size_type
+ in_degree (vertex_descriptor vertex,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (graph.in_degree(vertex));
+ }
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline degree_size_type
+ degree (vertex_descriptor vertex,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (graph.out_degree(vertex) * 2);
+ }
+
+ //==================
+ // Adjacency Matrix
+ //==================
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend std::pair<edge_descriptor, bool>
+ edge (vertex_descriptor source_vertex,
+ vertex_descriptor destination_vertex,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
+
+ std::pair<edge_descriptor, bool> edge_exists =
+ std::make_pair(std::make_pair(source_vertex, destination_vertex), false);
+
+ for (std::size_t dimension_index = 0;
+ dimension_index < Dimensions;
+ ++dimension_index) {
+
+ vertices_size_type dim_difference = 0;
+ vertices_size_type source_dim = source_vertex[dimension_index],
+ dest_dim = destination_vertex[dimension_index];
+
+ dim_difference = (source_dim > dest_dim) ?
+ (source_dim - dest_dim) : (dest_dim - source_dim);
+
+ if (dim_difference > 0) {
+
+ // If we've already found a valid edge, this would mean that
+ // the vertices are really diagonal across dimensions and
+ // therefore not connected.
+ if (edge_exists.second) {
+ edge_exists.second = false;
+ break;
+ }
+
+ // If the difference is one, the vertices are right next to
+ // each other and the edge is valid. The edge is still
+ // valid, though, if the dimension wraps and the vertices
+ // are on opposite ends.
+ if ((dim_difference == 1) ||
+ (graph.wrapped(dimension_index) &&
+ (((source_dim == 0) && (dest_dim == (graph.length(dimension_index) - 1))) ||
+ ((dest_dim == 0) && (source_dim == (graph.length(dimension_index) - 1)))))) {
+
+ edge_exists.second = true;
+ // Stay in the loop to check for diagonal vertices.
+ }
+ else {
+
+ // Stop checking - the vertices are too far apart.
+ edge_exists.second = false;
+ break;
+ }
+ }
+
+ } // for dimension_index
+
+ return (edge_exists);
+ }
+
+
+ //=============================
+ // Index Property Map Functions
+ //=============================
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline vertices_size_type
+ get(vertex_index_t,
+ const BOOST_GRID_GRAPH_TYPE& graph,
+ vertex_descriptor vertex) {
+ return (graph.index_of(vertex));
+ }
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline edges_size_type
+ get(edge_index_t,
+ const BOOST_GRID_GRAPH_TYPE& graph,
+ edge_descriptor edge) {
+ return (graph.index_of(edge));
+ }
+
+ template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline grid_graph_index_map<BOOST_GRID_GRAPH_TYPE,
+ vertex_descriptor,
+ vertices_size_type>
+ get(vertex_index_t, const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (grid_graph_index_map<BOOST_GRID_GRAPH_TYPE,
+ vertex_descriptor, vertices_size_type>(graph));
+ }
+
+ template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline grid_graph_index_map<BOOST_GRID_GRAPH_TYPE,
+ edge_descriptor,
+ edges_size_type>
+ get(edge_index_t, const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (grid_graph_index_map<BOOST_GRID_GRAPH_TYPE,
+ edge_descriptor, edges_size_type>(graph));
+ }
+
+ template<typename Graph,
+ typename Descriptor,
+ typename Index>
+ friend inline Index
+ get(const grid_graph_index_map<Graph, Descriptor, Index>& index_map,
+ const typename grid_graph_index_map<Graph, Descriptor, Index>::key_type& key)
+ {
+ return (index_map[key]);
+ }
+
+ template<typename Graph,
+ typename Descriptor,
+ typename Index>
+ friend struct grid_graph_index_map;
+
+ }; // grid_graph
+
+} // namespace boost
+
+#undef BOOST_GRID_GRAPH_TYPE
+#undef BOOST_GRID_GRAPH_TEMPLATE_PARAMS
+#undef BOOST_GRID_GRAPH_TRAITS_T
+
+#endif // BOOST_GRAPH_GRID_GRAPH_HPP

Added: trunk/libs/graph/doc/figs/grid_graph_indexed.png
==============================================================================
Binary file. No diff available.

Added: trunk/libs/graph/doc/figs/grid_graph_indexed.svg
==============================================================================
Binary file. No diff available.

Added: trunk/libs/graph/doc/figs/grid_graph_unindexed.svg
==============================================================================
Binary file. No diff available.

Added: trunk/libs/graph/doc/figs/grid_graph_unwrapped.png
==============================================================================
Binary file. No diff available.

Added: trunk/libs/graph/doc/figs/grid_graph_wrapped.png
==============================================================================
Binary file. No diff available.

Added: trunk/libs/graph/doc/grid_graph.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/grid_graph.html 2009-08-08 14:58:07 EDT (Sat, 08 Aug 2009)
@@ -0,0 +1,293 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
+
+<html>
+ <head>
+ <title>Boost Graph Library: Grid Graph</title>
+ <style type="text/css">
+ 
+ </style>
+ </head>
+ <body>
+ <img src="../../../boost.png" alt="C++ Boost" width="277" height="86" />
+ 
+ <h1>
+ <tt>grid_graph</tt>
+ </h1>
+
+ <ul>
+ <li>Overview</li>
+ <li>Creating a Grid Graph</li>
+ <li>Indexing</li>
+ <li>Grid Graph Member Functions</li>
+ </ul>
+
+ <h3 id="overview">Overview</h3>
+ 
+ A <tt>grid_graph</tt> represents a multi-dimensional,
+ rectangular grid of vertices with user-defined dimension lengths
+ and wrapping.
+
+ 
+ 
+ <tt>grid_graph</tt> models:
+ <ul>
+ <li>Incidence Graph</li>
+ <li>Adjacency Graph</li>
+ <li>Vertex List Graph</li>
+ <li>Edge List Graph</li>
+ <li>Bidirectional Graph</li>
+ <li>Adjacency Matrix</li>
+ </ul>
+ 
+ 
+ Defined in
+ boost/graph/grid_graph.hpp
+ with all functions in the <tt>boost</tt> namespace. All examples are available in a single program file in libs/graph/example/grid_graph_example.cpp
+ 
+
+ <h4>Template Parameters</h4>
+ <pre class="code">
+template <typename std::size_t Dimensions,
+ typename VertexIndex = std::size_t,
+ typename EdgeIndex = VertexIndex>
+ class grid_graph;
+ </pre>
+ <ul>
+ <li>
+ <tt>Dimensions</tt> - Number of dimensions in the graph, must be greater than 2
+ </li>
+ <li>
+ <tt>VertexIndex</tt> - Type used for vertex indices, defaults to std::size_t
+ </li>
+ <li>
+ <tt>EdgeIndex</tt> - Type used for edge indices, defaults to the same type as VertexIndex
+ </li>
+ </ul>
+
+ <h3 id="creating">Creating a Grid Graph</h3>
+ 
+ The constructor to <tt>grid_graph</tt> has several overloads to aid in configuring each dimension:
+ 
+ <pre class="code">
+// Defines a grid_graph that does not wrap.
+grid_graph<...>(boost:array<VertexIndex, Dimensions> dimension_lengths);
+
+// Defines a grid_graph where all dimensions are either wrapped or unwrapped.
+grid_graph<...>(boost:array<VertexIndex, Dimensions> dimension_lengths,
+ bool wrap_all_dimensions);
+
+// Defines a grid_graph where the wrapping for each dimension is specified individually.
+grid_graph<...>(boost:array<VertexIndex, Dimensions> dimension_lengths,
+ boost:array<bool, Dimensions> wrap_dimension);
+ </pre>
+
+ <h4>Example</h4>
+ <pre class="code">
+// Define dimension lengths, a 3x3 in this case
+boost::array<int, 2> lengths = { { 3, 3 } };
+
+// Create a 3x3 two-dimensional, unwrapped grid graph (Figure 1)
+grid_graph<2> graph(lengths);
+
+// Create a 3x3 two-dimensional, wrapped grid graph (Figure 2)
+grid_graph<2> graph(lengths, true);
+
+ </pre>
+ 
+ <img src="figs/grid_graph_unwrapped.png" />
+ 
+ Figure 1: A 3x3 two-dimensional, unwrapped grid graph
+ 
+ 
+ 
+ <img src="figs/grid_graph_wrapped.png" />
+ 
+ Figure 2: A 3x3 two-dimensional, wrapped grid graph
+ 
+ 
+
+ <h3 id="indexing">Indexing</h3>
+ 
+ The <tt>grid_graph</tt> supports addressing vertices and edges
+ by index. The following functions allow you to convert between
+ vertices, edges, and their associated indices:
+ 
+
+ <pre class="code">
+typedef grid_graph<...> Graph;
+typedef graph_traits<Graph> Traits;
+
+// Get the vertex associated with vertex_index
+Traits::vertex_descriptor
+vertex(Traits::vertices_size_type vertex_index,
+ const Graph& graph);
+
+// Get the index associated with vertex
+Traits::vertices_size_type
+get(boost::vertex_index_t,
+ Traits::vertex_descriptor vertex,
+ const Graph& graph);
+
+// Get the edge associated with edge_index
+Traits::edge_descriptor
+edge_at(Traits::edges_size_type edge_index,
+ const Graph& graph);
+
+// Get the index associated with edge
+Traits::edges_size_type
+get(boost::edge_index_t,
+ Traits::edge_descriptor edge,
+ const Graph& graph);
+
+ </pre>
+
+ <h4>Example</h4>
+ <pre class="code">
+typedef grid_graph<2> Graph;
+typedef graph_traits<Graph> Traits;
+
+// Create a 3x3, unwrapped grid_graph (Figure 3)
+boost::array<int, 2> lengths = { { 3, 3 } };
+Graph graph(lengths);
+
+// Do a round-trip test of the vertex index functions
+for (Traits::vertices_size_type v_index = 0;
+ v_index < num_vertices(graph); ++v_index) {
+
+ // The two indices should always be equal
+ std::cout << "Index of vertex " << v_index << " is " <<
+ get(boost::vertex_index, graph, vertex(v_index, graph)) << std::endl;
+
+}
+
+// Do a round-trip test of the edge index functions
+for (Traits::edges_size_type e_index = 0;
+ e_index < num_edges(graph); ++e_index) {
+
+ // The two indices should always be equal
+ std::cout << "Index of edge " << e_index << " is " <<
+ get(boost::edge_index, graph, edge_at(e_index, graph)) << std::endl;
+
+}
+ </pre>
+
+ 
+ <img src="figs/grid_graph_indexed.png" />
+ 
+ Figure 3: 3x3 unwrapped grid_graph with vertex and edge indices shown.
+ 
+ 
+
+ <h3 id="member">Member Functions</h3>
+ 
+ There are several <tt>grid_graph</tt> specific member functions available:
+ 
+ <pre class="code">
+typedef grid_graph<...> Graph;
+typedef graph_traits<Graph> Traits;
+
+// Returns the number of dimensions
+std::size_t dimensions();
+
+// Returns the length of a dimension
+Traits::vertices_size_type length(std::size_t dimension);
+
+// Returns true if the dimension wraps, false if not
+bool wrapped(std::size_t dimension);
+
+// Returns the "next" vertex in a dimension at a given distance. If the dimension
+// is unwrapped, next will stop at the last vertex in the dimension.
+Traits::vertex_descriptor next(Traits::vertex_descriptor vertex,
+ std::size_t dimension,
+ Traits::vertices_size_type distance = 1);
+
+// Returns the "previous" vertex in a dimension at a given distance. If the
+// dimension is unwrapped, previous will stop at the beginning vertex in the dimension.
+Traits::vertex_descriptor previous(Traits::vertex_descriptor vertex,
+ std::size_t dimension,
+ Traits::vertices_size_type distance = 1);
+ </pre>
+
+ <h4>Example</h4>
+ <pre class="code">
+typedef grid_graph<3> Graph;
+typedef graph_traits<Graph> Traits;
+
+// Define a 3x5x7 grid_graph where the second dimension doesn't wrap
+boost::array<std::size_t, 3> lengths = { { 3, 5, 7 } };
+boost::array<bool, 3> wrapped = { { true, false, true } };
+Graph graph(lengths, wrapped);
+
+// Print number of dimensions
+std::cout << graph.dimensions() << std::endl; // prints "3"
+
+// Print dimension lengths (same order as in the lengths array)
+std::cout << graph.length(0) << "x" << graph.length(1) <<
+ "x" << graph.length(2) << std::endl; // prints "3x5x7"
+
+// Print dimension wrapping (W = wrapped, U = unwrapped)
+std::cout << graph.wrapped(0) ? "W" : "U" << ", " <<
+ graph.wrapped(1) ? "W" : "U" << ", " <<
+ graph.wrapped(2) ? "W" : "U" << std::endl; // prints "W, U, W"
+
+// Define a simple function to print vertices
+void print_vertex(Traits::vertex_descriptor vertex_to_print) {
+ std::cout << "(" << vertex_to_print[0] << ", " << vertex_to_print[1] <<
+ ", " << vertex_to_print[2] << ")" << std::endl;
+}
+
+// Start with the first vertex in the graph
+Traits::vertex_descriptor first_vertex = vertex(0, graph);
+print_vertex(first_vertex); // prints "(0, 0, 0)"
+
+// Print the next vertex in dimension 0
+print_vertex(graph.next(first_vertex, 0)); // prints "(1, 0, 0)"
+
+// Print the next vertex in dimension 1
+print_vertex(graph.next(first_vertex, 1)); // prints "(0, 1, 0)"
+
+// Print the 5th next vertex in dimension 2
+print_vertex(graph.next(first_vertex, 2, 5)); // prints "(0, 0, 5)"
+
+// Print the previous vertex in dimension 0 (wraps)
+print_vertex(graph.previous(first_vertex, 0)); // prints "(2, 0, 0)"
+
+// Print the previous vertex in dimension 1 (doesn't wrap, so it's the same)
+print_vertex(graph.previous(first_vertex, 1)); // prints "(0, 0, 0)"
+
+// Print the 20th previous vertex in dimension 2 (wraps around twice)
+print_vertex(graph.previous(first_vertex, 2, 20)); // prints "(0, 0, 1)"
+ </pre>
+
+ <hr />
+ Copyright © 2009 Trustees of Indiana University
+
+ </body>
+</html>

Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html (original)
+++ trunk/libs/graph/doc/table_of_contents.html 2009-08-08 14:58:07 EDT (Sat, 08 Aug 2009)
@@ -110,6 +110,9 @@
 <LI>Matrix as Graph<a href="#*">*</a>
 <LI>Leda Graph <a href="#*">*</a>
 <LI>Stanford GraphBase
+ <LI>Implicit Graphs
+ <OL>
+ <LI>Multi-dimensional grid graph
 </OL>
 <LI>Iterator Adaptors
 <OL>

Modified: trunk/libs/graph/example/Jamfile.v2
==============================================================================
--- trunk/libs/graph/example/Jamfile.v2 (original)
+++ trunk/libs/graph/example/Jamfile.v2 2009-08-08 14:58:07 EDT (Sat, 08 Aug 2009)
@@ -19,3 +19,4 @@
exe bron_kerbosch_print_cliques : bron_kerbosch_print_cliques.cpp ;
exe bron_kerbosch_clique_number : bron_kerbosch_clique_number.cpp ;
exe mcgregor_subgraphs_example : mcgregor_subgraphs_example.cpp ;
+exe grid_graph_example : grid_graph_example.cpp ;

Added: trunk/libs/graph/example/grid_graph_example.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/grid_graph_example.cpp 2009-08-08 14:58:07 EDT (Sat, 08 Aug 2009)
@@ -0,0 +1,86 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen, Andrew Lumsdaine
+//
+// 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 <iostream>
+#include <boost/array.hpp>
+#include <boost/graph/grid_graph.hpp>
+
+#define DIMENSIONS 3
+using namespace boost;
+
+typedef grid_graph<DIMENSIONS> Graph;
+typedef graph_traits<Graph> Traits;
+
+// Define a simple function to print vertices
+void print_vertex(Traits::vertex_descriptor vertex_to_print) {
+ std::cout << "(" << vertex_to_print[0] << ", " << vertex_to_print[1] <<
+ ", " << vertex_to_print[2] << ")" << std::endl;
+}
+
+int main(int argc, char* argv[]) {
+
+ // Define a 3x5x7 grid_graph where the second dimension doesn't wrap
+ boost::array<std::size_t, 3> lengths = { { 3, 5, 7 } };
+ boost::array<bool, 3> wrapped = { { true, false, true } };
+ Graph graph(lengths, wrapped);
+
+ // Do a round-trip test of the vertex index functions
+ for (Traits::vertices_size_type v_index = 0;
+ v_index < num_vertices(graph); ++v_index) {
+
+ // The two indicies should always be equal
+ std::cout << "Index of vertex " << v_index << " is " <<
+ get(boost::vertex_index, graph, vertex(v_index, graph)) << std::endl;
+
+ }
+
+ // Do a round-trip test of the edge index functions
+ for (Traits::edges_size_type e_index = 0;
+ e_index < num_edges(graph); ++e_index) {
+
+ // The two indicies should always be equal
+ std::cout << "Index of edge " << e_index << " is " <<
+ get(boost::edge_index, graph, edge_at(e_index, graph)) << std::endl;
+
+ }
+
+ // Print number of dimensions
+ std::cout << graph.dimensions() << std::endl; // prints "3"
+
+ // Print dimension lengths (same order as in the lengths array)
+ std::cout << graph.length(0) << "x" << graph.length(1) <<
+ "x" << graph.length(2) << std::endl; // prints "3x5x7"
+
+ // Print dimension wrapping (W = wrapped, U = unwrapped)
+ std::cout << (graph.wrapped(0) ? "W" : "U") << ", " <<
+ (graph.wrapped(1) ? "W" : "U") << ", " <<
+ (graph.wrapped(2) ? "W" : "U") << std::endl; // prints "W, U, W"
+
+ // Start with the first vertex in the graph
+ Traits::vertex_descriptor first_vertex = vertex(0, graph);
+ print_vertex(first_vertex); // prints "(0, 0, 0)"
+
+ // Print the next vertex in dimension 0
+ print_vertex(graph.next(first_vertex, 0)); // prints "(1, 0, 0)"
+
+ // Print the next vertex in dimension 1
+ print_vertex(graph.next(first_vertex, 1)); // prints "(0, 1, 0)"
+
+ // Print the 5th next vertex in dimension 2
+ print_vertex(graph.next(first_vertex, 2, 5)); // prints "(0, 0, 4)"
+
+ // Print the previous vertex in dimension 0 (wraps)
+ print_vertex(graph.previous(first_vertex, 0)); // prints "(2, 0, 0)"
+
+ // Print the previous vertex in dimension 1 (doesn't wrap, so it's the same)
+ print_vertex(graph.previous(first_vertex, 1)); // prints "(0, 0, 0)"
+
+ // Print the 20th previous vertex in dimension 2 (wraps around twice)
+ print_vertex(graph.previous(first_vertex, 2, 20)); // prints "(0, 0, ?)"
+}

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2009-08-08 14:58:07 EDT (Sat, 08 Aug 2009)
@@ -119,6 +119,8 @@
     [ run core_numbers_test.cpp ]
     [ run read_propmap.cpp ]
     [ run mcgregor_subgraphs_test.cpp ]
+ [ compile grid_graph_cc.cpp ]
+ [ run grid_graph_test.cpp ]

     $(optional_tests)
     ;

Added: trunk/libs/graph/test/grid_graph_cc.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/grid_graph_cc.cpp 2009-08-08 14:58:07 EDT (Sat, 08 Aug 2009)
@@ -0,0 +1,33 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen, Andrew Lumsdaine
+//
+// 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/graph_archetypes.hpp>
+#include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/grid_graph.hpp>
+
+#define DIMENSIONS 3
+using namespace boost;
+
+int main (int argc, char* argv[]) {
+
+ typedef grid_graph<DIMENSIONS> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef graph_traits<Graph>::edge_descriptor Edge;
+
+ function_requires<BidirectionalGraphConcept<Graph> >();
+ function_requires<VertexListGraphConcept<Graph> >();
+ function_requires<EdgeListGraphConcept<Graph> >();
+ function_requires<IncidenceGraphConcept<Graph> >();
+ function_requires<AdjacencyGraphConcept<Graph> >();
+ function_requires<AdjacencyMatrixConcept<Graph> >();
+ function_requires<ReadablePropertyGraphConcept<Graph, Vertex, vertex_index_t> >();
+ function_requires<ReadablePropertyGraphConcept<Graph, Edge, edge_index_t> >();
+
+ return (0);
+};

Added: trunk/libs/graph/test/grid_graph_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/grid_graph_test.cpp 2009-08-08 14:58:07 EDT (Sat, 08 Aug 2009)
@@ -0,0 +1,211 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen, Andrew Lumsdaine
+//
+// 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 <fstream>
+#include <iostream>
+#include <set>
+
+#include <boost/foreach.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/graph/grid_graph.hpp>
+#include <boost/random.hpp>
+#include <boost/test/minimal.hpp>
+
+#define DIMENSIONS 3
+
+using namespace boost;
+
+// Function that prints a vertex to std::cout
+template <typename Vertex>
+void print_vertex(Vertex vertex_to_print) {
+
+ std::cout << "(";
+
+ for (std::size_t dimension_index = 0;
+ dimension_index < DIMENSIONS;
+ ++dimension_index) {
+ std::cout << vertex_to_print[dimension_index];
+
+ if (dimension_index != (DIMENSIONS - 1)) {
+ std::cout << ", ";
+ }
+ }
+
+ std::cout << ")";
+}
+
+int test_main(int argc, char* argv[]) {
+
+ std::size_t random_seed = time(0);
+
+ if (argc > 1) {
+ random_seed = lexical_cast<std::size_t>(argv[1]);
+ }
+
+ minstd_rand generator(random_seed);
+
+ typedef grid_graph<DIMENSIONS> Graph;
+ typedef graph_traits<Graph>::vertices_size_type vertices_size_type;
+ typedef graph_traits<Graph>::edges_size_type edges_size_type;
+
+ typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+ typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
+
+ std::cout << "Dimensions: " << DIMENSIONS << ", lengths: ";
+
+ // Randomly generate the dimension lengths (3-10) and wrapping
+ array<Graph::vertices_size_type, DIMENSIONS> lengths;
+ array<bool, DIMENSIONS> wrapped;
+
+ for (int dimension_index = 0;
+ dimension_index < DIMENSIONS;
+ ++dimension_index) {
+ lengths[dimension_index] = 3 + (generator() % 8);
+ wrapped[dimension_index] = ((generator() % 2) == 0);
+
+ std::cout << lengths[dimension_index] <<
+ (wrapped[dimension_index] ? " [W]" : " [U]") << ", ";
+ }
+
+ std::cout << std::endl;
+
+ Graph graph(lengths, wrapped);
+
+ // Verify dimension lengths and wrapping
+ for (int dimension_index = 0;
+ dimension_index < DIMENSIONS;
+ ++dimension_index) {
+ BOOST_REQUIRE(graph.length(dimension_index) == lengths[dimension_index]);
+ BOOST_REQUIRE(graph.wrapped(dimension_index) == wrapped[dimension_index]);
+ }
+
+ // Verify matching indicies
+ for (vertices_size_type vertex_index = 0;
+ vertex_index < num_vertices(graph);
+ ++vertex_index) {
+ BOOST_REQUIRE(get(boost::vertex_index, graph, vertex(vertex_index, graph)) == vertex_index);
+ }
+
+ for (edges_size_type edge_index = 0;
+ edge_index < num_edges(graph);
+ ++edge_index) {
+
+ edge_descriptor current_edge = edge_at(edge_index, graph);
+ BOOST_REQUIRE(get(boost::edge_index, graph, current_edge) == edge_index);
+ }
+
+ // Verify all vertices are within bounds
+ vertices_size_type vertex_count = 0;
+ BOOST_FOREACH(vertex_descriptor current_vertex, vertices(graph)) {
+
+ vertices_size_type current_index =
+ get(boost::vertex_index, graph, current_vertex);
+
+ for (int dimension_index = 0;
+ dimension_index < DIMENSIONS;
+ ++dimension_index) {
+ BOOST_REQUIRE((current_vertex[dimension_index] >= 0) &&
+ (current_vertex[dimension_index] < lengths[dimension_index]));
+ }
+
+ // Verify out-edges of this vertex
+ edges_size_type out_edge_count = 0;
+ std::set<vertices_size_type> target_vertices;
+
+ BOOST_FOREACH(edge_descriptor out_edge,
+ out_edges(current_vertex, graph)) {
+
+ target_vertices.insert
+ (get(boost::vertex_index, graph, target(out_edge, graph)));
+
+ ++out_edge_count;
+ }
+
+ BOOST_REQUIRE(out_edge_count == out_degree(current_vertex, graph));
+
+ // Verify in-edges of this vertex
+ edges_size_type in_edge_count = 0;
+
+ BOOST_FOREACH(edge_descriptor in_edge,
+ in_edges(current_vertex, graph)) {
+
+ BOOST_REQUIRE(target_vertices.count
+ (get(boost::vertex_index, graph, source(in_edge, graph))) > 0);
+
+ ++in_edge_count;
+ }
+
+ BOOST_REQUIRE(in_edge_count == in_degree(current_vertex, graph));
+
+ // The number of out-edges and in-edges should be the same
+ BOOST_REQUIRE(degree(current_vertex, graph) ==
+ out_degree(current_vertex, graph) +
+ in_degree(current_vertex, graph));
+
+ // Verify adjacent vertices to this vertex
+ vertices_size_type adjacent_count = 0;
+
+ BOOST_FOREACH(vertex_descriptor adjacent_vertex,
+ adjacent_vertices(current_vertex, graph)) {
+
+ BOOST_REQUIRE(target_vertices.count
+ (get(boost::vertex_index, graph, adjacent_vertex)) > 0);
+
+ ++adjacent_count;
+ }
+
+ BOOST_REQUIRE(adjacent_count == out_degree(current_vertex, graph));
+
+ // Verify that this vertex is not listed as connected to any
+ // vertices outside of its adjacent vertices.
+ BOOST_FOREACH(vertex_descriptor unconnected_vertex, vertices(graph)) {
+
+ vertices_size_type unconnected_index =
+ get(boost::vertex_index, graph, unconnected_vertex);
+
+ if ((unconnected_index == current_index) ||
+ (target_vertices.count(unconnected_index) > 0)) {
+ continue;
+ }
+
+ BOOST_REQUIRE(!edge(current_vertex, unconnected_vertex, graph).second);
+ BOOST_REQUIRE(!edge(unconnected_vertex, current_vertex, graph).second);
+ }
+
+ ++vertex_count;
+ }
+
+ BOOST_REQUIRE(vertex_count == num_vertices(graph));
+
+ // Verify all edges are within bounds
+ edges_size_type edge_count = 0;
+ BOOST_FOREACH(edge_descriptor current_edge, edges(graph)) {
+
+ vertices_size_type source_index =
+ get(boost::vertex_index, graph, source(current_edge, graph));
+
+ vertices_size_type target_index =
+ get(boost::vertex_index, graph, target(current_edge, graph));
+
+ BOOST_REQUIRE(source_index != target_index);
+ BOOST_REQUIRE((source_index >= 0) && (source_index < num_vertices(graph)));
+ BOOST_REQUIRE((target_index >= 0) && (target_index < num_vertices(graph)));
+
+ // Verify that the edge is listed as existing in both directions
+ BOOST_REQUIRE(edge(source(current_edge, graph), target(current_edge, graph), graph).second);
+ BOOST_REQUIRE(edge(target(current_edge, graph), source(current_edge, graph), graph).second);
+
+ ++edge_count;
+ }
+
+ BOOST_REQUIRE(edge_count == num_edges(graph));
+
+ return (0);
+}
+

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk