diff options
Diffstat (limited to 'boost/graph/grid_graph.hpp')
| -rw-r--r-- | boost/graph/grid_graph.hpp | 243 |
1 files changed, 107 insertions, 136 deletions
diff --git a/boost/graph/grid_graph.hpp b/boost/graph/grid_graph.hpp index 7bb3732422..9a09fca347 100644 --- a/boost/graph/grid_graph.hpp +++ b/boost/graph/grid_graph.hpp @@ -30,11 +30,6 @@ #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 > @@ -68,6 +63,13 @@ namespace boost { 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; }; @@ -106,6 +108,13 @@ namespace boost { 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> @@ -442,7 +451,7 @@ namespace boost { vertex_descriptor vertex_at (vertices_size_type vertex_index) const { - array<vertices_size_type, Dimensions> vertex; + boost::array<vertices_size_type, Dimensions> vertex; vertices_size_type index_divider = 1; for (std::size_t dimension_index = 0; @@ -532,6 +541,8 @@ namespace boost { 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; @@ -732,13 +743,12 @@ namespace boost { // 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); + 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), @@ -747,16 +757,14 @@ namespace boost { 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) { + friend inline typename type::vertices_size_type + num_vertices(const 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) { + friend inline typename type::vertex_descriptor + vertex(typename type::vertices_size_type vertex_index, + const type& graph) { return (graph.vertex_at(vertex_index)); } @@ -765,14 +773,13 @@ namespace boost { // 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); + 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), @@ -781,19 +788,17 @@ namespace boost { out_edge_function(vertex, &graph)))); } - template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> - friend inline BOOST_GRID_GRAPH_TYPE_MEM degree_size_type + friend inline typename type::degree_size_type out_degree - (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, - const BOOST_GRID_GRAPH_TYPE& graph) { + (typename type::vertex_descriptor vertex, + const 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) { + 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)); } @@ -801,14 +806,13 @@ namespace boost { // 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); + 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), @@ -821,26 +825,23 @@ namespace boost { // 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) { + friend inline typename type::edges_size_type + num_edges(const 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) { + friend inline typename type::edge_descriptor + edge_at(typename type::edges_size_type edge_index, + const 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); + 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), @@ -853,14 +854,13 @@ namespace boost { // 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); + 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), @@ -869,25 +869,22 @@ namespace boost { 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) { + friend inline typename type::degree_size_type + in_degree (typename type::vertex_descriptor vertex, + const 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) { + friend inline typename type::degree_size_type + degree (typename type::vertex_descriptor vertex, + const 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) { + 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)); } @@ -896,21 +893,20 @@ namespace boost { // 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) { + 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<BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor, bool> edge_exists = + 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) { - BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type dim_difference = 0; - BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type + 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]; @@ -957,78 +953,55 @@ namespace boost { // Index Property Map Functions //============================= - template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> - friend inline BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type + friend inline typename type::vertices_size_type get(vertex_index_t, - const BOOST_GRID_GRAPH_TYPE& graph, - BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex) { + const type& graph, + typename type::vertex_descriptor vertex) { return (graph.index_of(vertex)); } - template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> - friend inline BOOST_GRID_GRAPH_TYPE_MEM edges_size_type + friend inline typename type::edges_size_type get(edge_index_t, - const BOOST_GRID_GRAPH_TYPE& graph, - BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor edge) { + const type& graph, + typename type::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) { + type, + typename type::vertex_descriptor, + typename type::vertices_size_type> + get(vertex_index_t, const 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)); + type, + typename type::vertex_descriptor, + typename type::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) { + type, + typename type::edge_descriptor, + typename type::edges_size_type> + get(edge_index_t, const 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)); + type, + typename type::edge_descriptor, + typename type::edges_size_type>(graph)); } - template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS> friend inline grid_graph_reverse_edge_map< - BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor> - get(edge_reverse_t, const BOOST_GRID_GRAPH_TYPE& graph) { + typename type::edge_descriptor> + get(edge_reverse_t, const type& graph) { return (grid_graph_reverse_edge_map< - BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor>()); + typename type::edge_descriptor>()); } 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; template<typename Descriptor> - 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<typename Descriptor> friend struct grid_graph_reverse_edge_map; }; // grid_graph @@ -1036,8 +1009,6 @@ namespace boost { } // 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 |