boost/graph/grid_graph.hpp
//======================================================================= // 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/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