1 //======================================================================= 2 // Copyright 2009 Trustees of Indiana University. 3 // Authors: Michael Hansen, Andrew Lumsdaine 4 // 5 // Distributed under the Boost Software License, Version 1.0. (See 6 // accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 //======================================================================= 9 10 #ifndef BOOST_GRAPH_GRID_GRAPH_HPP 11 #define BOOST_GRAPH_GRID_GRAPH_HPP 12 13 #include <cmath> 14 #include <functional> 15 #include <numeric> 16 17 #include <boost/array.hpp> 18 #include <boost/bind.hpp> 19 #include <boost/limits.hpp> 20 #include <boost/graph/graph_traits.hpp> 21 #include <boost/graph/properties.hpp> 22 #include <boost/iterator/counting_iterator.hpp> 23 #include <boost/iterator/transform_iterator.hpp> 24 #include <boost/property_map/property_map.hpp> 25 26 #define BOOST_GRID_GRAPH_TEMPLATE_PARAMS \ 27 std::size_t DimensionsT, typename VertexIndexT, \ 28 typename EdgeIndexT 29 30 #define BOOST_GRID_GRAPH_TYPE \ 31 grid_graph<DimensionsT, VertexIndexT, EdgeIndexT> 32 33 #define BOOST_GRID_GRAPH_TRAITS_T \ 34 typename graph_traits<BOOST_GRID_GRAPH_TYPE > 35 36 namespace boost { 37 38 // Class prototype for grid_graph 39 template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> 40 class grid_graph; 41 42 //=================== 43 // Index Property Map 44 //=================== 45 46 template <typename Graph, 47 typename Descriptor, 48 typename Index> 49 struct grid_graph_index_map { 50 public: 51 typedef Index value_type; 52 typedef Index reference_type; 53 typedef reference_type reference; 54 typedef Descriptor key_type; 55 typedef readable_property_map_tag category; 56 grid_graph_index_mapboost::grid_graph_index_map57 grid_graph_index_map() { } 58 grid_graph_index_mapboost::grid_graph_index_map59 grid_graph_index_map(const Graph& graph) : 60 m_graph(&graph) { } 61 operator []boost::grid_graph_index_map62 value_type operator[](key_type key) const { 63 return (m_graph->index_of(key)); 64 } 65 66 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)67 get(const grid_graph_index_map<Graph, Descriptor, Index>& index_map, 68 const typename grid_graph_index_map<Graph, Descriptor, Index>::key_type& key) 69 { 70 return (index_map[key]); 71 } 72 73 protected: 74 const Graph* m_graph; 75 }; 76 77 template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> 78 struct property_map<BOOST_GRID_GRAPH_TYPE, vertex_index_t> { 79 typedef grid_graph_index_map<BOOST_GRID_GRAPH_TYPE, 80 BOOST_GRID_GRAPH_TRAITS_T::vertex_descriptor, 81 BOOST_GRID_GRAPH_TRAITS_T::vertices_size_type> type; 82 typedef type const_type; 83 }; 84 85 template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> 86 struct property_map<BOOST_GRID_GRAPH_TYPE, edge_index_t> { 87 typedef grid_graph_index_map<BOOST_GRID_GRAPH_TYPE, 88 BOOST_GRID_GRAPH_TRAITS_T::edge_descriptor, 89 BOOST_GRID_GRAPH_TRAITS_T::edges_size_type> type; 90 typedef type const_type; 91 }; 92 93 //========================== 94 // Reverse Edge Property Map 95 //========================== 96 97 template <typename Descriptor> 98 struct grid_graph_reverse_edge_map { 99 public: 100 typedef Descriptor value_type; 101 typedef Descriptor reference_type; 102 typedef reference_type reference; 103 typedef Descriptor key_type; 104 typedef readable_property_map_tag category; 105 grid_graph_reverse_edge_mapboost::grid_graph_reverse_edge_map106 grid_graph_reverse_edge_map() { } 107 operator []boost::grid_graph_reverse_edge_map108 value_type operator[](const key_type& key) const { 109 return (value_type(key.second, key.first)); 110 } 111 112 friend inline Descriptor get(const grid_graph_reverse_edge_map<Descriptor> & rev_map,const typename grid_graph_reverse_edge_map<Descriptor>::key_type & key)113 get(const grid_graph_reverse_edge_map<Descriptor>& rev_map, 114 const typename grid_graph_reverse_edge_map<Descriptor>::key_type& key) 115 { 116 return (rev_map[key]); 117 } 118 }; 119 120 template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> 121 struct property_map<BOOST_GRID_GRAPH_TYPE, edge_reverse_t> { 122 typedef grid_graph_reverse_edge_map<BOOST_GRID_GRAPH_TRAITS_T::edge_descriptor> type; 123 typedef type const_type; 124 }; 125 126 //================= 127 // Function Objects 128 //================= 129 130 namespace detail { 131 132 // vertex_at 133 template <typename Graph> 134 struct grid_graph_vertex_at { 135 136 typedef typename graph_traits<Graph>::vertex_descriptor result_type; 137 grid_graph_vertex_atboost::detail::grid_graph_vertex_at138 grid_graph_vertex_at() : m_graph(0) {} 139 grid_graph_vertex_atboost::detail::grid_graph_vertex_at140 grid_graph_vertex_at(const Graph* graph) : 141 m_graph(graph) { } 142 143 result_type operator ()boost::detail::grid_graph_vertex_at144 operator() 145 (typename graph_traits<Graph>::vertices_size_type vertex_index) const { 146 return (vertex(vertex_index, *m_graph)); 147 } 148 149 private: 150 const Graph* m_graph; 151 }; 152 153 // out_edge_at 154 template <typename Graph> 155 struct grid_graph_out_edge_at { 156 157 private: 158 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; 159 160 public: 161 typedef typename graph_traits<Graph>::edge_descriptor result_type; 162 grid_graph_out_edge_atboost::detail::grid_graph_out_edge_at163 grid_graph_out_edge_at() : m_vertex(), m_graph(0) {} 164 grid_graph_out_edge_atboost::detail::grid_graph_out_edge_at165 grid_graph_out_edge_at(vertex_descriptor source_vertex, 166 const Graph* graph) : 167 m_vertex(source_vertex), 168 m_graph(graph) { } 169 170 result_type operator ()boost::detail::grid_graph_out_edge_at171 operator() 172 (typename graph_traits<Graph>::degree_size_type out_edge_index) const { 173 return (out_edge_at(m_vertex, out_edge_index, *m_graph)); 174 } 175 176 private: 177 vertex_descriptor m_vertex; 178 const Graph* m_graph; 179 }; 180 181 // in_edge_at 182 template <typename Graph> 183 struct grid_graph_in_edge_at { 184 185 private: 186 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; 187 188 public: 189 typedef typename graph_traits<Graph>::edge_descriptor result_type; 190 grid_graph_in_edge_atboost::detail::grid_graph_in_edge_at191 grid_graph_in_edge_at() : m_vertex(), m_graph(0) {} 192 grid_graph_in_edge_atboost::detail::grid_graph_in_edge_at193 grid_graph_in_edge_at(vertex_descriptor target_vertex, 194 const Graph* graph) : 195 m_vertex(target_vertex), 196 m_graph(graph) { } 197 198 result_type operator ()boost::detail::grid_graph_in_edge_at199 operator() 200 (typename graph_traits<Graph>::degree_size_type in_edge_index) const { 201 return (in_edge_at(m_vertex, in_edge_index, *m_graph)); 202 } 203 204 private: 205 vertex_descriptor m_vertex; 206 const Graph* m_graph; 207 }; 208 209 // edge_at 210 template <typename Graph> 211 struct grid_graph_edge_at { 212 213 typedef typename graph_traits<Graph>::edge_descriptor result_type; 214 grid_graph_edge_atboost::detail::grid_graph_edge_at215 grid_graph_edge_at() : m_graph(0) {} 216 grid_graph_edge_atboost::detail::grid_graph_edge_at217 grid_graph_edge_at(const Graph* graph) : 218 m_graph(graph) { } 219 220 result_type operator ()boost::detail::grid_graph_edge_at221 operator() 222 (typename graph_traits<Graph>::edges_size_type edge_index) const { 223 return (edge_at(edge_index, *m_graph)); 224 } 225 226 private: 227 const Graph* m_graph; 228 }; 229 230 // adjacent_vertex_at 231 template <typename Graph> 232 struct grid_graph_adjacent_vertex_at { 233 234 public: 235 typedef typename graph_traits<Graph>::vertex_descriptor result_type; 236 grid_graph_adjacent_vertex_atboost::detail::grid_graph_adjacent_vertex_at237 grid_graph_adjacent_vertex_at(result_type source_vertex, 238 const Graph* graph) : 239 m_vertex(source_vertex), 240 m_graph(graph) { } 241 242 result_type operator ()boost::detail::grid_graph_adjacent_vertex_at243 operator() 244 (typename graph_traits<Graph>::degree_size_type adjacent_index) const { 245 return (target(out_edge_at(m_vertex, adjacent_index, *m_graph), *m_graph)); 246 } 247 248 private: 249 result_type m_vertex; 250 const Graph* m_graph; 251 }; 252 253 } // namespace detail 254 255 //=========== 256 // Grid Graph 257 //=========== 258 259 template <std::size_t Dimensions, 260 typename VertexIndex = std::size_t, 261 typename EdgeIndex = VertexIndex> 262 class grid_graph { 263 264 private: 265 typedef boost::array<bool, Dimensions> WrapDimensionArray; grid_graph()266 grid_graph() { }; 267 268 public: 269 270 typedef grid_graph<Dimensions, VertexIndex, EdgeIndex> type; 271 272 // sizes 273 typedef VertexIndex vertices_size_type; 274 typedef EdgeIndex edges_size_type; 275 typedef EdgeIndex degree_size_type; 276 277 // descriptors 278 typedef boost::array<VertexIndex, Dimensions> vertex_descriptor; 279 typedef std::pair<vertex_descriptor, vertex_descriptor> edge_descriptor; 280 281 // vertex_iterator 282 typedef counting_iterator<vertices_size_type> vertex_index_iterator; 283 typedef detail::grid_graph_vertex_at<type> vertex_function; 284 typedef transform_iterator<vertex_function, vertex_index_iterator> vertex_iterator; 285 286 // edge_iterator 287 typedef counting_iterator<edges_size_type> edge_index_iterator; 288 typedef detail::grid_graph_edge_at<type> edge_function; 289 typedef transform_iterator<edge_function, edge_index_iterator> edge_iterator; 290 291 // out_edge_iterator 292 typedef counting_iterator<degree_size_type> degree_iterator; 293 typedef detail::grid_graph_out_edge_at<type> out_edge_function; 294 typedef transform_iterator<out_edge_function, degree_iterator> out_edge_iterator; 295 296 // in_edge_iterator 297 typedef detail::grid_graph_in_edge_at<type> in_edge_function; 298 typedef transform_iterator<in_edge_function, degree_iterator> in_edge_iterator; 299 300 // adjacency_iterator 301 typedef detail::grid_graph_adjacent_vertex_at<type> adjacent_vertex_function; 302 typedef transform_iterator<adjacent_vertex_function, degree_iterator> adjacency_iterator; 303 304 // categories 305 typedef directed_tag directed_category; 306 typedef disallow_parallel_edge_tag edge_parallel_category; 307 struct traversal_category : virtual public incidence_graph_tag, 308 virtual public adjacency_graph_tag, 309 virtual public vertex_list_graph_tag, 310 virtual public edge_list_graph_tag, 311 virtual public bidirectional_graph_tag, 312 virtual public adjacency_matrix_tag { }; 313 null_vertex()314 static inline vertex_descriptor null_vertex() 315 { 316 vertex_descriptor maxed_out_vertex; 317 std::fill(maxed_out_vertex.begin(), maxed_out_vertex.end(), 318 (std::numeric_limits<vertices_size_type>::max)()); 319 320 return (maxed_out_vertex); 321 } 322 323 // Constructor that defaults to no wrapping for all dimensions. grid_graph(vertex_descriptor dimension_lengths)324 grid_graph(vertex_descriptor dimension_lengths) : 325 m_dimension_lengths(dimension_lengths) { 326 327 std::fill(m_wrap_dimension.begin(), 328 m_wrap_dimension.end(), false); 329 330 precalculate(); 331 } 332 333 // Constructor that allows for wrapping to be specified for all 334 // dimensions at once. grid_graph(vertex_descriptor dimension_lengths,bool wrap_all_dimensions)335 grid_graph(vertex_descriptor dimension_lengths, 336 bool wrap_all_dimensions) : 337 m_dimension_lengths(dimension_lengths) { 338 339 std::fill(m_wrap_dimension.begin(), 340 m_wrap_dimension.end(), 341 wrap_all_dimensions); 342 343 precalculate(); 344 } 345 346 // Constructor that allows for individual dimension wrapping to be 347 // specified. grid_graph(vertex_descriptor dimension_lengths,WrapDimensionArray wrap_dimension)348 grid_graph(vertex_descriptor dimension_lengths, 349 WrapDimensionArray wrap_dimension) : 350 m_dimension_lengths(dimension_lengths), 351 m_wrap_dimension(wrap_dimension) { 352 353 precalculate(); 354 } 355 356 // Returns the number of dimensions in the graph dimensions() const357 inline std::size_t dimensions() const { 358 return (Dimensions); 359 } 360 361 // Returns the length of dimension [dimension_index] length(std::size_t dimension) const362 inline vertices_size_type length(std::size_t dimension) const { 363 return (m_dimension_lengths[dimension]); 364 } 365 366 // Returns a value indicating if dimension [dimension_index] wraps wrapped(std::size_t dimension) const367 inline bool wrapped(std::size_t dimension) const { 368 return (m_wrap_dimension[dimension]); 369 } 370 371 // Gets the vertex that is [distance] units ahead of [vertex] in 372 // dimension [dimension_index]. next(vertex_descriptor vertex,std::size_t dimension_index,vertices_size_type distance=1) const373 vertex_descriptor next 374 (vertex_descriptor vertex, 375 std::size_t dimension_index, 376 vertices_size_type distance = 1) const { 377 378 vertices_size_type new_position = 379 vertex[dimension_index] + distance; 380 381 if (wrapped(dimension_index)) { 382 new_position %= length(dimension_index); 383 } 384 else { 385 // Stop at the end of this dimension if necessary. 386 new_position = 387 (std::min)(new_position, 388 vertices_size_type(length(dimension_index) - 1)); 389 } 390 391 vertex[dimension_index] = new_position; 392 393 return (vertex); 394 } 395 396 // Gets the vertex that is [distance] units behind [vertex] in 397 // dimension [dimension_index]. previous(vertex_descriptor vertex,std::size_t dimension_index,vertices_size_type distance=1) const398 vertex_descriptor previous 399 (vertex_descriptor vertex, 400 std::size_t dimension_index, 401 vertices_size_type distance = 1) const { 402 403 // We're assuming that vertices_size_type is unsigned, so we 404 // need to be careful about the math. 405 vertex[dimension_index] = 406 (distance > vertex[dimension_index]) ? 407 (wrapped(dimension_index) ? 408 (length(dimension_index) - (distance % length(dimension_index))) : 0) : 409 vertex[dimension_index] - distance; 410 411 return (vertex); 412 } 413 414 protected: 415 416 // Returns the number of vertices in the graph num_vertices() const417 inline vertices_size_type num_vertices() const { 418 return (m_num_vertices); 419 } 420 421 // Returns the number of edges in the graph num_edges() const422 inline edges_size_type num_edges() const { 423 return (m_num_edges); 424 } 425 426 // Returns the number of edges in dimension [dimension_index] num_edges(std::size_t dimension_index) const427 inline edges_size_type num_edges 428 (std::size_t dimension_index) const { 429 return (m_edge_count[dimension_index]); 430 } 431 432 // Returns the index of [vertex] (See also vertex_at) index_of(vertex_descriptor vertex) const433 vertices_size_type index_of(vertex_descriptor vertex) const { 434 435 vertices_size_type vertex_index = 0; 436 vertices_size_type index_multiplier = 1; 437 438 for (std::size_t dimension_index = 0; 439 dimension_index < Dimensions; 440 ++dimension_index) { 441 442 vertex_index += (vertex[dimension_index] * index_multiplier); 443 index_multiplier *= length(dimension_index); 444 } 445 446 return (vertex_index); 447 } 448 449 // Returns the vertex whose index is [vertex_index] (See also 450 // index_of(vertex_descriptor)) vertex_at(vertices_size_type vertex_index) const451 vertex_descriptor vertex_at 452 (vertices_size_type vertex_index) const { 453 454 boost::array<vertices_size_type, Dimensions> vertex; 455 vertices_size_type index_divider = 1; 456 457 for (std::size_t dimension_index = 0; 458 dimension_index < Dimensions; 459 ++dimension_index) { 460 461 vertex[dimension_index] = (vertex_index / index_divider) % 462 length(dimension_index); 463 464 index_divider *= length(dimension_index); 465 } 466 467 return (vertex); 468 } 469 470 // Returns the edge whose index is [edge_index] (See also 471 // index_of(edge_descriptor)). NOTE: The index mapping is 472 // dependent upon dimension wrapping. edge_at(edges_size_type edge_index) const473 edge_descriptor edge_at(edges_size_type edge_index) const { 474 475 // Edge indices are sorted into bins by dimension 476 std::size_t dimension_index = 0; 477 edges_size_type dimension_edges = num_edges(0); 478 479 while (edge_index >= dimension_edges) { 480 edge_index -= dimension_edges; 481 ++dimension_index; 482 dimension_edges = num_edges(dimension_index); 483 } 484 485 vertex_descriptor vertex_source, vertex_target; 486 bool is_forward = ((edge_index / (num_edges(dimension_index) / 2)) == 0); 487 488 if (wrapped(dimension_index)) { 489 vertex_source = vertex_at(edge_index % num_vertices()); 490 vertex_target = is_forward ? 491 next(vertex_source, dimension_index) : 492 previous(vertex_source, dimension_index); 493 } 494 else { 495 496 // Dimensions can wrap arbitrarily, so an index needs to be 497 // computed in a more complex manner. This is done by 498 // grouping the edges for each dimension together into "bins" 499 // and considering [edge_index] as an offset into the bin. 500 // Each bin consists of two parts: the "forward" looking edges 501 // and the "backward" looking edges for the dimension. 502 503 edges_size_type vertex_offset = edge_index % num_edges(dimension_index); 504 505 // Consider vertex_offset an index into the graph's vertex 506 // space but with the dimension [dimension_index] reduced in 507 // size by one. 508 vertices_size_type index_divider = 1; 509 510 for (std::size_t dimension_index_iter = 0; 511 dimension_index_iter < Dimensions; 512 ++dimension_index_iter) { 513 514 std::size_t dimension_length = (dimension_index_iter == dimension_index) ? 515 length(dimension_index_iter) - 1 : 516 length(dimension_index_iter); 517 518 vertex_source[dimension_index_iter] = (vertex_offset / index_divider) % 519 dimension_length; 520 521 index_divider *= dimension_length; 522 } 523 524 if (is_forward) { 525 vertex_target = next(vertex_source, dimension_index); 526 } 527 else { 528 // Shift forward one more unit in the dimension for backward 529 // edges since the algorithm above will leave us one behind. 530 vertex_target = vertex_source; 531 ++vertex_source[dimension_index]; 532 } 533 534 } // if (wrapped(dimension_index)) 535 536 return (std::make_pair(vertex_source, vertex_target)); 537 } 538 539 // Returns the index for [edge] (See also edge_at) index_of(edge_descriptor edge) const540 edges_size_type index_of(edge_descriptor edge) const { 541 vertex_descriptor source_vertex = source(edge, *this); 542 vertex_descriptor target_vertex = target(edge, *this); 543 544 BOOST_ASSERT (source_vertex != target_vertex); 545 546 // Determine the dimension where the source and target vertices 547 // differ (should only be one if this is a valid edge). 548 std::size_t different_dimension_index = 0; 549 550 while (source_vertex[different_dimension_index] == 551 target_vertex[different_dimension_index]) { 552 553 ++different_dimension_index; 554 } 555 556 edges_size_type edge_index = 0; 557 558 // Offset the edge index into the appropriate "bin" (see edge_at 559 // for a more in-depth description). 560 for (std::size_t dimension_index = 0; 561 dimension_index < different_dimension_index; 562 ++dimension_index) { 563 564 edge_index += num_edges(dimension_index); 565 } 566 567 // Get the position of both vertices in the differing dimension. 568 vertices_size_type source_position = source_vertex[different_dimension_index]; 569 vertices_size_type target_position = target_vertex[different_dimension_index]; 570 571 // Determine if edge is forward or backward 572 bool is_forward = true; 573 574 if (wrapped(different_dimension_index)) { 575 576 // If the dimension is wrapped, an edge is going backward if 577 // either A: its target precedes the source in the differing 578 // dimension and the vertices are adjacent or B: its source 579 // precedes the target and they're not adjacent. 580 if (((target_position < source_position) && 581 ((source_position - target_position) == 1)) || 582 ((source_position < target_position) && 583 ((target_position - source_position) > 1))) { 584 585 is_forward = false; 586 } 587 } 588 else if (target_position < source_position) { 589 is_forward = false; 590 } 591 592 // "Backward" edges are in the second half of the bin. 593 if (!is_forward) { 594 edge_index += (num_edges(different_dimension_index) / 2); 595 } 596 597 // Finally, apply the vertex offset 598 if (wrapped(different_dimension_index)) { 599 edge_index += index_of(source_vertex); 600 } 601 else { 602 vertices_size_type index_multiplier = 1; 603 604 if (!is_forward) { 605 --source_vertex[different_dimension_index]; 606 } 607 608 for (std::size_t dimension_index = 0; 609 dimension_index < Dimensions; 610 ++dimension_index) { 611 612 edge_index += (source_vertex[dimension_index] * index_multiplier); 613 index_multiplier *= (dimension_index == different_dimension_index) ? 614 length(dimension_index) - 1 : 615 length(dimension_index); 616 } 617 } 618 619 return (edge_index); 620 } 621 622 // Returns the number of out-edges for [vertex] out_degree(vertex_descriptor vertex) const623 degree_size_type out_degree(vertex_descriptor vertex) const { 624 625 degree_size_type out_edge_count = 0; 626 627 for (std::size_t dimension_index = 0; 628 dimension_index < Dimensions; 629 ++dimension_index) { 630 631 // If the vertex is on the edge of this dimension, then its 632 // number of out edges is dependent upon whether the dimension 633 // wraps or not. 634 if ((vertex[dimension_index] == 0) || 635 (vertex[dimension_index] == (length(dimension_index) - 1))) { 636 out_edge_count += (wrapped(dimension_index) ? 2 : 1); 637 } 638 else { 639 // Next and previous edges, regardless or wrapping 640 out_edge_count += 2; 641 } 642 } 643 644 return (out_edge_count); 645 } 646 647 // Returns an out-edge for [vertex] by index. Indices are in the 648 // range [0, out_degree(vertex)). out_edge_at(vertex_descriptor vertex,degree_size_type out_edge_index) const649 edge_descriptor out_edge_at 650 (vertex_descriptor vertex, 651 degree_size_type out_edge_index) const { 652 653 edges_size_type edges_left = out_edge_index + 1; 654 std::size_t dimension_index = 0; 655 bool is_forward = false; 656 657 // Walks the out edges of [vertex] and accommodates for dimension 658 // wrapping. 659 while (edges_left > 0) { 660 661 if (!wrapped(dimension_index)) { 662 if (!is_forward && (vertex[dimension_index] == 0)) { 663 is_forward = true; 664 continue; 665 } 666 else if (is_forward && 667 (vertex[dimension_index] == (length(dimension_index) - 1))) { 668 is_forward = false; 669 ++dimension_index; 670 continue; 671 } 672 } 673 674 --edges_left; 675 676 if (edges_left > 0) { 677 is_forward = !is_forward; 678 679 if (!is_forward) { 680 ++dimension_index; 681 } 682 } 683 } 684 685 return (std::make_pair(vertex, is_forward ? 686 next(vertex, dimension_index) : 687 previous(vertex, dimension_index))); 688 } 689 690 // Returns the number of in-edges for [vertex] in_degree(vertex_descriptor vertex) const691 inline degree_size_type in_degree(vertex_descriptor vertex) const { 692 return (out_degree(vertex)); 693 } 694 695 // Returns an in-edge for [vertex] by index. Indices are in the 696 // range [0, in_degree(vertex)). in_edge_at(vertex_descriptor vertex,edges_size_type in_edge_index) const697 edge_descriptor in_edge_at 698 (vertex_descriptor vertex, 699 edges_size_type in_edge_index) const { 700 701 edge_descriptor out_edge = out_edge_at(vertex, in_edge_index); 702 return (std::make_pair(target(out_edge, *this), source(out_edge, *this))); 703 704 } 705 706 // Pre-computes the number of vertices and edges precalculate()707 void precalculate() { 708 m_num_vertices = 709 std::accumulate(m_dimension_lengths.begin(), 710 m_dimension_lengths.end(), 711 vertices_size_type(1), 712 std::multiplies<vertices_size_type>()); 713 714 // Calculate number of edges in each dimension 715 m_num_edges = 0; 716 717 for (std::size_t dimension_index = 0; 718 dimension_index < Dimensions; 719 ++dimension_index) { 720 721 if (wrapped(dimension_index)) { 722 m_edge_count[dimension_index] = num_vertices() * 2; 723 } 724 else { 725 m_edge_count[dimension_index] = 726 (num_vertices() - (num_vertices() / length(dimension_index))) * 2; 727 } 728 729 m_num_edges += num_edges(dimension_index); 730 } 731 } 732 733 const vertex_descriptor m_dimension_lengths; 734 WrapDimensionArray m_wrap_dimension; 735 vertices_size_type m_num_vertices; 736 737 boost::array<edges_size_type, Dimensions> m_edge_count; 738 edges_size_type m_num_edges; 739 740 public: 741 742 //================ 743 // VertexListGraph 744 //================ 745 746 friend inline std::pair<typename type::vertex_iterator, 747 typename type::vertex_iterator> vertices(const type & graph)748 vertices(const type& graph) { 749 typedef typename type::vertex_iterator vertex_iterator; 750 typedef typename type::vertex_function vertex_function; 751 typedef typename type::vertex_index_iterator vertex_index_iterator; 752 753 return (std::make_pair 754 (vertex_iterator(vertex_index_iterator(0), 755 vertex_function(&graph)), 756 vertex_iterator(vertex_index_iterator(graph.num_vertices()), 757 vertex_function(&graph)))); 758 } 759 760 friend inline typename type::vertices_size_type num_vertices(const type & graph)761 num_vertices(const type& graph) { 762 return (graph.num_vertices()); 763 } 764 765 friend inline typename type::vertex_descriptor vertex(typename type::vertices_size_type vertex_index,const type & graph)766 vertex(typename type::vertices_size_type vertex_index, 767 const type& graph) { 768 769 return (graph.vertex_at(vertex_index)); 770 } 771 772 //=============== 773 // IncidenceGraph 774 //=============== 775 776 friend inline std::pair<typename type::out_edge_iterator, 777 typename type::out_edge_iterator> out_edges(typename type::vertex_descriptor vertex,const type & graph)778 out_edges(typename type::vertex_descriptor vertex, 779 const type& graph) { 780 typedef typename type::degree_iterator degree_iterator; 781 typedef typename type::out_edge_function out_edge_function; 782 typedef typename type::out_edge_iterator out_edge_iterator; 783 784 return (std::make_pair 785 (out_edge_iterator(degree_iterator(0), 786 out_edge_function(vertex, &graph)), 787 out_edge_iterator(degree_iterator(graph.out_degree(vertex)), 788 out_edge_function(vertex, &graph)))); 789 } 790 791 friend inline typename type::degree_size_type out_degree(typename type::vertex_descriptor vertex,const type & graph)792 out_degree 793 (typename type::vertex_descriptor vertex, 794 const type& graph) { 795 return (graph.out_degree(vertex)); 796 } 797 798 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)799 out_edge_at(typename type::vertex_descriptor vertex, 800 typename type::degree_size_type out_edge_index, 801 const type& graph) { 802 return (graph.out_edge_at(vertex, out_edge_index)); 803 } 804 805 //=============== 806 // AdjacencyGraph 807 //=============== 808 809 friend typename std::pair<typename type::adjacency_iterator, 810 typename type::adjacency_iterator> adjacent_vertices(typename type::vertex_descriptor vertex,const type & graph)811 adjacent_vertices (typename type::vertex_descriptor vertex, 812 const type& graph) { 813 typedef typename type::degree_iterator degree_iterator; 814 typedef typename type::adjacent_vertex_function adjacent_vertex_function; 815 typedef typename type::adjacency_iterator adjacency_iterator; 816 817 return (std::make_pair 818 (adjacency_iterator(degree_iterator(0), 819 adjacent_vertex_function(vertex, &graph)), 820 adjacency_iterator(degree_iterator(graph.out_degree(vertex)), 821 adjacent_vertex_function(vertex, &graph)))); 822 } 823 824 //============== 825 // EdgeListGraph 826 //============== 827 828 friend inline typename type::edges_size_type num_edges(const type & graph)829 num_edges(const type& graph) { 830 return (graph.num_edges()); 831 } 832 833 friend inline typename type::edge_descriptor edge_at(typename type::edges_size_type edge_index,const type & graph)834 edge_at(typename type::edges_size_type edge_index, 835 const type& graph) { 836 return (graph.edge_at(edge_index)); 837 } 838 839 friend inline std::pair<typename type::edge_iterator, 840 typename type::edge_iterator> edges(const type & graph)841 edges(const type& graph) { 842 typedef typename type::edge_index_iterator edge_index_iterator; 843 typedef typename type::edge_function edge_function; 844 typedef typename type::edge_iterator edge_iterator; 845 846 return (std::make_pair 847 (edge_iterator(edge_index_iterator(0), 848 edge_function(&graph)), 849 edge_iterator(edge_index_iterator(graph.num_edges()), 850 edge_function(&graph)))); 851 } 852 853 //=================== 854 // BiDirectionalGraph 855 //=================== 856 857 friend inline std::pair<typename type::in_edge_iterator, 858 typename type::in_edge_iterator> in_edges(typename type::vertex_descriptor vertex,const type & graph)859 in_edges(typename type::vertex_descriptor vertex, 860 const type& graph) { 861 typedef typename type::in_edge_function in_edge_function; 862 typedef typename type::degree_iterator degree_iterator; 863 typedef typename type::in_edge_iterator in_edge_iterator; 864 865 return (std::make_pair 866 (in_edge_iterator(degree_iterator(0), 867 in_edge_function(vertex, &graph)), 868 in_edge_iterator(degree_iterator(graph.in_degree(vertex)), 869 in_edge_function(vertex, &graph)))); 870 } 871 872 friend inline typename type::degree_size_type in_degree(typename type::vertex_descriptor vertex,const type & graph)873 in_degree (typename type::vertex_descriptor vertex, 874 const type& graph) { 875 return (graph.in_degree(vertex)); 876 } 877 878 friend inline typename type::degree_size_type degree(typename type::vertex_descriptor vertex,const type & graph)879 degree (typename type::vertex_descriptor vertex, 880 const type& graph) { 881 return (graph.out_degree(vertex) * 2); 882 } 883 884 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)885 in_edge_at(typename type::vertex_descriptor vertex, 886 typename type::degree_size_type in_edge_index, 887 const type& graph) { 888 return (graph.in_edge_at(vertex, in_edge_index)); 889 } 890 891 892 //================== 893 // Adjacency Matrix 894 //================== 895 896 friend std::pair<typename type::edge_descriptor, bool> edge(typename type::vertex_descriptor source_vertex,typename type::vertex_descriptor destination_vertex,const type & graph)897 edge (typename type::vertex_descriptor source_vertex, 898 typename type::vertex_descriptor destination_vertex, 899 const type& graph) { 900 901 std::pair<typename type::edge_descriptor, bool> edge_exists = 902 std::make_pair(std::make_pair(source_vertex, destination_vertex), false); 903 904 for (std::size_t dimension_index = 0; 905 dimension_index < Dimensions; 906 ++dimension_index) { 907 908 typename type::vertices_size_type dim_difference = 0; 909 typename type::vertices_size_type 910 source_dim = source_vertex[dimension_index], 911 dest_dim = destination_vertex[dimension_index]; 912 913 dim_difference = (source_dim > dest_dim) ? 914 (source_dim - dest_dim) : (dest_dim - source_dim); 915 916 if (dim_difference > 0) { 917 918 // If we've already found a valid edge, this would mean that 919 // the vertices are really diagonal across dimensions and 920 // therefore not connected. 921 if (edge_exists.second) { 922 edge_exists.second = false; 923 break; 924 } 925 926 // If the difference is one, the vertices are right next to 927 // each other and the edge is valid. The edge is still 928 // valid, though, if the dimension wraps and the vertices 929 // are on opposite ends. 930 if ((dim_difference == 1) || 931 (graph.wrapped(dimension_index) && 932 (((source_dim == 0) && (dest_dim == (graph.length(dimension_index) - 1))) || 933 ((dest_dim == 0) && (source_dim == (graph.length(dimension_index) - 1)))))) { 934 935 edge_exists.second = true; 936 // Stay in the loop to check for diagonal vertices. 937 } 938 else { 939 940 // Stop checking - the vertices are too far apart. 941 edge_exists.second = false; 942 break; 943 } 944 } 945 946 } // for dimension_index 947 948 return (edge_exists); 949 } 950 951 952 //============================= 953 // Index Property Map Functions 954 //============================= 955 956 friend inline typename type::vertices_size_type get(vertex_index_t,const type & graph,typename type::vertex_descriptor vertex)957 get(vertex_index_t, 958 const type& graph, 959 typename type::vertex_descriptor vertex) { 960 return (graph.index_of(vertex)); 961 } 962 963 friend inline typename type::edges_size_type get(edge_index_t,const type & graph,typename type::edge_descriptor edge)964 get(edge_index_t, 965 const type& graph, 966 typename type::edge_descriptor edge) { 967 return (graph.index_of(edge)); 968 } 969 970 friend inline grid_graph_index_map< 971 type, 972 typename type::vertex_descriptor, 973 typename type::vertices_size_type> get(vertex_index_t,const type & graph)974 get(vertex_index_t, const type& graph) { 975 return (grid_graph_index_map< 976 type, 977 typename type::vertex_descriptor, 978 typename type::vertices_size_type>(graph)); 979 } 980 981 friend inline grid_graph_index_map< 982 type, 983 typename type::edge_descriptor, 984 typename type::edges_size_type> get(edge_index_t,const type & graph)985 get(edge_index_t, const type& graph) { 986 return (grid_graph_index_map< 987 type, 988 typename type::edge_descriptor, 989 typename type::edges_size_type>(graph)); 990 } 991 992 friend inline grid_graph_reverse_edge_map< 993 typename type::edge_descriptor> get(edge_reverse_t,const type & graph)994 get(edge_reverse_t, const type& graph) { 995 return (grid_graph_reverse_edge_map< 996 typename type::edge_descriptor>()); 997 } 998 999 template<typename Graph, 1000 typename Descriptor, 1001 typename Index> 1002 friend struct grid_graph_index_map; 1003 1004 template<typename Descriptor> 1005 friend struct grid_graph_reverse_edge_map; 1006 1007 }; // grid_graph 1008 1009 } // namespace boost 1010 1011 #undef BOOST_GRID_GRAPH_TYPE 1012 #undef BOOST_GRID_GRAPH_TEMPLATE_PARAMS 1013 #undef BOOST_GRID_GRAPH_TRAITS_T 1014 1015 #endif // BOOST_GRAPH_GRID_GRAPH_HPP 1016