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