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