| //======================================================================= |
| // Copyright 2009 Trustees of Indiana University. |
| // Authors: Michael Hansen, Andrew Lumsdaine |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| |
| #ifndef BOOST_GRAPH_GRID_GRAPH_HPP |
| #define BOOST_GRAPH_GRID_GRAPH_HPP |
| |
| #include <cmath> |
| #include <functional> |
| #include <numeric> |
| |
| #include <boost/array.hpp> |
| #include <boost/bind.hpp> |
| #include <boost/limits.hpp> |
| #include <boost/make_shared.hpp> |
| #include <boost/graph/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_TYPE_MEM typename BOOST_GRID_GRAPH_TYPE:: |
| |
| #define BOOST_GRID_GRAPH_TYPE_TD(mem) \ |
| typedef typename BOOST_GRID_GRAPH_TYPE::mem mem |
| |
| #define BOOST_GRID_GRAPH_TRAITS_T \ |
| typename graph_traits<BOOST_GRID_GRAPH_TYPE > |
| |
| namespace boost { |
| |
| // Class prototype for grid_graph |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| class grid_graph; |
| |
| //=================== |
| // Index Property Map |
| //=================== |
| |
| template <typename Graph, |
| typename Descriptor, |
| typename Index> |
| struct grid_graph_index_map { |
| public: |
| typedef Index value_type; |
| typedef Index reference_type; |
| typedef reference_type reference; |
| typedef Descriptor key_type; |
| typedef readable_property_map_tag category; |
| |
| grid_graph_index_map() { } |
| |
| grid_graph_index_map(const Graph& graph) : |
| m_graph(make_shared<Graph>(graph)) { } |
| |
| value_type operator[](key_type key) const { |
| return (m_graph->index_of(key)); |
| } |
| |
| protected: |
| shared_ptr<Graph> m_graph; |
| }; |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| struct property_map<BOOST_GRID_GRAPH_TYPE, vertex_index_t> { |
| typedef grid_graph_index_map<BOOST_GRID_GRAPH_TYPE, |
| BOOST_GRID_GRAPH_TRAITS_T::vertex_descriptor, |
| BOOST_GRID_GRAPH_TRAITS_T::vertices_size_type> type; |
| typedef type const_type; |
| }; |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| struct property_map<BOOST_GRID_GRAPH_TYPE, edge_index_t> { |
| typedef grid_graph_index_map<BOOST_GRID_GRAPH_TYPE, |
| BOOST_GRID_GRAPH_TRAITS_T::edge_descriptor, |
| BOOST_GRID_GRAPH_TRAITS_T::edges_size_type> type; |
| typedef type const_type; |
| }; |
| |
| //================= |
| // 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 undirected_tag directed_category; |
| typedef disallow_parallel_edge_tag edge_parallel_category; |
| struct traversal_category : virtual public incidence_graph_tag, |
| virtual public adjacency_graph_tag, |
| virtual public vertex_list_graph_tag, |
| virtual public edge_list_graph_tag, |
| virtual public bidirectional_graph_tag, |
| virtual public adjacency_matrix_tag { }; |
| |
| static inline vertex_descriptor null_vertex() |
| { |
| vertex_descriptor maxed_out_vertex; |
| std::fill(maxed_out_vertex.begin(), maxed_out_vertex.end(), |
| (std::numeric_limits<vertices_size_type>::max)()); |
| |
| return (maxed_out_vertex); |
| } |
| |
| // Constructor that defaults to no wrapping for all dimensions. |
| grid_graph(vertex_descriptor dimension_lengths) : |
| m_dimension_lengths(dimension_lengths) { |
| |
| std::fill(m_wrap_dimension.begin(), |
| m_wrap_dimension.end(), false); |
| |
| precalculate(); |
| } |
| |
| // Constructor that allows for wrapping to be specified for all |
| // dimensions at once. |
| grid_graph(vertex_descriptor dimension_lengths, |
| bool wrap_all_dimensions) : |
| m_dimension_lengths(dimension_lengths) { |
| |
| std::fill(m_wrap_dimension.begin(), |
| m_wrap_dimension.end(), |
| wrap_all_dimensions); |
| |
| precalculate(); |
| } |
| |
| // Constructor that allows for individual dimension wrapping to be |
| // specified. |
| grid_graph(vertex_descriptor dimension_lengths, |
| WrapDimensionArray wrap_dimension) : |
| m_dimension_lengths(dimension_lengths), |
| m_wrap_dimension(wrap_dimension) { |
| |
| precalculate(); |
| } |
| |
| // Returns the number of dimensions in the graph |
| inline std::size_t dimensions() const { |
| return (Dimensions); |
| } |
| |
| // Returns the length of dimension [dimension_index] |
| inline vertices_size_type length(std::size_t dimension) const { |
| return (m_dimension_lengths[dimension]); |
| } |
| |
| // Returns a value indicating if dimension [dimension_index] wraps |
| inline bool wrapped(std::size_t dimension) const { |
| return (m_wrap_dimension[dimension]); |
| } |
| |
| // Gets the vertex that is [distance] units ahead of [vertex] in |
| // dimension [dimension_index]. |
| vertex_descriptor next |
| (vertex_descriptor vertex, |
| std::size_t dimension_index, |
| vertices_size_type distance = 1) const { |
| |
| vertices_size_type new_position = |
| vertex[dimension_index] + distance; |
| |
| if (wrapped(dimension_index)) { |
| new_position %= length(dimension_index); |
| } |
| else { |
| // Stop at the end of this dimension if necessary. |
| new_position = |
| (std::min)(new_position, |
| length(dimension_index) - 1); |
| } |
| |
| vertex[dimension_index] = new_position; |
| |
| return (vertex); |
| } |
| |
| // Gets the vertex that is [distance] units behind [vertex] in |
| // dimension [dimension_index]. |
| vertex_descriptor previous |
| (vertex_descriptor vertex, |
| std::size_t dimension_index, |
| vertices_size_type distance = 1) const { |
| |
| // We're assuming that vertices_size_type is unsigned, so we |
| // need to be careful about the math. |
| vertex[dimension_index] = |
| (distance > vertex[dimension_index]) ? |
| (wrapped(dimension_index) ? |
| (length(dimension_index) - (distance % length(dimension_index))) : 0) : |
| vertex[dimension_index] - distance; |
| |
| return (vertex); |
| } |
| |
| protected: |
| |
| // Returns the number of vertices in the graph |
| inline vertices_size_type num_vertices() const { |
| return (m_num_vertices); |
| } |
| |
| // Returns the number of edges in the graph |
| inline edges_size_type num_edges() const { |
| return (m_num_edges); |
| } |
| |
| // Returns the number of edges in dimension [dimension_index] |
| inline edges_size_type num_edges |
| (std::size_t dimension_index) const { |
| return (m_edge_count[dimension_index]); |
| } |
| |
| // Returns the index of [vertex] (See also vertex_at) |
| vertices_size_type index_of(vertex_descriptor vertex) const { |
| |
| vertices_size_type vertex_index = 0; |
| vertices_size_type index_multiplier = 1; |
| |
| for (std::size_t dimension_index = 0; |
| dimension_index < Dimensions; |
| ++dimension_index) { |
| |
| vertex_index += (vertex[dimension_index] * index_multiplier); |
| index_multiplier *= length(dimension_index); |
| } |
| |
| return (vertex_index); |
| } |
| |
| // Returns the vertex whose index is [vertex_index] (See also |
| // index_of(vertex_descriptor)) |
| vertex_descriptor vertex_at |
| (vertices_size_type vertex_index) const { |
| |
| array<vertices_size_type, Dimensions> vertex; |
| vertices_size_type index_divider = 1; |
| |
| for (std::size_t dimension_index = 0; |
| dimension_index < Dimensions; |
| ++dimension_index) { |
| |
| vertex[dimension_index] = (vertex_index / index_divider) % |
| length(dimension_index); |
| |
| index_divider *= length(dimension_index); |
| } |
| |
| return (vertex); |
| } |
| |
| // Returns the edge whose index is [edge_index] (See also |
| // index_of(edge_descriptor)). NOTE: The index mapping is |
| // dependent upon dimension wrapping. |
| edge_descriptor edge_at(edges_size_type edge_index) const { |
| |
| // Edge 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); |
| |
| // 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(), 1, |
| std::multiplies<vertices_size_type>()); |
| |
| // Calculate number of edges in each dimension |
| m_num_edges = 0; |
| |
| for (std::size_t dimension_index = 0; |
| dimension_index < Dimensions; |
| ++dimension_index) { |
| |
| if (wrapped(dimension_index)) { |
| m_edge_count[dimension_index] = num_vertices() * 2; |
| } |
| else { |
| m_edge_count[dimension_index] = |
| (num_vertices() - (num_vertices() / length(dimension_index))) * 2; |
| } |
| |
| m_num_edges += num_edges(dimension_index); |
| } |
| } |
| |
| const vertex_descriptor m_dimension_lengths; |
| WrapDimensionArray m_wrap_dimension; |
| vertices_size_type m_num_vertices; |
| |
| boost::array<edges_size_type, Dimensions> m_edge_count; |
| edges_size_type m_num_edges; |
| |
| public: |
| |
| //================ |
| // VertexListGraph |
| //================ |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM vertex_iterator, |
| BOOST_GRID_GRAPH_TYPE_MEM vertex_iterator> |
| vertices(const BOOST_GRID_GRAPH_TYPE& graph) { |
| BOOST_GRID_GRAPH_TYPE_TD(vertex_iterator); |
| BOOST_GRID_GRAPH_TYPE_TD(vertex_function); |
| BOOST_GRID_GRAPH_TYPE_TD(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)))); |
| } |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type |
| num_vertices(const BOOST_GRID_GRAPH_TYPE& graph) { |
| return (graph.num_vertices()); |
| } |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor |
| vertex(BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type vertex_index, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| |
| return (graph.vertex_at(vertex_index)); |
| } |
| |
| //=============== |
| // IncidenceGraph |
| //=============== |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM out_edge_iterator, |
| BOOST_GRID_GRAPH_TYPE_MEM out_edge_iterator> |
| out_edges(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| BOOST_GRID_GRAPH_TYPE_TD(degree_iterator); |
| BOOST_GRID_GRAPH_TYPE_TD(out_edge_function); |
| BOOST_GRID_GRAPH_TYPE_TD(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)))); |
| } |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM degree_size_type |
| out_degree |
| (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| return (graph.out_degree(vertex)); |
| } |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor |
| out_edge_at(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, |
| BOOST_GRID_GRAPH_TYPE_MEM degree_size_type out_edge_index, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| return (graph.out_edge_at(vertex, out_edge_index)); |
| } |
| |
| //=============== |
| // AdjacencyGraph |
| //=============== |
| |
| template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend typename std::pair<BOOST_GRID_GRAPH_TYPE_MEM adjacency_iterator, |
| BOOST_GRID_GRAPH_TYPE_MEM adjacency_iterator> |
| adjacent_vertices (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| BOOST_GRID_GRAPH_TYPE_TD(degree_iterator); |
| BOOST_GRID_GRAPH_TYPE_TD(adjacent_vertex_function); |
| BOOST_GRID_GRAPH_TYPE_TD(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 |
| //============== |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM edges_size_type |
| num_edges(const BOOST_GRID_GRAPH_TYPE& graph) { |
| return (graph.num_edges()); |
| } |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor |
| edge_at(BOOST_GRID_GRAPH_TYPE_MEM edges_size_type edge_index, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| return (graph.edge_at(edge_index)); |
| } |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM edge_iterator, |
| BOOST_GRID_GRAPH_TYPE_MEM edge_iterator> |
| edges(const BOOST_GRID_GRAPH_TYPE& graph) { |
| BOOST_GRID_GRAPH_TYPE_TD(edge_index_iterator); |
| BOOST_GRID_GRAPH_TYPE_TD(edge_function); |
| BOOST_GRID_GRAPH_TYPE_TD(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 |
| //=================== |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM in_edge_iterator, |
| BOOST_GRID_GRAPH_TYPE_MEM in_edge_iterator> |
| in_edges(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| BOOST_GRID_GRAPH_TYPE_TD(in_edge_function); |
| BOOST_GRID_GRAPH_TYPE_TD(degree_iterator); |
| BOOST_GRID_GRAPH_TYPE_TD(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)))); |
| } |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM degree_size_type |
| in_degree (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| return (graph.in_degree(vertex)); |
| } |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM degree_size_type |
| degree (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| return (graph.out_degree(vertex) * 2); |
| } |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor |
| in_edge_at(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, |
| BOOST_GRID_GRAPH_TYPE_MEM degree_size_type in_edge_index, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| return (graph.in_edge_at(vertex, in_edge_index)); |
| } |
| |
| |
| //================== |
| // Adjacency Matrix |
| //================== |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend std::pair<BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor, bool> |
| edge (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor source_vertex, |
| BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor destination_vertex, |
| const BOOST_GRID_GRAPH_TYPE& graph) { |
| |
| std::pair<BOOST_GRID_GRAPH_TYPE_MEM 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) { |
| |
| BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type dim_difference = 0; |
| BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type |
| source_dim = source_vertex[dimension_index], |
| dest_dim = destination_vertex[dimension_index]; |
| |
| dim_difference = (source_dim > dest_dim) ? |
| (source_dim - dest_dim) : (dest_dim - source_dim); |
| |
| if (dim_difference > 0) { |
| |
| // If we've already found a valid edge, this would mean that |
| // the vertices are really diagonal across dimensions and |
| // therefore not connected. |
| if (edge_exists.second) { |
| edge_exists.second = false; |
| break; |
| } |
| |
| // If the difference is one, the vertices are right next to |
| // each other and the edge is valid. The edge is still |
| // valid, though, if the dimension wraps and the vertices |
| // are on opposite ends. |
| if ((dim_difference == 1) || |
| (graph.wrapped(dimension_index) && |
| (((source_dim == 0) && (dest_dim == (graph.length(dimension_index) - 1))) || |
| ((dest_dim == 0) && (source_dim == (graph.length(dimension_index) - 1)))))) { |
| |
| edge_exists.second = true; |
| // Stay in the loop to check for diagonal vertices. |
| } |
| else { |
| |
| // Stop checking - the vertices are too far apart. |
| edge_exists.second = false; |
| break; |
| } |
| } |
| |
| } // for dimension_index |
| |
| return (edge_exists); |
| } |
| |
| |
| //============================= |
| // Index Property Map Functions |
| //============================= |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type |
| get(vertex_index_t, |
| const BOOST_GRID_GRAPH_TYPE& graph, |
| BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex) { |
| return (graph.index_of(vertex)); |
| } |
| |
| template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline BOOST_GRID_GRAPH_TYPE_MEM edges_size_type |
| get(edge_index_t, |
| const BOOST_GRID_GRAPH_TYPE& graph, |
| BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor edge) { |
| return (graph.index_of(edge)); |
| } |
| |
| template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline grid_graph_index_map< |
| BOOST_GRID_GRAPH_TYPE, |
| BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor, |
| BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type> |
| get(vertex_index_t, const BOOST_GRID_GRAPH_TYPE& graph) { |
| return (grid_graph_index_map< |
| BOOST_GRID_GRAPH_TYPE, |
| BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor, |
| BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type>(graph)); |
| } |
| |
| template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS> |
| friend inline grid_graph_index_map< |
| BOOST_GRID_GRAPH_TYPE, |
| BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor, |
| BOOST_GRID_GRAPH_TYPE_MEM edges_size_type> |
| get(edge_index_t, const BOOST_GRID_GRAPH_TYPE& graph) { |
| return (grid_graph_index_map< |
| BOOST_GRID_GRAPH_TYPE, |
| BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor, |
| BOOST_GRID_GRAPH_TYPE_MEM edges_size_type>(graph)); |
| } |
| |
| template<typename Graph, |
| typename Descriptor, |
| typename Index> |
| friend inline Index |
| get(const grid_graph_index_map<Graph, Descriptor, Index>& index_map, |
| const typename grid_graph_index_map<Graph, Descriptor, Index>::key_type& key) |
| { |
| return (index_map[key]); |
| } |
| |
| template<typename Graph, |
| typename Descriptor, |
| typename Index> |
| friend struct grid_graph_index_map; |
| |
| }; // grid_graph |
| |
| } // namespace boost |
| |
| #undef BOOST_GRID_GRAPH_TYPE |
| #undef BOOST_GRID_GRAPH_TYPE_TD |
| #undef BOOST_GRID_GRAPH_TYPE_MEM |
| #undef BOOST_GRID_GRAPH_TEMPLATE_PARAMS |
| #undef BOOST_GRID_GRAPH_TRAITS_T |
| |
| #endif // BOOST_GRAPH_GRID_GRAPH_HPP |