1 //======================================================================= 2 // Copyright 2001 University of Notre Dame. 3 // Copyright 2006 Trustees of Indiana University 4 // Authors: Jeremy G. Siek and Douglas Gregor <dgregor@cs.indiana.edu> 5 // 6 // Distributed under the Boost Software License, Version 1.0. (See 7 // accompanying file LICENSE_1_0.txt or copy at 8 // http://www.boost.org/LICENSE_1_0.txt) 9 //======================================================================= 10 11 #ifndef BOOST_ADJACENCY_MATRIX_HPP 12 #define BOOST_ADJACENCY_MATRIX_HPP 13 14 #include <boost/config.hpp> 15 #include <vector> 16 #include <memory> 17 #include <iterator> 18 #include <boost/assert.hpp> 19 #include <boost/limits.hpp> 20 #include <boost/graph/graph_traits.hpp> 21 #include <boost/graph/graph_mutability_traits.hpp> 22 #include <boost/graph/graph_selectors.hpp> 23 #include <boost/mpl/if.hpp> 24 #include <boost/mpl/bool.hpp> 25 #include <boost/graph/adjacency_iterator.hpp> 26 #include <boost/graph/detail/edge.hpp> 27 #include <boost/iterator/iterator_adaptor.hpp> 28 #include <boost/iterator/filter_iterator.hpp> 29 #include <boost/range/irange.hpp> 30 #include <boost/graph/properties.hpp> 31 #include <boost/tuple/tuple.hpp> 32 #include <boost/static_assert.hpp> 33 #include <boost/type_traits.hpp> 34 #include <boost/property_map/property_map.hpp> 35 #include <boost/property_map/transform_value_property_map.hpp> 36 #include <boost/property_map/function_property_map.hpp> 37 38 namespace boost { 39 40 namespace detail { 41 42 template <class Directed, class Vertex> 43 class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex> 44 { 45 typedef edge_desc_impl<Directed,Vertex> Base; 46 public: matrix_edge_desc_impl()47 matrix_edge_desc_impl() { } matrix_edge_desc_impl(bool exists,Vertex s,Vertex d,const void * ep=0)48 matrix_edge_desc_impl(bool exists, Vertex s, Vertex d, 49 const void* ep = 0) 50 : Base(s, d, ep), m_exists(exists) { } exists() const51 bool exists() const { return m_exists; } 52 private: 53 bool m_exists; 54 }; 55 56 struct does_edge_exist { 57 template <class Edge> operator ()boost::detail::does_edge_exist58 bool operator()(const Edge& e) const { return e.exists(); } 59 }; 60 61 // Note to self... The int for get_edge_exists and set_edge exist helps 62 // make these calls unambiguous. 63 template <typename EdgeProperty> get_edge_exists(const std::pair<bool,EdgeProperty> & stored_edge,int)64 bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) { 65 return stored_edge.first; 66 } 67 template <typename EdgeProperty> set_edge_exists(std::pair<bool,EdgeProperty> & stored_edge,bool flag,int)68 void set_edge_exists( 69 std::pair<bool, EdgeProperty>& stored_edge, 70 bool flag, 71 int 72 ) { 73 stored_edge.first = flag; 74 } 75 76 template <typename EdgeProxy> get_edge_exists(const EdgeProxy & edge_proxy,...)77 bool get_edge_exists(const EdgeProxy& edge_proxy, ...) { 78 return edge_proxy; 79 } 80 template <typename EdgeProxy> set_edge_exists(EdgeProxy & edge_proxy,bool flag,...)81 EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) { 82 edge_proxy = flag; 83 return edge_proxy; // just to avoid never used warning 84 } 85 86 87 // NOTE: These functions collide with the get_property function for 88 // accessing bundled graph properties. Be excplicit when using them. 89 template <typename EdgeProperty> 90 const EdgeProperty& get_edge_property(const std::pair<bool,EdgeProperty> & stored_edge)91 get_edge_property(const std::pair<bool, EdgeProperty>& stored_edge) { 92 return stored_edge.second; 93 } 94 template <typename EdgeProperty> 95 EdgeProperty& get_edge_property(std::pair<bool,EdgeProperty> & stored_edge)96 get_edge_property(std::pair<bool, EdgeProperty>& stored_edge) { 97 return stored_edge.second; 98 } 99 100 template <typename StoredEdgeProperty, typename EdgeProperty> 101 inline void set_edge_property(std::pair<bool,StoredEdgeProperty> & stored_edge,const EdgeProperty & ep,int)102 set_edge_property(std::pair<bool, StoredEdgeProperty>& stored_edge, 103 const EdgeProperty& ep, int) { 104 stored_edge.second = ep; 105 } 106 get_edge_property(const char &)107 inline const no_property& get_edge_property(const char&) { 108 static no_property s_prop; 109 return s_prop; 110 } get_edge_property(char &)111 inline no_property& get_edge_property(char&) { 112 static no_property s_prop; 113 return s_prop; 114 } 115 template <typename EdgeProxy, typename EdgeProperty> set_edge_property(EdgeProxy,const EdgeProperty &,...)116 inline void set_edge_property(EdgeProxy, const EdgeProperty&, ...) {} 117 118 //======================================================================= 119 // Directed Out Edge Iterator 120 121 template < 122 typename VertexDescriptor, typename MatrixIter 123 , typename VerticesSizeType, typename EdgeDescriptor 124 > 125 struct dir_adj_matrix_out_edge_iter 126 : iterator_adaptor< 127 dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> 128 , MatrixIter 129 , EdgeDescriptor 130 , use_default 131 , EdgeDescriptor 132 , std::ptrdiff_t 133 > 134 { 135 typedef iterator_adaptor< 136 dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> 137 , MatrixIter 138 , EdgeDescriptor 139 , use_default 140 , EdgeDescriptor 141 , std::ptrdiff_t 142 > super_t; 143 dir_adj_matrix_out_edge_iterboost::detail::dir_adj_matrix_out_edge_iter144 dir_adj_matrix_out_edge_iter() { } 145 dir_adj_matrix_out_edge_iterboost::detail::dir_adj_matrix_out_edge_iter146 dir_adj_matrix_out_edge_iter( 147 const MatrixIter& i 148 , const VertexDescriptor& src 149 , const VerticesSizeType& n 150 ) 151 : super_t(i), m_src(src), m_targ(0), m_n(n) 152 { } 153 incrementboost::detail::dir_adj_matrix_out_edge_iter154 void increment() { 155 ++this->base_reference(); 156 ++m_targ; 157 } 158 159 inline EdgeDescriptor dereferenceboost::detail::dir_adj_matrix_out_edge_iter160 dereference() const 161 { 162 return EdgeDescriptor(get_edge_exists(*this->base(), 0), 163 m_src, m_targ, 164 &get_edge_property(*this->base())); 165 } 166 VertexDescriptor m_src, m_targ; 167 VerticesSizeType m_n; 168 }; 169 170 //======================================================================= 171 // Directed In Edge Iterator 172 173 template < 174 typename VertexDescriptor, typename MatrixIter 175 , typename VerticesSizeType, typename EdgeDescriptor 176 > 177 struct dir_adj_matrix_in_edge_iter 178 : iterator_adaptor< 179 dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> 180 , MatrixIter 181 , EdgeDescriptor 182 , use_default 183 , EdgeDescriptor 184 , std::ptrdiff_t 185 > 186 { 187 typedef iterator_adaptor< 188 dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> 189 , MatrixIter 190 , EdgeDescriptor 191 , use_default 192 , EdgeDescriptor 193 , std::ptrdiff_t 194 > super_t; 195 dir_adj_matrix_in_edge_iterboost::detail::dir_adj_matrix_in_edge_iter196 dir_adj_matrix_in_edge_iter() { } 197 dir_adj_matrix_in_edge_iterboost::detail::dir_adj_matrix_in_edge_iter198 dir_adj_matrix_in_edge_iter( 199 const MatrixIter& i 200 , const MatrixIter& last 201 , const VertexDescriptor& tgt 202 , const VerticesSizeType& n 203 ) 204 : super_t(i), m_last(last), m_src(0), m_targ(tgt), m_n(n) 205 { } 206 incrementboost::detail::dir_adj_matrix_in_edge_iter207 void increment() { 208 if (VerticesSizeType(m_last - this->base_reference()) >= m_n) { 209 this->base_reference() += m_n; 210 ++m_src; 211 } else { 212 this->base_reference() = m_last; 213 } 214 } 215 216 inline EdgeDescriptor dereferenceboost::detail::dir_adj_matrix_in_edge_iter217 dereference() const 218 { 219 return EdgeDescriptor(get_edge_exists(*this->base(), 0), 220 m_src, m_targ, 221 &get_edge_property(*this->base())); 222 } 223 MatrixIter m_last; 224 VertexDescriptor m_src, m_targ; 225 VerticesSizeType m_n; 226 }; 227 228 //======================================================================= 229 // Undirected Out Edge Iterator 230 231 template < 232 typename VertexDescriptor, typename MatrixIter 233 , typename VerticesSizeType, typename EdgeDescriptor 234 > 235 struct undir_adj_matrix_out_edge_iter 236 : iterator_adaptor< 237 undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> 238 , MatrixIter 239 , EdgeDescriptor 240 , use_default 241 , EdgeDescriptor 242 , std::ptrdiff_t 243 > 244 { 245 typedef iterator_adaptor< 246 undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> 247 , MatrixIter 248 , EdgeDescriptor 249 , use_default 250 , EdgeDescriptor 251 , std::ptrdiff_t 252 > super_t; 253 undir_adj_matrix_out_edge_iterboost::detail::undir_adj_matrix_out_edge_iter254 undir_adj_matrix_out_edge_iter() { } 255 undir_adj_matrix_out_edge_iterboost::detail::undir_adj_matrix_out_edge_iter256 undir_adj_matrix_out_edge_iter( 257 const MatrixIter& i 258 , const VertexDescriptor& src 259 , const VerticesSizeType& n 260 ) 261 : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n) 262 {} 263 incrementboost::detail::undir_adj_matrix_out_edge_iter264 void increment() 265 { 266 if (m_targ < m_src) // first half 267 { 268 ++this->base_reference(); 269 } 270 else if (m_targ < m_n - 1) 271 { // second half 272 ++m_inc; 273 this->base_reference() += m_inc; 274 } 275 else 276 { // past-the-end 277 this->base_reference() += m_n - m_src; 278 } 279 ++m_targ; 280 } 281 282 inline EdgeDescriptor dereferenceboost::detail::undir_adj_matrix_out_edge_iter283 dereference() const 284 { 285 return EdgeDescriptor(get_edge_exists(*this->base(), 0), 286 m_src, m_targ, 287 &get_edge_property(*this->base())); 288 } 289 290 VertexDescriptor m_src, m_inc, m_targ; 291 VerticesSizeType m_n; 292 }; 293 294 //======================================================================= 295 // Undirected In Edge Iterator 296 297 template < 298 typename VertexDescriptor, typename MatrixIter 299 , typename VerticesSizeType, typename EdgeDescriptor 300 > 301 struct undir_adj_matrix_in_edge_iter 302 : iterator_adaptor< 303 undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> 304 , MatrixIter 305 , EdgeDescriptor 306 , use_default 307 , EdgeDescriptor 308 , std::ptrdiff_t 309 > 310 { 311 typedef iterator_adaptor< 312 undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> 313 , MatrixIter 314 , EdgeDescriptor 315 , use_default 316 , EdgeDescriptor 317 , std::ptrdiff_t 318 > super_t; 319 undir_adj_matrix_in_edge_iterboost::detail::undir_adj_matrix_in_edge_iter320 undir_adj_matrix_in_edge_iter() { } 321 undir_adj_matrix_in_edge_iterboost::detail::undir_adj_matrix_in_edge_iter322 undir_adj_matrix_in_edge_iter( 323 const MatrixIter& i 324 , const VertexDescriptor& src 325 , const VerticesSizeType& n 326 ) 327 : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n) 328 {} 329 incrementboost::detail::undir_adj_matrix_in_edge_iter330 void increment() 331 { 332 if (m_targ < m_src) // first half 333 { 334 ++this->base_reference(); 335 } 336 else if (m_targ < m_n - 1) 337 { // second half 338 ++m_inc; 339 this->base_reference() += m_inc; 340 } 341 else 342 { // past-the-end 343 this->base_reference() += m_n - m_src; 344 } 345 ++m_targ; 346 } 347 348 inline EdgeDescriptor dereferenceboost::detail::undir_adj_matrix_in_edge_iter349 dereference() const 350 { 351 return EdgeDescriptor(get_edge_exists(*this->base(), 0), 352 m_targ, m_src, 353 &get_edge_property(*this->base())); 354 } 355 356 VertexDescriptor m_src, m_inc, m_targ; 357 VerticesSizeType m_n; 358 }; 359 360 //======================================================================= 361 // Edge Iterator 362 363 template <typename Directed, typename MatrixIter, 364 typename VerticesSizeType, typename EdgeDescriptor> 365 struct adj_matrix_edge_iter 366 : iterator_adaptor< 367 adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor> 368 , MatrixIter 369 , EdgeDescriptor 370 , use_default 371 , EdgeDescriptor 372 , std::ptrdiff_t 373 > 374 { 375 typedef iterator_adaptor< 376 adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor> 377 , MatrixIter 378 , EdgeDescriptor 379 , use_default 380 , EdgeDescriptor 381 , std::ptrdiff_t 382 > super_t; 383 adj_matrix_edge_iterboost::detail::adj_matrix_edge_iter384 adj_matrix_edge_iter() { } 385 adj_matrix_edge_iterboost::detail::adj_matrix_edge_iter386 adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n) 387 : super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { } 388 incrementboost::detail::adj_matrix_edge_iter389 void increment() 390 { 391 increment_dispatch(this->base_reference(), Directed()); 392 } 393 increment_dispatchboost::detail::adj_matrix_edge_iter394 void increment_dispatch(MatrixIter& i, directedS) 395 { 396 ++i; 397 if (m_targ == m_n - 1) 398 { 399 m_targ = 0; 400 ++m_src; 401 } 402 else 403 { 404 ++m_targ; 405 } 406 } 407 increment_dispatchboost::detail::adj_matrix_edge_iter408 void increment_dispatch(MatrixIter& i, undirectedS) 409 { 410 ++i; 411 if (m_targ == m_src) 412 { 413 m_targ = 0; 414 ++m_src; 415 } 416 else 417 { 418 ++m_targ; 419 } 420 } 421 422 inline EdgeDescriptor dereferenceboost::detail::adj_matrix_edge_iter423 dereference() const 424 { 425 return EdgeDescriptor(get_edge_exists(*this->base(), 0), 426 m_src, m_targ, 427 &get_edge_property(*this->base())); 428 } 429 430 MatrixIter m_start; 431 VerticesSizeType m_src, m_targ, m_n; 432 }; 433 434 } // namespace detail 435 436 //========================================================================= 437 // Adjacency Matrix Traits 438 template <typename Directed = directedS> 439 class adjacency_matrix_traits { 440 typedef typename Directed::is_directed_t is_directed; 441 public: 442 // The bidirectionalS tag is not allowed with the adjacency_matrix 443 // graph type. Instead, use directedS, which also provides the 444 // functionality required for a Bidirectional Graph (in_edges, 445 // in_degree, etc.). 446 BOOST_STATIC_ASSERT(!(is_same<Directed, bidirectionalS>::value)); 447 448 typedef typename mpl::if_<is_directed, 449 bidirectional_tag, undirected_tag>::type 450 directed_category; 451 452 typedef disallow_parallel_edge_tag edge_parallel_category; 453 454 typedef std::size_t vertex_descriptor; 455 456 typedef detail::matrix_edge_desc_impl<directed_category, 457 vertex_descriptor> edge_descriptor; 458 }; 459 460 struct adjacency_matrix_class_tag { }; 461 462 struct adj_matrix_traversal_tag : 463 public virtual adjacency_matrix_tag, 464 public virtual vertex_list_graph_tag, 465 public virtual incidence_graph_tag, 466 public virtual adjacency_graph_tag, 467 public virtual edge_list_graph_tag { }; 468 469 //========================================================================= 470 // Adjacency Matrix Class 471 template <typename Directed = directedS, 472 typename VertexProperty = no_property, 473 typename EdgeProperty = no_property, 474 typename GraphProperty = no_property, 475 typename Allocator = std::allocator<bool> > 476 class adjacency_matrix { 477 typedef adjacency_matrix self; 478 typedef adjacency_matrix_traits<Directed> Traits; 479 480 public: 481 // The bidirectionalS tag is not allowed with the adjacency_matrix 482 // graph type. Instead, use directedS, which also provides the 483 // functionality required for a Bidirectional Graph (in_edges, 484 // in_degree, etc.). 485 BOOST_STATIC_ASSERT(!(is_same<Directed, bidirectionalS>::value)); 486 487 typedef GraphProperty graph_property_type; 488 typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled; 489 490 typedef VertexProperty vertex_property_type; 491 typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type vertex_bundled; 492 493 typedef EdgeProperty edge_property_type; 494 typedef typename lookup_one_property<EdgeProperty, edge_bundle_t>::type edge_bundled; 495 496 public: // should be private 497 typedef typename mpl::if_<typename has_property<edge_property_type>::type, 498 std::pair<bool, edge_property_type>, char>::type StoredEdge; 499 #if defined(BOOST_NO_STD_ALLOCATOR) 500 typedef std::vector<StoredEdge> Matrix; 501 #else 502 #if defined(BOOST_NO_CXX11_ALLOCATOR) 503 typedef typename Allocator::template rebind<StoredEdge>::other Alloc; 504 #else 505 typedef typename std::allocator_traits<Allocator>::template rebind_alloc<StoredEdge> Alloc; 506 #endif 507 typedef std::vector<StoredEdge, Alloc> Matrix; 508 #endif 509 typedef typename Matrix::iterator MatrixIter; 510 typedef typename Matrix::size_type size_type; 511 public: 512 // Graph concept required types 513 typedef typename Traits::vertex_descriptor vertex_descriptor; 514 typedef typename Traits::edge_descriptor edge_descriptor; 515 typedef typename Traits::directed_category directed_category; 516 typedef typename Traits::edge_parallel_category edge_parallel_category; 517 typedef adj_matrix_traversal_tag traversal_category; 518 null_vertex()519 static vertex_descriptor null_vertex() 520 { 521 return (std::numeric_limits<vertex_descriptor>::max)(); 522 } 523 524 //private: if friends worked, these would be private 525 526 typedef detail::dir_adj_matrix_out_edge_iter< 527 vertex_descriptor, MatrixIter, size_type, edge_descriptor 528 > DirOutEdgeIter; 529 530 typedef detail::undir_adj_matrix_out_edge_iter< 531 vertex_descriptor, MatrixIter, size_type, edge_descriptor 532 > UnDirOutEdgeIter; 533 534 typedef typename mpl::if_< 535 typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter 536 >::type unfiltered_out_edge_iter; 537 538 typedef detail::dir_adj_matrix_in_edge_iter< 539 vertex_descriptor, MatrixIter, size_type, edge_descriptor 540 > DirInEdgeIter; 541 542 typedef detail::undir_adj_matrix_in_edge_iter< 543 vertex_descriptor, MatrixIter, size_type, edge_descriptor 544 > UnDirInEdgeIter; 545 546 typedef typename mpl::if_< 547 typename Directed::is_directed_t, DirInEdgeIter, UnDirInEdgeIter 548 >::type unfiltered_in_edge_iter; 549 550 typedef detail::adj_matrix_edge_iter< 551 Directed, MatrixIter, size_type, edge_descriptor 552 > unfiltered_edge_iter; 553 554 public: 555 556 // IncidenceGraph concept required types 557 typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter> 558 out_edge_iterator; 559 560 typedef size_type degree_size_type; 561 562 // BidirectionalGraph required types 563 typedef filter_iterator<detail::does_edge_exist, unfiltered_in_edge_iter> 564 in_edge_iterator; 565 566 // AdjacencyGraph required types 567 typedef typename adjacency_iterator_generator<self, 568 vertex_descriptor, out_edge_iterator>::type adjacency_iterator; 569 570 // VertexListGraph required types 571 typedef size_type vertices_size_type; 572 typedef integer_range<vertex_descriptor> VertexList; 573 typedef typename VertexList::iterator vertex_iterator; 574 575 // EdgeListGraph required types 576 typedef size_type edges_size_type; 577 typedef filter_iterator< 578 detail::does_edge_exist, unfiltered_edge_iter 579 > edge_iterator; 580 581 // PropertyGraph required types 582 typedef adjacency_matrix_class_tag graph_tag; 583 584 // Constructor required by MutableGraph adjacency_matrix(vertices_size_type n_vertices,const GraphProperty & p=GraphProperty ())585 adjacency_matrix(vertices_size_type n_vertices, 586 const GraphProperty& p = GraphProperty()) 587 : m_matrix(Directed::is_directed ? 588 (n_vertices * n_vertices) 589 : (n_vertices * (n_vertices + 1) / 2)), 590 m_vertex_set(0, n_vertices), 591 m_vertex_properties(n_vertices), 592 m_num_edges(0), 593 m_property(p) { } 594 595 template <typename EdgeIterator> adjacency_matrix(EdgeIterator first,EdgeIterator last,vertices_size_type n_vertices,const GraphProperty & p=GraphProperty ())596 adjacency_matrix(EdgeIterator first, 597 EdgeIterator last, 598 vertices_size_type n_vertices, 599 const GraphProperty& p = GraphProperty()) 600 : m_matrix(Directed::is_directed ? 601 (n_vertices * n_vertices) 602 : (n_vertices * (n_vertices + 1) / 2)), 603 m_vertex_set(0, n_vertices), 604 m_vertex_properties(n_vertices), 605 m_num_edges(0), 606 m_property(p) 607 { 608 for (; first != last; ++first) { 609 add_edge(first->first, first->second, *this); 610 } 611 } 612 613 template <typename EdgeIterator, typename EdgePropertyIterator> adjacency_matrix(EdgeIterator first,EdgeIterator last,EdgePropertyIterator ep_iter,vertices_size_type n_vertices,const GraphProperty & p=GraphProperty ())614 adjacency_matrix(EdgeIterator first, 615 EdgeIterator last, 616 EdgePropertyIterator ep_iter, 617 vertices_size_type n_vertices, 618 const GraphProperty& p = GraphProperty()) 619 : m_matrix(Directed::is_directed ? 620 (n_vertices * n_vertices) 621 : (n_vertices * (n_vertices + 1) / 2)), 622 m_vertex_set(0, n_vertices), 623 m_vertex_properties(n_vertices), 624 m_num_edges(0), 625 m_property(p) 626 { 627 for (; first != last; ++first, ++ep_iter) { 628 add_edge(first->first, first->second, *ep_iter, *this); 629 } 630 } 631 632 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES 633 // Directly access a vertex or edge bundle operator [](vertex_descriptor v)634 vertex_bundled& operator[](vertex_descriptor v) 635 { return get(vertex_bundle, *this, v); } 636 operator [](vertex_descriptor v) const637 const vertex_bundled& operator[](vertex_descriptor v) const 638 { return get(vertex_bundle, *this, v); } 639 operator [](edge_descriptor e)640 edge_bundled& operator[](edge_descriptor e) 641 { return get(edge_bundle, *this, e); } 642 operator [](edge_descriptor e) const643 const edge_bundled& operator[](edge_descriptor e) const 644 { return get(edge_bundle, *this, e); } 645 operator [](graph_bundle_t)646 graph_bundled& operator[](graph_bundle_t) 647 { return get_property(*this); } 648 operator [](graph_bundle_t) const649 const graph_bundled& operator[](graph_bundle_t) const 650 { return get_property(*this); } 651 #endif 652 653 //private: if friends worked, these would be private 654 655 typename Matrix::const_reference get_edge(vertex_descriptor u,vertex_descriptor v) const656 get_edge(vertex_descriptor u, vertex_descriptor v) const { 657 if (Directed::is_directed) 658 return m_matrix[u * m_vertex_set.size() + v]; 659 else { 660 if (v > u) 661 std::swap(u, v); 662 return m_matrix[u * (u + 1)/2 + v]; 663 } 664 } 665 typename Matrix::reference get_edge(vertex_descriptor u,vertex_descriptor v)666 get_edge(vertex_descriptor u, vertex_descriptor v) { 667 if (Directed::is_directed) 668 return m_matrix[u * m_vertex_set.size() + v]; 669 else { 670 if (v > u) 671 std::swap(u, v); 672 return m_matrix[u * (u + 1)/2 + v]; 673 } 674 } 675 676 Matrix m_matrix; 677 VertexList m_vertex_set; 678 std::vector<vertex_property_type> m_vertex_properties; 679 size_type m_num_edges; 680 graph_property_type m_property; 681 }; 682 683 //========================================================================= 684 // Functions required by the AdjacencyMatrix concept 685 686 template <typename D, typename VP, typename EP, typename GP, typename A> 687 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, 688 bool> edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,const adjacency_matrix<D,VP,EP,GP,A> & g)689 edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 690 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, 691 const adjacency_matrix<D,VP,EP,GP,A>& g) 692 { 693 bool exists = detail::get_edge_exists(g.get_edge(u,v), 0); 694 typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor 695 e(exists, u, v, &detail::get_edge_property(g.get_edge(u,v))); 696 return std::make_pair(e, exists); 697 } 698 699 //========================================================================= 700 // Functions required by the IncidenceGraph concept 701 702 // O(1) 703 template <typename VP, typename EP, typename GP, typename A> 704 std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator, 705 typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator> out_edges(typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,const adjacency_matrix<directedS,VP,EP,GP,A> & g_)706 out_edges 707 (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, 708 const adjacency_matrix<directedS,VP,EP,GP,A>& g_) 709 { 710 typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph; 711 Graph& g = const_cast<Graph&>(g_); 712 typename Graph::vertices_size_type offset = u * g.m_vertex_set.size(); 713 typename Graph::MatrixIter f = g.m_matrix.begin() + offset; 714 typename Graph::MatrixIter l = f + g.m_vertex_set.size(); 715 typename Graph::unfiltered_out_edge_iter 716 first(f, u, g.m_vertex_set.size()) 717 , last(l, u, g.m_vertex_set.size()); 718 detail::does_edge_exist pred; 719 typedef typename Graph::out_edge_iterator out_edge_iterator; 720 return std::make_pair(out_edge_iterator(pred, first, last), 721 out_edge_iterator(pred, last, last)); 722 } 723 724 // O(1) 725 template <typename VP, typename EP, typename GP, typename A> 726 std::pair< 727 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator, 728 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator> out_edges(typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,const adjacency_matrix<undirectedS,VP,EP,GP,A> & g_)729 out_edges 730 (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, 731 const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_) 732 { 733 typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph; 734 Graph& g = const_cast<Graph&>(g_); 735 typename Graph::vertices_size_type offset = u * (u + 1) / 2; 736 typename Graph::MatrixIter f = g.m_matrix.begin() + offset; 737 typename Graph::MatrixIter l = g.m_matrix.end(); 738 739 typename Graph::unfiltered_out_edge_iter 740 first(f, u, g.m_vertex_set.size()) 741 , last(l, u, g.m_vertex_set.size()); 742 743 detail::does_edge_exist pred; 744 typedef typename Graph::out_edge_iterator out_edge_iterator; 745 return std::make_pair(out_edge_iterator(pred, first, last), 746 out_edge_iterator(pred, last, last)); 747 } 748 749 // O(N) 750 template <typename D, typename VP, typename EP, typename GP, typename A> 751 typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,const adjacency_matrix<D,VP,EP,GP,A> & g)752 out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 753 const adjacency_matrix<D,VP,EP,GP,A>& g) 754 { 755 typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0; 756 typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l; 757 for (boost::tie(f, l) = out_edges(u, g); f != l; ++f) 758 ++n; 759 return n; 760 } 761 762 // O(1) 763 template <typename D, typename VP, typename EP, typename GP, typename A, 764 typename Dir, typename Vertex> 765 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor source(const detail::matrix_edge_desc_impl<Dir,Vertex> & e,const adjacency_matrix<D,VP,EP,GP,A> &)766 source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e, 767 const adjacency_matrix<D,VP,EP,GP,A>&) 768 { 769 return e.m_source; 770 } 771 772 // O(1) 773 template <typename D, typename VP, typename EP, typename GP, typename A, 774 typename Dir, typename Vertex> 775 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor target(const detail::matrix_edge_desc_impl<Dir,Vertex> & e,const adjacency_matrix<D,VP,EP,GP,A> &)776 target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e, 777 const adjacency_matrix<D,VP,EP,GP,A>&) 778 { 779 return e.m_target; 780 } 781 782 //========================================================================= 783 // Functions required by the BidirectionalGraph concept 784 785 // O(1) 786 template <typename VP, typename EP, typename GP, typename A> 787 std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator, 788 typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator> in_edges(typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,const adjacency_matrix<directedS,VP,EP,GP,A> & g_)789 in_edges 790 (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, 791 const adjacency_matrix<directedS,VP,EP,GP,A>& g_) 792 { 793 typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph; 794 Graph& g = const_cast<Graph&>(g_); 795 typename Graph::MatrixIter f = g.m_matrix.begin() + u; 796 typename Graph::MatrixIter l = g.m_matrix.end(); 797 typename Graph::unfiltered_in_edge_iter 798 first(f, l, u, g.m_vertex_set.size()) 799 , last(l, l, u, g.m_vertex_set.size()); 800 detail::does_edge_exist pred; 801 typedef typename Graph::in_edge_iterator in_edge_iterator; 802 return std::make_pair(in_edge_iterator(pred, first, last), 803 in_edge_iterator(pred, last, last)); 804 } 805 806 // O(1) 807 template <typename VP, typename EP, typename GP, typename A> 808 std::pair< 809 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator, 810 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator> in_edges(typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,const adjacency_matrix<undirectedS,VP,EP,GP,A> & g_)811 in_edges 812 (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, 813 const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_) 814 { 815 typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph; 816 Graph& g = const_cast<Graph&>(g_); 817 typename Graph::vertices_size_type offset = u * (u + 1) / 2; 818 typename Graph::MatrixIter f = g.m_matrix.begin() + offset; 819 typename Graph::MatrixIter l = g.m_matrix.end(); 820 821 typename Graph::unfiltered_in_edge_iter 822 first(f, u, g.m_vertex_set.size()) 823 , last(l, u, g.m_vertex_set.size()); 824 825 detail::does_edge_exist pred; 826 typedef typename Graph::in_edge_iterator in_edge_iterator; 827 return std::make_pair(in_edge_iterator(pred, first, last), 828 in_edge_iterator(pred, last, last)); 829 } 830 831 // O(N) 832 template <typename D, typename VP, typename EP, typename GP, typename A> 833 typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,const adjacency_matrix<D,VP,EP,GP,A> & g)834 in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 835 const adjacency_matrix<D,VP,EP,GP,A>& g) 836 { 837 typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0; 838 typename adjacency_matrix<D,VP,EP,GP,A>::in_edge_iterator f, l; 839 for (boost::tie(f, l) = in_edges(u, g); f != l; ++f) 840 ++n; 841 return n; 842 } 843 844 //========================================================================= 845 // Functions required by the AdjacencyGraph concept 846 847 template <typename D, typename VP, typename EP, typename GP, typename A> 848 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator, 849 typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator> adjacent_vertices(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,const adjacency_matrix<D,VP,EP,GP,A> & g_)850 adjacent_vertices 851 (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 852 const adjacency_matrix<D,VP,EP,GP,A>& g_) 853 { 854 typedef adjacency_matrix<D,VP,EP,GP,A> Graph; 855 const Graph& cg = static_cast<const Graph&>(g_); 856 Graph& g = const_cast<Graph&>(cg); 857 typedef typename Graph::adjacency_iterator adjacency_iterator; 858 typename Graph::out_edge_iterator first, last; 859 boost::tie(first, last) = out_edges(u, g); 860 return std::make_pair(adjacency_iterator(first, &g), 861 adjacency_iterator(last, &g)); 862 } 863 864 //========================================================================= 865 // Functions required by the VertexListGraph concept 866 867 template <typename D, typename VP, typename EP, typename GP, typename A> 868 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator, 869 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator> vertices(const adjacency_matrix<D,VP,EP,GP,A> & g_)870 vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) { 871 typedef adjacency_matrix<D,VP,EP,GP,A> Graph; 872 Graph& g = const_cast<Graph&>(g_); 873 return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end()); 874 } 875 876 template <typename D, typename VP, typename EP, typename GP, typename A> 877 typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type num_vertices(const adjacency_matrix<D,VP,EP,GP,A> & g)878 num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) { 879 return g.m_vertex_set.size(); 880 } 881 882 //========================================================================= 883 // Functions required by the EdgeListGraph concept 884 885 template <typename D, typename VP, typename EP, typename GP, typename A> 886 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator, 887 typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator> edges(const adjacency_matrix<D,VP,EP,GP,A> & g_)888 edges(const adjacency_matrix<D,VP,EP,GP,A>& g_) 889 { 890 typedef adjacency_matrix<D,VP,EP,GP,A> Graph; 891 Graph& g = const_cast<Graph&>(g_); 892 893 typename Graph::unfiltered_edge_iter 894 first(g.m_matrix.begin(), g.m_matrix.begin(), 895 g.m_vertex_set.size()), 896 last(g.m_matrix.end(), g.m_matrix.begin(), 897 g.m_vertex_set.size()); 898 detail::does_edge_exist pred; 899 typedef typename Graph::edge_iterator edge_iterator; 900 return std::make_pair(edge_iterator(pred, first, last), 901 edge_iterator(pred, last, last)); 902 } 903 904 // O(1) 905 template <typename D, typename VP, typename EP, typename GP, typename A> 906 typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type num_edges(const adjacency_matrix<D,VP,EP,GP,A> & g)907 num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g) 908 { 909 return g.m_num_edges; 910 } 911 912 //========================================================================= 913 // Functions required by the MutableGraph concept 914 915 // O(1) 916 template <typename D, typename VP, typename EP, typename GP, typename A, 917 typename EP2> 918 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool> add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,const EP2 & ep,adjacency_matrix<D,VP,EP,GP,A> & g)919 add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 920 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, 921 const EP2& ep, 922 adjacency_matrix<D,VP,EP,GP,A>& g) 923 { 924 typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor 925 edge_descriptor; 926 if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) { 927 ++(g.m_num_edges); 928 detail::set_edge_property(g.get_edge(u,v), EP(ep), 0); 929 detail::set_edge_exists(g.get_edge(u,v), true, 0); 930 return std::make_pair 931 (edge_descriptor(true, u, v, &detail::get_edge_property(g.get_edge(u,v))), 932 true); 933 } else 934 return std::make_pair 935 (edge_descriptor(true, u, v, &detail::get_edge_property(g.get_edge(u,v))), 936 false); 937 } 938 // O(1) 939 template <typename D, typename VP, typename EP, typename GP, typename A> 940 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool> add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,adjacency_matrix<D,VP,EP,GP,A> & g)941 add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 942 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, 943 adjacency_matrix<D,VP,EP,GP,A>& g) 944 { 945 EP ep; 946 return add_edge(u, v, ep, g); 947 } 948 949 // O(1) 950 template <typename D, typename VP, typename EP, typename GP, typename A> 951 void remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,adjacency_matrix<D,VP,EP,GP,A> & g)952 remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 953 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, 954 adjacency_matrix<D,VP,EP,GP,A>& g) 955 { 956 // Don'remove the edge unless it already exists. 957 if(detail::get_edge_exists(g.get_edge(u,v), 0)) { 958 --(g.m_num_edges); 959 detail::set_edge_exists(g.get_edge(u,v), false, 0); 960 } 961 } 962 963 // O(1) 964 template <typename D, typename VP, typename EP, typename GP, typename A> 965 void remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e,adjacency_matrix<D,VP,EP,GP,A> & g)966 remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e, 967 adjacency_matrix<D,VP,EP,GP,A>& g) 968 { 969 remove_edge(source(e, g), target(e, g), g); 970 } 971 972 973 template <typename D, typename VP, typename EP, typename GP, typename A> 974 inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor add_vertex(adjacency_matrix<D,VP,EP,GP,A> & g)975 add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) { 976 // UNDER CONSTRUCTION 977 BOOST_ASSERT(false); 978 return *vertices(g).first; 979 } 980 981 template <typename D, typename VP, typename EP, typename GP, typename A, 982 typename VP2> 983 inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor add_vertex(const VP2 &,adjacency_matrix<D,VP,EP,GP,A> & g)984 add_vertex(const VP2& /*vp*/, adjacency_matrix<D,VP,EP,GP,A>& g) { 985 // UNDER CONSTRUCTION 986 BOOST_ASSERT(false); 987 return *vertices(g).first; 988 } 989 990 template <typename D, typename VP, typename EP, typename GP, typename A> 991 inline void remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor,adjacency_matrix<D,VP,EP,GP,A> &)992 remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor /*u*/, 993 adjacency_matrix<D,VP,EP,GP,A>& /*g*/) 994 { 995 // UNDER CONSTRUCTION 996 BOOST_ASSERT(false); 997 } 998 999 // O(V) 1000 template <typename VP, typename EP, typename GP, typename A> 1001 void clear_vertex(typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,adjacency_matrix<directedS,VP,EP,GP,A> & g)1002 clear_vertex 1003 (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, 1004 adjacency_matrix<directedS,VP,EP,GP,A>& g) 1005 { 1006 typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator 1007 vi, vi_end; 1008 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 1009 remove_edge(u, *vi, g); 1010 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 1011 remove_edge(*vi, u, g); 1012 } 1013 1014 // O(V) 1015 template <typename VP, typename EP, typename GP, typename A> 1016 void clear_vertex(typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,adjacency_matrix<undirectedS,VP,EP,GP,A> & g)1017 clear_vertex 1018 (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, 1019 adjacency_matrix<undirectedS,VP,EP,GP,A>& g) 1020 { 1021 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator 1022 vi, vi_end; 1023 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 1024 remove_edge(u, *vi, g); 1025 } 1026 1027 //========================================================================= 1028 // Functions required by the PropertyGraph concept 1029 1030 template <typename D, typename VP, typename EP, typename GP, typename A, 1031 typename Prop, typename Kind> 1032 struct adj_mat_pm_helper; 1033 1034 template <typename D, typename VP, typename EP, typename GP, typename A, 1035 typename Prop> 1036 struct adj_mat_pm_helper<D, VP, EP, GP, A, Prop, vertex_property_tag> { 1037 typedef typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::vertex_descriptor arg_type; 1038 typedef typed_identity_property_map<arg_type> vi_map_type; 1039 typedef iterator_property_map<typename std::vector<VP>::iterator, vi_map_type> all_map_type; 1040 typedef iterator_property_map<typename std::vector<VP>::const_iterator, vi_map_type> all_map_const_type; 1041 typedef transform_value_property_map< 1042 detail::lookup_one_property_f<VP, Prop>, 1043 all_map_type> 1044 type; 1045 typedef transform_value_property_map< 1046 detail::lookup_one_property_f<const VP, Prop>, 1047 all_map_const_type> 1048 const_type; 1049 typedef typename property_traits<type>::reference single_nonconst_type; 1050 typedef typename property_traits<const_type>::reference single_const_type; 1051 get_nonconstboost::adj_mat_pm_helper1052 static type get_nonconst(adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop) { 1053 return type(prop, all_map_type(g.m_vertex_properties.begin(), vi_map_type())); 1054 } 1055 get_constboost::adj_mat_pm_helper1056 static const_type get_const(const adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop) { 1057 return const_type(prop, all_map_const_type(g.m_vertex_properties.begin(), vi_map_type())); 1058 } 1059 get_nonconst_oneboost::adj_mat_pm_helper1060 static single_nonconst_type get_nonconst_one(adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop, arg_type v) { 1061 return lookup_one_property<VP, Prop>::lookup(g.m_vertex_properties[v], prop); 1062 } 1063 get_const_oneboost::adj_mat_pm_helper1064 static single_const_type get_const_one(const adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop, arg_type v) { 1065 return lookup_one_property<const VP, Prop>::lookup(g.m_vertex_properties[v], prop); 1066 } 1067 }; 1068 1069 template <typename D, typename VP, typename EP, typename GP, typename A, 1070 typename Tag> 1071 struct adj_mat_pm_helper<D, VP, EP, GP, A, Tag, edge_property_tag> { 1072 typedef typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::edge_descriptor edge_descriptor; 1073 1074 template <typename IsConst> 1075 struct lookup_property_from_edge { 1076 Tag tag; lookup_property_from_edgeboost::adj_mat_pm_helper::lookup_property_from_edge1077 lookup_property_from_edge(Tag tag): tag(tag) {} 1078 typedef typename boost::mpl::if_<IsConst, const EP, EP>::type ep_type_nonref; 1079 typedef ep_type_nonref& ep_type; 1080 typedef typename lookup_one_property<ep_type_nonref, Tag>::type& result_type; operator ()boost::adj_mat_pm_helper::lookup_property_from_edge1081 result_type operator()(edge_descriptor e) const { 1082 return lookup_one_property<ep_type_nonref, Tag>::lookup(*static_cast<ep_type_nonref*>(e.get_property()), tag); 1083 } 1084 }; 1085 1086 typedef function_property_map< 1087 lookup_property_from_edge<boost::mpl::false_>, 1088 typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::edge_descriptor> type; 1089 typedef function_property_map< 1090 lookup_property_from_edge<boost::mpl::true_>, 1091 typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::edge_descriptor> const_type; 1092 typedef edge_descriptor arg_type; 1093 typedef typename lookup_property_from_edge<boost::mpl::false_>::result_type single_nonconst_type; 1094 typedef typename lookup_property_from_edge<boost::mpl::true_>::result_type single_const_type; 1095 get_nonconstboost::adj_mat_pm_helper1096 static type get_nonconst(adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag) { 1097 return type(tag); 1098 } 1099 get_constboost::adj_mat_pm_helper1100 static const_type get_const(const adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag) { 1101 return const_type(tag); 1102 } 1103 get_nonconst_oneboost::adj_mat_pm_helper1104 static single_nonconst_type get_nonconst_one(adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag, edge_descriptor e) { 1105 return lookup_one_property<EP, Tag>::lookup(*static_cast<EP*>(e.get_property()), tag); 1106 } 1107 get_const_oneboost::adj_mat_pm_helper1108 static single_const_type get_const_one(const adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag, edge_descriptor e) { 1109 return lookup_one_property<const EP, Tag>::lookup(*static_cast<const EP*>(e.get_property()), tag); 1110 } 1111 }; 1112 1113 template <typename D, typename VP, typename EP, typename GP, typename A, 1114 typename Tag> 1115 struct property_map<adjacency_matrix<D,VP,EP,GP,A>, Tag> 1116 : adj_mat_pm_helper<D, VP, EP, GP, A, Tag, 1117 typename detail::property_kind_from_graph<adjacency_matrix<D, VP, EP, GP, A>, Tag>::type> {}; 1118 1119 template <typename D, typename VP, typename EP, typename GP, typename A, 1120 typename Tag> 1121 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::type get(Tag tag,adjacency_matrix<D,VP,EP,GP,A> & g)1122 get(Tag tag, adjacency_matrix<D, VP, EP, GP, A>& g) { 1123 return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_nonconst(g, tag); 1124 } 1125 1126 template <typename D, typename VP, typename EP, typename GP, typename A, 1127 typename Tag> 1128 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::const_type get(Tag tag,const adjacency_matrix<D,VP,EP,GP,A> & g)1129 get(Tag tag, const adjacency_matrix<D, VP, EP, GP, A>& g) { 1130 return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_const(g, tag); 1131 } 1132 1133 template <typename D, typename VP, typename EP, typename GP, typename A, 1134 typename Tag> 1135 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::single_nonconst_type get(Tag tag,adjacency_matrix<D,VP,EP,GP,A> & g,typename property_map<adjacency_matrix<D,VP,EP,GP,A>,Tag>::arg_type a)1136 get(Tag tag, adjacency_matrix<D, VP, EP, GP, A>& g, typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::arg_type a) { 1137 return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_nonconst_one(g, tag, a); 1138 } 1139 1140 template <typename D, typename VP, typename EP, typename GP, typename A, 1141 typename Tag> 1142 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::single_const_type get(Tag tag,const adjacency_matrix<D,VP,EP,GP,A> & g,typename property_map<adjacency_matrix<D,VP,EP,GP,A>,Tag>::arg_type a)1143 get(Tag tag, const adjacency_matrix<D, VP, EP, GP, A>& g, typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::arg_type a) { 1144 return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_const_one(g, tag, a); 1145 } 1146 1147 template <typename D, typename VP, typename EP, typename GP, typename A, 1148 typename Tag> 1149 void put(Tag tag,adjacency_matrix<D,VP,EP,GP,A> & g,typename property_map<adjacency_matrix<D,VP,EP,GP,A>,Tag>::arg_type a,typename property_map<adjacency_matrix<D,VP,EP,GP,A>,Tag>::single_const_type val)1150 put(Tag tag, 1151 adjacency_matrix<D, VP, EP, GP, A>& g, 1152 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::arg_type a, 1153 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::single_const_type val) { 1154 property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_nonconst_one(g, tag, a) = val; 1155 } 1156 1157 // O(1) 1158 template <typename D, typename VP, typename EP, typename GP, typename A, 1159 typename Tag, typename Value> 1160 inline void set_property(adjacency_matrix<D,VP,EP,GP,A> & g,Tag tag,const Value & value)1161 set_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag tag, const Value& value) 1162 { 1163 get_property_value(g.m_property, tag) = value; 1164 } 1165 1166 template <typename D, typename VP, typename EP, typename GP, typename A, 1167 typename Tag> 1168 inline typename graph_property<adjacency_matrix<D,VP,EP,GP,A>, Tag>::type& get_property(adjacency_matrix<D,VP,EP,GP,A> & g,Tag tag)1169 get_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag tag) 1170 { 1171 return get_property_value(g.m_property, tag); 1172 } 1173 1174 template <typename D, typename VP, typename EP, typename GP, typename A, 1175 typename Tag> 1176 inline const typename graph_property<adjacency_matrix<D,VP,EP,GP,A>, Tag>::type& get_property(const adjacency_matrix<D,VP,EP,GP,A> & g,Tag tag)1177 get_property(const adjacency_matrix<D,VP,EP,GP,A>& g, Tag tag) 1178 { 1179 return get_property_value(g.m_property, tag); 1180 } 1181 1182 //========================================================================= 1183 // Vertex Property Map 1184 1185 template <typename D, typename VP, typename EP, typename GP, typename A> 1186 struct property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t> { 1187 typedef typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor Vertex; 1188 typedef typed_identity_property_map<Vertex> type; 1189 typedef type const_type; 1190 }; 1191 1192 template <typename D, typename VP, typename EP, typename GP, typename A> 1193 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t>::const_type get(vertex_index_t,adjacency_matrix<D,VP,EP,GP,A> &)1194 get(vertex_index_t, adjacency_matrix<D, VP, EP, GP, A>&) { 1195 return typename property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t>::const_type(); 1196 } 1197 1198 template <typename D, typename VP, typename EP, typename GP, typename A> 1199 typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor get(vertex_index_t,adjacency_matrix<D,VP,EP,GP,A> &,typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v)1200 get(vertex_index_t, 1201 adjacency_matrix<D, VP, EP, GP, A>&, 1202 typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor v) { 1203 return v; 1204 } 1205 1206 template <typename D, typename VP, typename EP, typename GP, typename A> 1207 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t>::const_type get(vertex_index_t,const adjacency_matrix<D,VP,EP,GP,A> &)1208 get(vertex_index_t, const adjacency_matrix<D, VP, EP, GP, A>&) { 1209 return typename property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t>::const_type(); 1210 } 1211 1212 template <typename D, typename VP, typename EP, typename GP, typename A> 1213 typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor get(vertex_index_t,const adjacency_matrix<D,VP,EP,GP,A> &,typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v)1214 get(vertex_index_t, 1215 const adjacency_matrix<D, VP, EP, GP, A>&, 1216 typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor v) { 1217 return v; 1218 } 1219 1220 //========================================================================= 1221 // Other Functions 1222 1223 template <typename D, typename VP, typename EP, typename GP, typename A> 1224 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n,const adjacency_matrix<D,VP,EP,GP,A> &)1225 vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n, 1226 const adjacency_matrix<D,VP,EP,GP,A>&) 1227 { 1228 return n; 1229 } 1230 1231 template <typename D, typename VP, typename EP, typename GP, typename A> 1232 struct graph_mutability_traits<adjacency_matrix<D, VP, EP, GP, A> > { 1233 typedef mutable_edge_property_graph_tag category; 1234 }; 1235 1236 1237 } // namespace boost 1238 1239 #endif // BOOST_ADJACENCY_MATRIX_HPP 1240