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 <boost/assert.hpp> 18 #include <boost/limits.hpp> 19 #include <boost/iterator.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 typedef typename Allocator::template rebind<StoredEdge>::other Alloc; 503 typedef std::vector<StoredEdge, Alloc> Matrix; 504 #endif 505 typedef typename Matrix::iterator MatrixIter; 506 typedef typename Matrix::size_type size_type; 507 public: 508 // Graph concept required types 509 typedef typename Traits::vertex_descriptor vertex_descriptor; 510 typedef typename Traits::edge_descriptor edge_descriptor; 511 typedef typename Traits::directed_category directed_category; 512 typedef typename Traits::edge_parallel_category edge_parallel_category; 513 typedef adj_matrix_traversal_tag traversal_category; 514 null_vertex()515 static vertex_descriptor null_vertex() 516 { 517 return (std::numeric_limits<vertex_descriptor>::max)(); 518 } 519 520 //private: if friends worked, these would be private 521 522 typedef detail::dir_adj_matrix_out_edge_iter< 523 vertex_descriptor, MatrixIter, size_type, edge_descriptor 524 > DirOutEdgeIter; 525 526 typedef detail::undir_adj_matrix_out_edge_iter< 527 vertex_descriptor, MatrixIter, size_type, edge_descriptor 528 > UnDirOutEdgeIter; 529 530 typedef typename mpl::if_< 531 typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter 532 >::type unfiltered_out_edge_iter; 533 534 typedef detail::dir_adj_matrix_in_edge_iter< 535 vertex_descriptor, MatrixIter, size_type, edge_descriptor 536 > DirInEdgeIter; 537 538 typedef detail::undir_adj_matrix_in_edge_iter< 539 vertex_descriptor, MatrixIter, size_type, edge_descriptor 540 > UnDirInEdgeIter; 541 542 typedef typename mpl::if_< 543 typename Directed::is_directed_t, DirInEdgeIter, UnDirInEdgeIter 544 >::type unfiltered_in_edge_iter; 545 546 typedef detail::adj_matrix_edge_iter< 547 Directed, MatrixIter, size_type, edge_descriptor 548 > unfiltered_edge_iter; 549 550 public: 551 552 // IncidenceGraph concept required types 553 typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter> 554 out_edge_iterator; 555 556 typedef size_type degree_size_type; 557 558 // BidirectionalGraph required types 559 typedef filter_iterator<detail::does_edge_exist, unfiltered_in_edge_iter> 560 in_edge_iterator; 561 562 // AdjacencyGraph required types 563 typedef typename adjacency_iterator_generator<self, 564 vertex_descriptor, out_edge_iterator>::type adjacency_iterator; 565 566 // VertexListGraph required types 567 typedef size_type vertices_size_type; 568 typedef integer_range<vertex_descriptor> VertexList; 569 typedef typename VertexList::iterator vertex_iterator; 570 571 // EdgeListGraph required types 572 typedef size_type edges_size_type; 573 typedef filter_iterator< 574 detail::does_edge_exist, unfiltered_edge_iter 575 > edge_iterator; 576 577 // PropertyGraph required types 578 typedef adjacency_matrix_class_tag graph_tag; 579 580 // Constructor required by MutableGraph adjacency_matrix(vertices_size_type n_vertices,const GraphProperty & p=GraphProperty ())581 adjacency_matrix(vertices_size_type n_vertices, 582 const GraphProperty& p = GraphProperty()) 583 : m_matrix(Directed::is_directed ? 584 (n_vertices * n_vertices) 585 : (n_vertices * (n_vertices + 1) / 2)), 586 m_vertex_set(0, n_vertices), 587 m_vertex_properties(n_vertices), 588 m_num_edges(0), 589 m_property(p) { } 590 591 template <typename EdgeIterator> adjacency_matrix(EdgeIterator first,EdgeIterator last,vertices_size_type n_vertices,const GraphProperty & p=GraphProperty ())592 adjacency_matrix(EdgeIterator first, 593 EdgeIterator last, 594 vertices_size_type n_vertices, 595 const GraphProperty& p = GraphProperty()) 596 : m_matrix(Directed::is_directed ? 597 (n_vertices * n_vertices) 598 : (n_vertices * (n_vertices + 1) / 2)), 599 m_vertex_set(0, n_vertices), 600 m_vertex_properties(n_vertices), 601 m_num_edges(0), 602 m_property(p) 603 { 604 for (; first != last; ++first) { 605 add_edge(first->first, first->second, *this); 606 } 607 } 608 609 template <typename EdgeIterator, typename EdgePropertyIterator> adjacency_matrix(EdgeIterator first,EdgeIterator last,EdgePropertyIterator ep_iter,vertices_size_type n_vertices,const GraphProperty & p=GraphProperty ())610 adjacency_matrix(EdgeIterator first, 611 EdgeIterator last, 612 EdgePropertyIterator ep_iter, 613 vertices_size_type n_vertices, 614 const GraphProperty& p = GraphProperty()) 615 : m_matrix(Directed::is_directed ? 616 (n_vertices * n_vertices) 617 : (n_vertices * (n_vertices + 1) / 2)), 618 m_vertex_set(0, n_vertices), 619 m_vertex_properties(n_vertices), 620 m_num_edges(0), 621 m_property(p) 622 { 623 for (; first != last; ++first, ++ep_iter) { 624 add_edge(first->first, first->second, *ep_iter, *this); 625 } 626 } 627 628 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES 629 // Directly access a vertex or edge bundle operator [](vertex_descriptor v)630 vertex_bundled& operator[](vertex_descriptor v) 631 { return get(vertex_bundle, *this, v); } 632 operator [](vertex_descriptor v) const633 const vertex_bundled& operator[](vertex_descriptor v) const 634 { return get(vertex_bundle, *this, v); } 635 operator [](edge_descriptor e)636 edge_bundled& operator[](edge_descriptor e) 637 { return get(edge_bundle, *this, e); } 638 operator [](edge_descriptor e) const639 const edge_bundled& operator[](edge_descriptor e) const 640 { return get(edge_bundle, *this, e); } 641 operator [](graph_bundle_t)642 graph_bundled& operator[](graph_bundle_t) 643 { return get_property(*this); } 644 operator [](graph_bundle_t) const645 const graph_bundled& operator[](graph_bundle_t) const 646 { return get_property(*this); } 647 #endif 648 649 //private: if friends worked, these would be private 650 651 typename Matrix::const_reference get_edge(vertex_descriptor u,vertex_descriptor v) const652 get_edge(vertex_descriptor u, vertex_descriptor v) const { 653 if (Directed::is_directed) 654 return m_matrix[u * m_vertex_set.size() + v]; 655 else { 656 if (v > u) 657 std::swap(u, v); 658 return m_matrix[u * (u + 1)/2 + v]; 659 } 660 } 661 typename Matrix::reference get_edge(vertex_descriptor u,vertex_descriptor v)662 get_edge(vertex_descriptor u, vertex_descriptor v) { 663 if (Directed::is_directed) 664 return m_matrix[u * m_vertex_set.size() + v]; 665 else { 666 if (v > u) 667 std::swap(u, v); 668 return m_matrix[u * (u + 1)/2 + v]; 669 } 670 } 671 672 Matrix m_matrix; 673 VertexList m_vertex_set; 674 std::vector<vertex_property_type> m_vertex_properties; 675 size_type m_num_edges; 676 graph_property_type m_property; 677 }; 678 679 //========================================================================= 680 // Functions required by the AdjacencyMatrix concept 681 682 template <typename D, typename VP, typename EP, typename GP, typename A> 683 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, 684 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)685 edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 686 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, 687 const adjacency_matrix<D,VP,EP,GP,A>& g) 688 { 689 bool exists = detail::get_edge_exists(g.get_edge(u,v), 0); 690 typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor 691 e(exists, u, v, &detail::get_edge_property(g.get_edge(u,v))); 692 return std::make_pair(e, exists); 693 } 694 695 //========================================================================= 696 // Functions required by the IncidenceGraph concept 697 698 // O(1) 699 template <typename VP, typename EP, typename GP, typename A> 700 std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator, 701 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_)702 out_edges 703 (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, 704 const adjacency_matrix<directedS,VP,EP,GP,A>& g_) 705 { 706 typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph; 707 Graph& g = const_cast<Graph&>(g_); 708 typename Graph::vertices_size_type offset = u * g.m_vertex_set.size(); 709 typename Graph::MatrixIter f = g.m_matrix.begin() + offset; 710 typename Graph::MatrixIter l = f + g.m_vertex_set.size(); 711 typename Graph::unfiltered_out_edge_iter 712 first(f, u, g.m_vertex_set.size()) 713 , last(l, u, g.m_vertex_set.size()); 714 detail::does_edge_exist pred; 715 typedef typename Graph::out_edge_iterator out_edge_iterator; 716 return std::make_pair(out_edge_iterator(pred, first, last), 717 out_edge_iterator(pred, last, last)); 718 } 719 720 // O(1) 721 template <typename VP, typename EP, typename GP, typename A> 722 std::pair< 723 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator, 724 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_)725 out_edges 726 (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, 727 const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_) 728 { 729 typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph; 730 Graph& g = const_cast<Graph&>(g_); 731 typename Graph::vertices_size_type offset = u * (u + 1) / 2; 732 typename Graph::MatrixIter f = g.m_matrix.begin() + offset; 733 typename Graph::MatrixIter l = g.m_matrix.end(); 734 735 typename Graph::unfiltered_out_edge_iter 736 first(f, u, g.m_vertex_set.size()) 737 , last(l, u, g.m_vertex_set.size()); 738 739 detail::does_edge_exist pred; 740 typedef typename Graph::out_edge_iterator out_edge_iterator; 741 return std::make_pair(out_edge_iterator(pred, first, last), 742 out_edge_iterator(pred, last, last)); 743 } 744 745 // O(N) 746 template <typename D, typename VP, typename EP, typename GP, typename A> 747 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)748 out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 749 const adjacency_matrix<D,VP,EP,GP,A>& g) 750 { 751 typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0; 752 typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l; 753 for (boost::tie(f, l) = out_edges(u, g); f != l; ++f) 754 ++n; 755 return n; 756 } 757 758 // O(1) 759 template <typename D, typename VP, typename EP, typename GP, typename A, 760 typename Dir, typename Vertex> 761 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> &)762 source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e, 763 const adjacency_matrix<D,VP,EP,GP,A>&) 764 { 765 return e.m_source; 766 } 767 768 // O(1) 769 template <typename D, typename VP, typename EP, typename GP, typename A, 770 typename Dir, typename Vertex> 771 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> &)772 target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e, 773 const adjacency_matrix<D,VP,EP,GP,A>&) 774 { 775 return e.m_target; 776 } 777 778 //========================================================================= 779 // Functions required by the BidirectionalGraph concept 780 781 // O(1) 782 template <typename VP, typename EP, typename GP, typename A> 783 std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator, 784 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_)785 in_edges 786 (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, 787 const adjacency_matrix<directedS,VP,EP,GP,A>& g_) 788 { 789 typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph; 790 Graph& g = const_cast<Graph&>(g_); 791 typename Graph::MatrixIter f = g.m_matrix.begin() + u; 792 typename Graph::MatrixIter l = g.m_matrix.end(); 793 typename Graph::unfiltered_in_edge_iter 794 first(f, l, u, g.m_vertex_set.size()) 795 , last(l, l, u, g.m_vertex_set.size()); 796 detail::does_edge_exist pred; 797 typedef typename Graph::in_edge_iterator in_edge_iterator; 798 return std::make_pair(in_edge_iterator(pred, first, last), 799 in_edge_iterator(pred, last, last)); 800 } 801 802 // O(1) 803 template <typename VP, typename EP, typename GP, typename A> 804 std::pair< 805 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator, 806 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_)807 in_edges 808 (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, 809 const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_) 810 { 811 typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph; 812 Graph& g = const_cast<Graph&>(g_); 813 typename Graph::vertices_size_type offset = u * (u + 1) / 2; 814 typename Graph::MatrixIter f = g.m_matrix.begin() + offset; 815 typename Graph::MatrixIter l = g.m_matrix.end(); 816 817 typename Graph::unfiltered_in_edge_iter 818 first(f, u, g.m_vertex_set.size()) 819 , last(l, u, g.m_vertex_set.size()); 820 821 detail::does_edge_exist pred; 822 typedef typename Graph::in_edge_iterator in_edge_iterator; 823 return std::make_pair(in_edge_iterator(pred, first, last), 824 in_edge_iterator(pred, last, last)); 825 } 826 827 // O(N) 828 template <typename D, typename VP, typename EP, typename GP, typename A> 829 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)830 in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 831 const adjacency_matrix<D,VP,EP,GP,A>& g) 832 { 833 typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0; 834 typename adjacency_matrix<D,VP,EP,GP,A>::in_edge_iterator f, l; 835 for (boost::tie(f, l) = in_edges(u, g); f != l; ++f) 836 ++n; 837 return n; 838 } 839 840 //========================================================================= 841 // Functions required by the AdjacencyGraph concept 842 843 template <typename D, typename VP, typename EP, typename GP, typename A> 844 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator, 845 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_)846 adjacent_vertices 847 (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 848 const adjacency_matrix<D,VP,EP,GP,A>& g_) 849 { 850 typedef adjacency_matrix<D,VP,EP,GP,A> Graph; 851 const Graph& cg = static_cast<const Graph&>(g_); 852 Graph& g = const_cast<Graph&>(cg); 853 typedef typename Graph::adjacency_iterator adjacency_iterator; 854 typename Graph::out_edge_iterator first, last; 855 boost::tie(first, last) = out_edges(u, g); 856 return std::make_pair(adjacency_iterator(first, &g), 857 adjacency_iterator(last, &g)); 858 } 859 860 //========================================================================= 861 // Functions required by the VertexListGraph concept 862 863 template <typename D, typename VP, typename EP, typename GP, typename A> 864 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator, 865 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator> vertices(const adjacency_matrix<D,VP,EP,GP,A> & g_)866 vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) { 867 typedef adjacency_matrix<D,VP,EP,GP,A> Graph; 868 Graph& g = const_cast<Graph&>(g_); 869 return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end()); 870 } 871 872 template <typename D, typename VP, typename EP, typename GP, typename A> 873 typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type num_vertices(const adjacency_matrix<D,VP,EP,GP,A> & g)874 num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) { 875 return g.m_vertex_set.size(); 876 } 877 878 //========================================================================= 879 // Functions required by the EdgeListGraph concept 880 881 template <typename D, typename VP, typename EP, typename GP, typename A> 882 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator, 883 typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator> edges(const adjacency_matrix<D,VP,EP,GP,A> & g_)884 edges(const adjacency_matrix<D,VP,EP,GP,A>& g_) 885 { 886 typedef adjacency_matrix<D,VP,EP,GP,A> Graph; 887 Graph& g = const_cast<Graph&>(g_); 888 889 typename Graph::unfiltered_edge_iter 890 first(g.m_matrix.begin(), g.m_matrix.begin(), 891 g.m_vertex_set.size()), 892 last(g.m_matrix.end(), g.m_matrix.begin(), 893 g.m_vertex_set.size()); 894 detail::does_edge_exist pred; 895 typedef typename Graph::edge_iterator edge_iterator; 896 return std::make_pair(edge_iterator(pred, first, last), 897 edge_iterator(pred, last, last)); 898 } 899 900 // O(1) 901 template <typename D, typename VP, typename EP, typename GP, typename A> 902 typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type num_edges(const adjacency_matrix<D,VP,EP,GP,A> & g)903 num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g) 904 { 905 return g.m_num_edges; 906 } 907 908 //========================================================================= 909 // Functions required by the MutableGraph concept 910 911 // O(1) 912 template <typename D, typename VP, typename EP, typename GP, typename A, 913 typename EP2> 914 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)915 add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 916 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, 917 const EP2& ep, 918 adjacency_matrix<D,VP,EP,GP,A>& g) 919 { 920 typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor 921 edge_descriptor; 922 if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) { 923 ++(g.m_num_edges); 924 detail::set_edge_property(g.get_edge(u,v), EP(ep), 0); 925 detail::set_edge_exists(g.get_edge(u,v), true, 0); 926 return std::make_pair 927 (edge_descriptor(true, u, v, &detail::get_edge_property(g.get_edge(u,v))), 928 true); 929 } else 930 return std::make_pair 931 (edge_descriptor(true, u, v, &detail::get_edge_property(g.get_edge(u,v))), 932 false); 933 } 934 // O(1) 935 template <typename D, typename VP, typename EP, typename GP, typename A> 936 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)937 add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 938 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, 939 adjacency_matrix<D,VP,EP,GP,A>& g) 940 { 941 EP ep; 942 return add_edge(u, v, ep, g); 943 } 944 945 // O(1) 946 template <typename D, typename VP, typename EP, typename GP, typename A> 947 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)948 remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, 949 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, 950 adjacency_matrix<D,VP,EP,GP,A>& g) 951 { 952 // Don'remove the edge unless it already exists. 953 if(detail::get_edge_exists(g.get_edge(u,v), 0)) { 954 --(g.m_num_edges); 955 detail::set_edge_exists(g.get_edge(u,v), false, 0); 956 } 957 } 958 959 // O(1) 960 template <typename D, typename VP, typename EP, typename GP, typename A> 961 void remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e,adjacency_matrix<D,VP,EP,GP,A> & g)962 remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e, 963 adjacency_matrix<D,VP,EP,GP,A>& g) 964 { 965 remove_edge(source(e, g), target(e, g), g); 966 } 967 968 969 template <typename D, typename VP, typename EP, typename GP, typename A> 970 inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor add_vertex(adjacency_matrix<D,VP,EP,GP,A> & g)971 add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) { 972 // UNDER CONSTRUCTION 973 BOOST_ASSERT(false); 974 return *vertices(g).first; 975 } 976 977 template <typename D, typename VP, typename EP, typename GP, typename A, 978 typename VP2> 979 inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor add_vertex(const VP2 &,adjacency_matrix<D,VP,EP,GP,A> & g)980 add_vertex(const VP2& /*vp*/, adjacency_matrix<D,VP,EP,GP,A>& g) { 981 // UNDER CONSTRUCTION 982 BOOST_ASSERT(false); 983 return *vertices(g).first; 984 } 985 986 template <typename D, typename VP, typename EP, typename GP, typename A> 987 inline void remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor,adjacency_matrix<D,VP,EP,GP,A> &)988 remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor /*u*/, 989 adjacency_matrix<D,VP,EP,GP,A>& /*g*/) 990 { 991 // UNDER CONSTRUCTION 992 BOOST_ASSERT(false); 993 } 994 995 // O(V) 996 template <typename VP, typename EP, typename GP, typename A> 997 void clear_vertex(typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,adjacency_matrix<directedS,VP,EP,GP,A> & g)998 clear_vertex 999 (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, 1000 adjacency_matrix<directedS,VP,EP,GP,A>& g) 1001 { 1002 typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator 1003 vi, vi_end; 1004 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 1005 remove_edge(u, *vi, g); 1006 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 1007 remove_edge(*vi, u, g); 1008 } 1009 1010 // O(V) 1011 template <typename VP, typename EP, typename GP, typename A> 1012 void clear_vertex(typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,adjacency_matrix<undirectedS,VP,EP,GP,A> & g)1013 clear_vertex 1014 (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, 1015 adjacency_matrix<undirectedS,VP,EP,GP,A>& g) 1016 { 1017 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator 1018 vi, vi_end; 1019 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 1020 remove_edge(u, *vi, g); 1021 } 1022 1023 //========================================================================= 1024 // Functions required by the PropertyGraph concept 1025 1026 template <typename D, typename VP, typename EP, typename GP, typename A, 1027 typename Prop, typename Kind> 1028 struct adj_mat_pm_helper; 1029 1030 template <typename D, typename VP, typename EP, typename GP, typename A, 1031 typename Prop> 1032 struct adj_mat_pm_helper<D, VP, EP, GP, A, Prop, vertex_property_tag> { 1033 typedef typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::vertex_descriptor arg_type; 1034 typedef typed_identity_property_map<arg_type> vi_map_type; 1035 typedef iterator_property_map<typename std::vector<VP>::iterator, vi_map_type> all_map_type; 1036 typedef iterator_property_map<typename std::vector<VP>::const_iterator, vi_map_type> all_map_const_type; 1037 typedef transform_value_property_map< 1038 detail::lookup_one_property_f<VP, Prop>, 1039 all_map_type> 1040 type; 1041 typedef transform_value_property_map< 1042 detail::lookup_one_property_f<const VP, Prop>, 1043 all_map_const_type> 1044 const_type; 1045 typedef typename property_traits<type>::reference single_nonconst_type; 1046 typedef typename property_traits<const_type>::reference single_const_type; 1047 get_nonconstboost::adj_mat_pm_helper1048 static type get_nonconst(adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop) { 1049 return type(prop, all_map_type(g.m_vertex_properties.begin(), vi_map_type())); 1050 } 1051 get_constboost::adj_mat_pm_helper1052 static const_type get_const(const adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop) { 1053 return const_type(prop, all_map_const_type(g.m_vertex_properties.begin(), vi_map_type())); 1054 } 1055 get_nonconst_oneboost::adj_mat_pm_helper1056 static single_nonconst_type get_nonconst_one(adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop, arg_type v) { 1057 return lookup_one_property<VP, Prop>::lookup(g.m_vertex_properties[v], prop); 1058 } 1059 get_const_oneboost::adj_mat_pm_helper1060 static single_const_type get_const_one(const adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop, arg_type v) { 1061 return lookup_one_property<const VP, Prop>::lookup(g.m_vertex_properties[v], prop); 1062 } 1063 }; 1064 1065 template <typename D, typename VP, typename EP, typename GP, typename A, 1066 typename Tag> 1067 struct adj_mat_pm_helper<D, VP, EP, GP, A, Tag, edge_property_tag> { 1068 typedef typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::edge_descriptor edge_descriptor; 1069 1070 template <typename IsConst> 1071 struct lookup_property_from_edge { 1072 Tag tag; lookup_property_from_edgeboost::adj_mat_pm_helper::lookup_property_from_edge1073 lookup_property_from_edge(Tag tag): tag(tag) {} 1074 typedef typename boost::mpl::if_<IsConst, const EP, EP>::type ep_type_nonref; 1075 typedef ep_type_nonref& ep_type; 1076 typedef typename lookup_one_property<ep_type_nonref, Tag>::type& result_type; operator ()boost::adj_mat_pm_helper::lookup_property_from_edge1077 result_type operator()(edge_descriptor e) const { 1078 return lookup_one_property<ep_type_nonref, Tag>::lookup(*static_cast<ep_type_nonref*>(e.get_property()), tag); 1079 } 1080 }; 1081 1082 typedef function_property_map< 1083 lookup_property_from_edge<boost::mpl::false_>, 1084 typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::edge_descriptor> type; 1085 typedef function_property_map< 1086 lookup_property_from_edge<boost::mpl::true_>, 1087 typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::edge_descriptor> const_type; 1088 typedef edge_descriptor arg_type; 1089 typedef typename lookup_property_from_edge<boost::mpl::false_>::result_type single_nonconst_type; 1090 typedef typename lookup_property_from_edge<boost::mpl::true_>::result_type single_const_type; 1091 get_nonconstboost::adj_mat_pm_helper1092 static type get_nonconst(adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag) { 1093 return type(tag); 1094 } 1095 get_constboost::adj_mat_pm_helper1096 static const_type get_const(const adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag) { 1097 return const_type(tag); 1098 } 1099 get_nonconst_oneboost::adj_mat_pm_helper1100 static single_nonconst_type get_nonconst_one(adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag, edge_descriptor e) { 1101 return lookup_one_property<EP, Tag>::lookup(*static_cast<EP*>(e.get_property()), tag); 1102 } 1103 get_const_oneboost::adj_mat_pm_helper1104 static single_const_type get_const_one(const adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag, edge_descriptor e) { 1105 return lookup_one_property<const EP, Tag>::lookup(*static_cast<const EP*>(e.get_property()), tag); 1106 } 1107 }; 1108 1109 template <typename D, typename VP, typename EP, typename GP, typename A, 1110 typename Tag> 1111 struct property_map<adjacency_matrix<D,VP,EP,GP,A>, Tag> 1112 : adj_mat_pm_helper<D, VP, EP, GP, A, Tag, 1113 typename detail::property_kind_from_graph<adjacency_matrix<D, VP, EP, GP, A>, Tag>::type> {}; 1114 1115 template <typename D, typename VP, typename EP, typename GP, typename A, 1116 typename Tag> 1117 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::type get(Tag tag,adjacency_matrix<D,VP,EP,GP,A> & g)1118 get(Tag tag, adjacency_matrix<D, VP, EP, GP, A>& g) { 1119 return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_nonconst(g, tag); 1120 } 1121 1122 template <typename D, typename VP, typename EP, typename GP, typename A, 1123 typename Tag> 1124 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)1125 get(Tag tag, const adjacency_matrix<D, VP, EP, GP, A>& g) { 1126 return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_const(g, tag); 1127 } 1128 1129 template <typename D, typename VP, typename EP, typename GP, typename A, 1130 typename Tag> 1131 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)1132 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) { 1133 return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_nonconst_one(g, tag, a); 1134 } 1135 1136 template <typename D, typename VP, typename EP, typename GP, typename A, 1137 typename Tag> 1138 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)1139 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) { 1140 return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_const_one(g, tag, a); 1141 } 1142 1143 template <typename D, typename VP, typename EP, typename GP, typename A, 1144 typename Tag> 1145 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)1146 put(Tag tag, 1147 adjacency_matrix<D, VP, EP, GP, A>& g, 1148 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::arg_type a, 1149 typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::single_const_type val) { 1150 property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_nonconst_one(g, tag, a) = val; 1151 } 1152 1153 // O(1) 1154 template <typename D, typename VP, typename EP, typename GP, typename A, 1155 typename Tag, typename Value> 1156 inline void set_property(adjacency_matrix<D,VP,EP,GP,A> & g,Tag tag,const Value & value)1157 set_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag tag, const Value& value) 1158 { 1159 get_property_value(g.m_property, tag) = value; 1160 } 1161 1162 template <typename D, typename VP, typename EP, typename GP, typename A, 1163 typename Tag> 1164 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)1165 get_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag tag) 1166 { 1167 return get_property_value(g.m_property, tag); 1168 } 1169 1170 template <typename D, typename VP, typename EP, typename GP, typename A, 1171 typename Tag> 1172 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)1173 get_property(const adjacency_matrix<D,VP,EP,GP,A>& g, Tag tag) 1174 { 1175 return get_property_value(g.m_property, tag); 1176 } 1177 1178 //========================================================================= 1179 // Vertex Property Map 1180 1181 template <typename D, typename VP, typename EP, typename GP, typename A> 1182 struct property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t> { 1183 typedef typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor Vertex; 1184 typedef typed_identity_property_map<Vertex> type; 1185 typedef type const_type; 1186 }; 1187 1188 template <typename D, typename VP, typename EP, typename GP, typename A> 1189 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> &)1190 get(vertex_index_t, adjacency_matrix<D, VP, EP, GP, A>&) { 1191 return typename property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t>::const_type(); 1192 } 1193 1194 template <typename D, typename VP, typename EP, typename GP, typename A> 1195 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)1196 get(vertex_index_t, 1197 adjacency_matrix<D, VP, EP, GP, A>&, 1198 typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor v) { 1199 return v; 1200 } 1201 1202 template <typename D, typename VP, typename EP, typename GP, typename A> 1203 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> &)1204 get(vertex_index_t, const adjacency_matrix<D, VP, EP, GP, A>&) { 1205 return typename property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t>::const_type(); 1206 } 1207 1208 template <typename D, typename VP, typename EP, typename GP, typename A> 1209 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)1210 get(vertex_index_t, 1211 const adjacency_matrix<D, VP, EP, GP, A>&, 1212 typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor v) { 1213 return v; 1214 } 1215 1216 //========================================================================= 1217 // Other Functions 1218 1219 template <typename D, typename VP, typename EP, typename GP, typename A> 1220 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> &)1221 vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n, 1222 const adjacency_matrix<D,VP,EP,GP,A>&) 1223 { 1224 return n; 1225 } 1226 1227 template <typename D, typename VP, typename EP, typename GP, typename A> 1228 struct graph_mutability_traits<adjacency_matrix<D, VP, EP, GP, A> > { 1229 typedef mutable_edge_property_graph_tag category; 1230 }; 1231 1232 1233 } // namespace boost 1234 1235 #endif // BOOST_ADJACENCY_MATRIX_HPP 1236