comparison DEPENDENCIES/generic/include/boost/graph/grid_graph.hpp @ 16:2665513ce2d3

Add boost headers

+//=======================================================================
+// 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/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(&graph) { }
+
+    value_type operator[](key_type key) const {
+      return (m_graph->index_of(key));
+    }
+
+    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]);
+    }
+
+  protected:
+    const 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;
+  };
+
+  //==========================
+  // Reverse Edge Property Map
+  //==========================
+
+  template <typename Descriptor>
+  struct grid_graph_reverse_edge_map {
+  public:
+    typedef Descriptor value_type;
+    typedef Descriptor reference_type;
+    typedef reference_type reference;
+    typedef Descriptor key_type;
+    typedef readable_property_map_tag category;
+
+    grid_graph_reverse_edge_map() { }
+
+    value_type operator[](const key_type& key) const {
+      return (value_type(key.second, key.first));
+    }
+
+    friend inline Descriptor
+    get(const grid_graph_reverse_edge_map<Descriptor>& rev_map,
+        const typename grid_graph_reverse_edge_map<Descriptor>::key_type& key)
+    {
+      return (rev_map[key]);
+    }
+  };
+
+  template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+  struct property_map<BOOST_GRID_GRAPH_TYPE, edge_reverse_t> {
+    typedef grid_graph_reverse_edge_map<BOOST_GRID_GRAPH_TRAITS_T::edge_descriptor> type;
+    typedef type const_type;
+  };
+
+  //=================
+  // Function Objects
+  //=================
+
+  namespace detail {
+
+    // vertex_at
+    template <typename Graph>
+    struct grid_graph_vertex_at {
+
+      typedef typename graph_traits<Graph>::vertex_descriptor result_type;
+
+      grid_graph_vertex_at() : m_graph(0) {}
+
+      grid_graph_vertex_at(const Graph* graph) :
+        m_graph(graph) { }
+
+      result_type
+      operator()
+      (typename graph_traits<Graph>::vertices_size_type vertex_index) const {
+        return (vertex(vertex_index, *m_graph));
+      }
+
+    private:
+      const Graph* m_graph;
+    };
+
+    // out_edge_at
+    template <typename Graph>
+    struct grid_graph_out_edge_at {
+
+    private:
+      typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+
+    public:
+      typedef typename graph_traits<Graph>::edge_descriptor result_type;
+
+      grid_graph_out_edge_at() : m_vertex(), m_graph(0) {}
+
+      grid_graph_out_edge_at(vertex_descriptor source_vertex,
+                             const Graph* graph) :
+        m_vertex(source_vertex),
+        m_graph(graph) { }
+
+      result_type
+      operator()
+      (typename graph_traits<Graph>::degree_size_type out_edge_index) const {
+        return (out_edge_at(m_vertex, out_edge_index, *m_graph));
+      }
+
+    private:
+      vertex_descriptor m_vertex;
+      const Graph* m_graph;
+    };
+
+    // in_edge_at
+    template <typename Graph>
+    struct grid_graph_in_edge_at {
+
+    private:
+      typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+
+    public:
+      typedef typename graph_traits<Graph>::edge_descriptor result_type;
+
+      grid_graph_in_edge_at() : m_vertex(), m_graph(0) {}
+
+      grid_graph_in_edge_at(vertex_descriptor target_vertex,
+                            const Graph* graph) :
+        m_vertex(target_vertex),
+        m_graph(graph) { }
+
+      result_type
+      operator()
+      (typename graph_traits<Graph>::degree_size_type in_edge_index) const {
+        return (in_edge_at(m_vertex, in_edge_index, *m_graph));
+      }
+
+    private:
+      vertex_descriptor m_vertex;
+      const Graph* m_graph;
+    };
+
+    // edge_at
+    template <typename Graph>
+    struct grid_graph_edge_at {
+
+      typedef typename graph_traits<Graph>::edge_descriptor result_type;
+
+      grid_graph_edge_at() : m_graph(0) {}
+
+      grid_graph_edge_at(const Graph* graph) :
+        m_graph(graph) { }
+
+      result_type
+      operator()
+      (typename graph_traits<Graph>::edges_size_type edge_index) const {
+        return (edge_at(edge_index, *m_graph));
+      }
+
+    private:
+      const Graph* m_graph;
+    };
+
+    // adjacent_vertex_at
+    template <typename Graph>
+    struct grid_graph_adjacent_vertex_at {
+
+    public:
+      typedef typename graph_traits<Graph>::vertex_descriptor result_type;
+
+      grid_graph_adjacent_vertex_at(result_type source_vertex,
+                                    const Graph* graph) :
+        m_vertex(source_vertex),
+        m_graph(graph) { }
+
+      result_type
+      operator()
+      (typename graph_traits<Graph>::degree_size_type adjacent_index) const {
+        return (target(out_edge_at(m_vertex, adjacent_index, *m_graph), *m_graph));
+      }
+
+    private:
+      result_type m_vertex;
+      const Graph* m_graph;
+    };
+
+  } // namespace detail
+
+  //===========
+  // 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 detail::grid_graph_vertex_at<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 detail::grid_graph_edge_at<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 detail::grid_graph_out_edge_at<type> out_edge_function;
+    typedef transform_iterator<out_edge_function, degree_iterator> out_edge_iterator;
+
+    // in_edge_iterator
+    typedef detail::grid_graph_in_edge_at<type> in_edge_function;
+    typedef transform_iterator<in_edge_function, degree_iterator> in_edge_iterator;
+
+    // adjacency_iterator
+    typedef detail::grid_graph_adjacent_vertex_at<type> adjacent_vertex_function;
+    typedef transform_iterator<adjacent_vertex_function, degree_iterator> adjacency_iterator;
+
+    // categories
+    typedef directed_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,
+                     vertices_size_type(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 {
+    
+      boost::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 indices 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);
+
+      BOOST_ASSERT (source_vertex != target_vertex);
+
+      // 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. Indices 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. Indices 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(),
+                        vertices_size_type(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
+    //================
+
+    friend inline std::pair<typename type::vertex_iterator,
+                            typename type::vertex_iterator> 
+    vertices(const type& graph) {
+      typedef typename type::vertex_iterator vertex_iterator;
+      typedef typename type::vertex_function vertex_function;
+      typedef typename type::vertex_index_iterator vertex_index_iterator;
+
+      return (std::make_pair
+              (vertex_iterator(vertex_index_iterator(0),
+                               vertex_function(&graph)),
+               vertex_iterator(vertex_index_iterator(graph.num_vertices()),
+                               vertex_function(&graph))));
+    }
+
+    friend inline typename type::vertices_size_type
+    num_vertices(const type& graph) {
+      return (graph.num_vertices());
+    }
+
+    friend inline typename type::vertex_descriptor
+    vertex(typename type::vertices_size_type vertex_index,
+           const type& graph) {
+
+      return (graph.vertex_at(vertex_index));
+    }
+
+    //===============
+    // IncidenceGraph
+    //===============
+
+    friend inline std::pair<typename type::out_edge_iterator,
+                            typename type::out_edge_iterator>
+    out_edges(typename type::vertex_descriptor vertex,
+              const type& graph) {
+      typedef typename type::degree_iterator degree_iterator;
+      typedef typename type::out_edge_function out_edge_function;
+      typedef typename type::out_edge_iterator out_edge_iterator;
+
+      return (std::make_pair
+              (out_edge_iterator(degree_iterator(0),
+                                 out_edge_function(vertex, &graph)),
+               out_edge_iterator(degree_iterator(graph.out_degree(vertex)),
+                                 out_edge_function(vertex, &graph))));
+    }
+
+    friend inline typename type::degree_size_type
+    out_degree
+    (typename type::vertex_descriptor vertex,
+     const type& graph) {
+      return (graph.out_degree(vertex));
+    }
+
+    friend inline typename type::edge_descriptor
+    out_edge_at(typename type::vertex_descriptor vertex,
+                typename type::degree_size_type out_edge_index,
+                const type& graph) {
+      return (graph.out_edge_at(vertex, out_edge_index));
+    }
+
+    //===============
+    // AdjacencyGraph
+    //===============
+
+    friend typename std::pair<typename type::adjacency_iterator,
+                              typename type::adjacency_iterator>
+    adjacent_vertices (typename type::vertex_descriptor vertex,
+                       const type& graph) {
+      typedef typename type::degree_iterator degree_iterator;
+      typedef typename type::adjacent_vertex_function adjacent_vertex_function;
+      typedef typename type::adjacency_iterator adjacency_iterator;
+
+      return (std::make_pair
+              (adjacency_iterator(degree_iterator(0),
+                                 adjacent_vertex_function(vertex, &graph)),
+               adjacency_iterator(degree_iterator(graph.out_degree(vertex)),
+                                 adjacent_vertex_function(vertex, &graph))));
+    }
+
+    //==============
+    // EdgeListGraph
+    //==============
+
+    friend inline typename type::edges_size_type
+    num_edges(const type& graph) {
+      return (graph.num_edges());
+    }
+
+    friend inline typename type::edge_descriptor
+    edge_at(typename type::edges_size_type edge_index,
+            const type& graph) {
+      return (graph.edge_at(edge_index));
+    }
+
+    friend inline std::pair<typename type::edge_iterator,
+                            typename type::edge_iterator>
+    edges(const type& graph) {
+      typedef typename type::edge_index_iterator edge_index_iterator;
+      typedef typename type::edge_function edge_function;
+      typedef typename type::edge_iterator edge_iterator;
+
+      return (std::make_pair
+              (edge_iterator(edge_index_iterator(0),
+                             edge_function(&graph)),
+               edge_iterator(edge_index_iterator(graph.num_edges()),
+                             edge_function(&graph))));
+    }
+
+    //===================
+    // BiDirectionalGraph
+    //===================
+
+    friend inline std::pair<typename type::in_edge_iterator,
+                            typename type::in_edge_iterator>
+    in_edges(typename type::vertex_descriptor vertex,
+             const type& graph) {
+      typedef typename type::in_edge_function in_edge_function;
+      typedef typename type::degree_iterator degree_iterator;
+      typedef typename type::in_edge_iterator in_edge_iterator;
+
+      return (std::make_pair
+              (in_edge_iterator(degree_iterator(0),
+                                in_edge_function(vertex, &graph)),
+               in_edge_iterator(degree_iterator(graph.in_degree(vertex)),
+                                in_edge_function(vertex, &graph))));
+    }
+
+    friend inline typename type::degree_size_type
+    in_degree (typename type::vertex_descriptor vertex,
+               const type& graph) {
+      return (graph.in_degree(vertex));
+    }
+
+    friend inline typename type::degree_size_type
+    degree (typename type::vertex_descriptor vertex,
+            const type& graph) {
+      return (graph.out_degree(vertex) * 2);
+    }
+
+    friend inline typename type::edge_descriptor
+    in_edge_at(typename type::vertex_descriptor vertex,
+               typename type::degree_size_type in_edge_index,
+               const type& graph) {
+      return (graph.in_edge_at(vertex, in_edge_index));
+    }
+
+
+    //==================
+    // Adjacency Matrix
+    //==================
+
+    friend std::pair<typename type::edge_descriptor, bool>
+    edge (typename type::vertex_descriptor source_vertex,
+          typename type::vertex_descriptor destination_vertex,
+          const type& graph) {
+
+      std::pair<typename type::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) {
+
+        typename type::vertices_size_type dim_difference = 0;
+        typename type::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
+    //=============================
+
+    friend inline typename type::vertices_size_type
+    get(vertex_index_t,
+        const type& graph,
+        typename type::vertex_descriptor vertex) {
+      return (graph.index_of(vertex));
+    }
+
+    friend inline typename type::edges_size_type
+    get(edge_index_t,
+        const type& graph,
+        typename type::edge_descriptor edge) {
+      return (graph.index_of(edge));
+    }
+
+    friend inline grid_graph_index_map<
+                    type,
+                    typename type::vertex_descriptor,
+                    typename type::vertices_size_type>
+    get(vertex_index_t, const type& graph) {
+      return (grid_graph_index_map<
+                type,
+                typename type::vertex_descriptor,
+                typename type::vertices_size_type>(graph));
+    }
+
+    friend inline grid_graph_index_map<
+                    type,
+                    typename type::edge_descriptor,
+                    typename type::edges_size_type>
+    get(edge_index_t, const type& graph) {
+      return (grid_graph_index_map<
+                type,
+                typename type::edge_descriptor,
+                typename type::edges_size_type>(graph));
+    }                                       
+
+    friend inline grid_graph_reverse_edge_map<
+                    typename type::edge_descriptor>
+    get(edge_reverse_t, const type& graph) {
+      return (grid_graph_reverse_edge_map<
+                typename type::edge_descriptor>());
+    }                                       
+
+    template<typename Graph,
+             typename Descriptor,
+             typename Index>
+    friend struct grid_graph_index_map;
+
+    template<typename Descriptor>
+    friend struct grid_graph_reverse_edge_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