| 1 | //======================================================================= |
|---|
| 2 | // Copyright 2001 University of Notre Dame. |
|---|
| 3 | // Author: Jeremy G. Siek |
|---|
| 4 | // |
|---|
| 5 | // Distributed under the Boost Software License, Version 1.0. (See |
|---|
| 6 | // accompanying file LICENSE_1_0.txt or copy at |
|---|
| 7 | // http://www.boost.org/LICENSE_1_0.txt) |
|---|
| 8 | //======================================================================= |
|---|
| 9 | |
|---|
| 10 | #ifndef BOOST_ADJACENCY_MATRIX_HPP |
|---|
| 11 | #define BOOST_ADJACENCY_MATRIX_HPP |
|---|
| 12 | |
|---|
| 13 | #include <boost/config.hpp> |
|---|
| 14 | #include <vector> |
|---|
| 15 | #include <memory> |
|---|
| 16 | #include <cassert> |
|---|
| 17 | #include <boost/limits.hpp> |
|---|
| 18 | #include <boost/iterator.hpp> |
|---|
| 19 | #include <boost/graph/graph_traits.hpp> |
|---|
| 20 | #include <boost/graph/graph_selectors.hpp> |
|---|
| 21 | #include <boost/pending/ct_if.hpp> |
|---|
| 22 | #include <boost/graph/adjacency_iterator.hpp> |
|---|
| 23 | #include <boost/graph/detail/edge.hpp> |
|---|
| 24 | #include <boost/iterator/iterator_adaptor.hpp> |
|---|
| 25 | #include <boost/iterator/filter_iterator.hpp> |
|---|
| 26 | #include <boost/pending/integer_range.hpp> |
|---|
| 27 | #include <boost/graph/properties.hpp> |
|---|
| 28 | #include <boost/tuple/tuple.hpp> |
|---|
| 29 | |
|---|
| 30 | namespace boost { |
|---|
| 31 | |
|---|
| 32 | namespace detail { |
|---|
| 33 | |
|---|
| 34 | template <class Directed, class Vertex> |
|---|
| 35 | class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex> |
|---|
| 36 | { |
|---|
| 37 | typedef edge_desc_impl<Directed,Vertex> Base; |
|---|
| 38 | public: |
|---|
| 39 | matrix_edge_desc_impl() { } |
|---|
| 40 | matrix_edge_desc_impl(bool exists, Vertex s, Vertex d, |
|---|
| 41 | const void* ep = 0) |
|---|
| 42 | : Base(s, d, ep), m_exists(exists) { } |
|---|
| 43 | bool exists() const { return m_exists; } |
|---|
| 44 | private: |
|---|
| 45 | bool m_exists; |
|---|
| 46 | }; |
|---|
| 47 | |
|---|
| 48 | struct does_edge_exist { |
|---|
| 49 | template <class Edge> |
|---|
| 50 | bool operator()(const Edge& e) const { return e.exists(); } |
|---|
| 51 | }; |
|---|
| 52 | |
|---|
| 53 | template <typename EdgeProperty> |
|---|
| 54 | bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) { |
|---|
| 55 | return stored_edge.first; |
|---|
| 56 | } |
|---|
| 57 | template <typename EdgeProperty> |
|---|
| 58 | void set_edge_exists( |
|---|
| 59 | std::pair<bool, EdgeProperty>& stored_edge, |
|---|
| 60 | bool flag, |
|---|
| 61 | int |
|---|
| 62 | ) { |
|---|
| 63 | stored_edge.first = flag; |
|---|
| 64 | } |
|---|
| 65 | |
|---|
| 66 | template <typename EdgeProxy> |
|---|
| 67 | bool get_edge_exists(const EdgeProxy& edge_proxy, ...) { |
|---|
| 68 | return edge_proxy; |
|---|
| 69 | } |
|---|
| 70 | template <typename EdgeProxy> |
|---|
| 71 | EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) { |
|---|
| 72 | edge_proxy = flag; |
|---|
| 73 | return edge_proxy; // just to avoid never used warning |
|---|
| 74 | } |
|---|
| 75 | |
|---|
| 76 | |
|---|
| 77 | |
|---|
| 78 | template <typename EdgeProperty> |
|---|
| 79 | const EdgeProperty& |
|---|
| 80 | get_property(const std::pair<bool, EdgeProperty>& stored_edge) { |
|---|
| 81 | return stored_edge.second; |
|---|
| 82 | } |
|---|
| 83 | template <typename EdgeProperty> |
|---|
| 84 | EdgeProperty& |
|---|
| 85 | get_property(std::pair<bool, EdgeProperty>& stored_edge) { |
|---|
| 86 | return stored_edge.second; |
|---|
| 87 | } |
|---|
| 88 | |
|---|
| 89 | template <typename StoredEdgeProperty, typename EdgeProperty> |
|---|
| 90 | inline void |
|---|
| 91 | set_property(std::pair<bool, StoredEdgeProperty>& stored_edge, |
|---|
| 92 | const EdgeProperty& ep, int) { |
|---|
| 93 | stored_edge.second = ep; |
|---|
| 94 | } |
|---|
| 95 | |
|---|
| 96 | inline const no_property& get_property(const char&) { |
|---|
| 97 | static no_property s_prop; |
|---|
| 98 | return s_prop; |
|---|
| 99 | } |
|---|
| 100 | inline no_property& get_property(char&) { |
|---|
| 101 | static no_property s_prop; |
|---|
| 102 | return s_prop; |
|---|
| 103 | } |
|---|
| 104 | template <typename EdgeProxy, typename EdgeProperty> |
|---|
| 105 | inline void |
|---|
| 106 | set_property(EdgeProxy, const EdgeProperty&, ...) {} |
|---|
| 107 | |
|---|
| 108 | //======================================================================= |
|---|
| 109 | // Directed Out Edge Iterator |
|---|
| 110 | |
|---|
| 111 | template < |
|---|
| 112 | typename VertexDescriptor, typename MatrixIter |
|---|
| 113 | , typename VerticesSizeType, typename EdgeDescriptor |
|---|
| 114 | > |
|---|
| 115 | struct dir_adj_matrix_out_edge_iter |
|---|
| 116 | : iterator_adaptor< |
|---|
| 117 | dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
|---|
| 118 | , MatrixIter |
|---|
| 119 | , EdgeDescriptor |
|---|
| 120 | , use_default |
|---|
| 121 | , EdgeDescriptor |
|---|
| 122 | , std::ptrdiff_t |
|---|
| 123 | > |
|---|
| 124 | { |
|---|
| 125 | typedef iterator_adaptor< |
|---|
| 126 | dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
|---|
| 127 | , MatrixIter |
|---|
| 128 | , EdgeDescriptor |
|---|
| 129 | , use_default |
|---|
| 130 | , EdgeDescriptor |
|---|
| 131 | , std::ptrdiff_t |
|---|
| 132 | > super_t; |
|---|
| 133 | |
|---|
| 134 | dir_adj_matrix_out_edge_iter() { } |
|---|
| 135 | |
|---|
| 136 | dir_adj_matrix_out_edge_iter( |
|---|
| 137 | const MatrixIter& i |
|---|
| 138 | , const VertexDescriptor& src |
|---|
| 139 | , const VerticesSizeType& n |
|---|
| 140 | ) |
|---|
| 141 | : super_t(i), m_src(src), m_targ(0), m_n(n) |
|---|
| 142 | { } |
|---|
| 143 | |
|---|
| 144 | void increment() { |
|---|
| 145 | ++this->base_reference(); |
|---|
| 146 | ++m_targ; |
|---|
| 147 | } |
|---|
| 148 | |
|---|
| 149 | inline EdgeDescriptor |
|---|
| 150 | dereference() const |
|---|
| 151 | { |
|---|
| 152 | return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ, |
|---|
| 153 | &get_property(*this->base())); |
|---|
| 154 | } |
|---|
| 155 | VertexDescriptor m_src, m_targ; |
|---|
| 156 | VerticesSizeType m_n; |
|---|
| 157 | }; |
|---|
| 158 | |
|---|
| 159 | //======================================================================= |
|---|
| 160 | // Undirected Out Edge Iterator |
|---|
| 161 | |
|---|
| 162 | template < |
|---|
| 163 | typename VertexDescriptor, typename MatrixIter |
|---|
| 164 | , typename VerticesSizeType, typename EdgeDescriptor |
|---|
| 165 | > |
|---|
| 166 | struct undir_adj_matrix_out_edge_iter |
|---|
| 167 | : iterator_adaptor< |
|---|
| 168 | undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
|---|
| 169 | , MatrixIter |
|---|
| 170 | , EdgeDescriptor |
|---|
| 171 | , use_default |
|---|
| 172 | , EdgeDescriptor |
|---|
| 173 | , std::ptrdiff_t |
|---|
| 174 | > |
|---|
| 175 | { |
|---|
| 176 | typedef iterator_adaptor< |
|---|
| 177 | undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
|---|
| 178 | , MatrixIter |
|---|
| 179 | , EdgeDescriptor |
|---|
| 180 | , use_default |
|---|
| 181 | , EdgeDescriptor |
|---|
| 182 | , std::ptrdiff_t |
|---|
| 183 | > super_t; |
|---|
| 184 | |
|---|
| 185 | undir_adj_matrix_out_edge_iter() { } |
|---|
| 186 | |
|---|
| 187 | undir_adj_matrix_out_edge_iter( |
|---|
| 188 | const MatrixIter& i |
|---|
| 189 | , const VertexDescriptor& src |
|---|
| 190 | , const VerticesSizeType& n |
|---|
| 191 | ) |
|---|
| 192 | : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n) |
|---|
| 193 | {} |
|---|
| 194 | |
|---|
| 195 | void increment() |
|---|
| 196 | { |
|---|
| 197 | if (m_targ < m_src) // first half |
|---|
| 198 | { |
|---|
| 199 | ++this->base_reference(); |
|---|
| 200 | } |
|---|
| 201 | else if (m_targ < m_n - 1) |
|---|
| 202 | { // second half |
|---|
| 203 | ++m_inc; |
|---|
| 204 | this->base_reference() += m_inc; |
|---|
| 205 | } |
|---|
| 206 | else |
|---|
| 207 | { // past-the-end |
|---|
| 208 | this->base_reference() += m_n - m_src; |
|---|
| 209 | } |
|---|
| 210 | ++m_targ; |
|---|
| 211 | } |
|---|
| 212 | |
|---|
| 213 | inline EdgeDescriptor |
|---|
| 214 | dereference() const |
|---|
| 215 | { |
|---|
| 216 | return EdgeDescriptor( |
|---|
| 217 | get_edge_exists(*this->base(), 0), m_src, m_targ |
|---|
| 218 | , &get_property(*this->base()) |
|---|
| 219 | ); |
|---|
| 220 | } |
|---|
| 221 | |
|---|
| 222 | VertexDescriptor m_src, m_inc, m_targ; |
|---|
| 223 | VerticesSizeType m_n; |
|---|
| 224 | }; |
|---|
| 225 | |
|---|
| 226 | //======================================================================= |
|---|
| 227 | // Edge Iterator |
|---|
| 228 | |
|---|
| 229 | template <typename Directed, typename MatrixIter, |
|---|
| 230 | typename VerticesSizeType, typename EdgeDescriptor> |
|---|
| 231 | struct adj_matrix_edge_iter |
|---|
| 232 | : iterator_adaptor< |
|---|
| 233 | adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor> |
|---|
| 234 | , MatrixIter |
|---|
| 235 | , EdgeDescriptor |
|---|
| 236 | , use_default |
|---|
| 237 | , EdgeDescriptor |
|---|
| 238 | , std::ptrdiff_t |
|---|
| 239 | > |
|---|
| 240 | { |
|---|
| 241 | typedef iterator_adaptor< |
|---|
| 242 | adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor> |
|---|
| 243 | , MatrixIter |
|---|
| 244 | , EdgeDescriptor |
|---|
| 245 | , use_default |
|---|
| 246 | , EdgeDescriptor |
|---|
| 247 | , std::ptrdiff_t |
|---|
| 248 | > super_t; |
|---|
| 249 | |
|---|
| 250 | adj_matrix_edge_iter() { } |
|---|
| 251 | |
|---|
| 252 | adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n) |
|---|
| 253 | : super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { } |
|---|
| 254 | |
|---|
| 255 | void increment() |
|---|
| 256 | { |
|---|
| 257 | increment_dispatch(this->base_reference(), Directed()); |
|---|
| 258 | } |
|---|
| 259 | |
|---|
| 260 | void increment_dispatch(MatrixIter& i, directedS) |
|---|
| 261 | { |
|---|
| 262 | ++i; |
|---|
| 263 | if (m_targ == m_n - 1) |
|---|
| 264 | { |
|---|
| 265 | m_targ = 0; |
|---|
| 266 | ++m_src; |
|---|
| 267 | } |
|---|
| 268 | else |
|---|
| 269 | { |
|---|
| 270 | ++m_targ; |
|---|
| 271 | } |
|---|
| 272 | } |
|---|
| 273 | |
|---|
| 274 | void increment_dispatch(MatrixIter& i, undirectedS) |
|---|
| 275 | { |
|---|
| 276 | ++i; |
|---|
| 277 | if (m_targ == m_src) |
|---|
| 278 | { |
|---|
| 279 | m_targ = 0; |
|---|
| 280 | ++m_src; |
|---|
| 281 | } |
|---|
| 282 | else |
|---|
| 283 | { |
|---|
| 284 | ++m_targ; |
|---|
| 285 | } |
|---|
| 286 | } |
|---|
| 287 | |
|---|
| 288 | inline EdgeDescriptor |
|---|
| 289 | dereference() const |
|---|
| 290 | { |
|---|
| 291 | return EdgeDescriptor( |
|---|
| 292 | get_edge_exists( |
|---|
| 293 | *this->base(), 0), m_src, m_targ, &get_property(*this->base()) |
|---|
| 294 | ); |
|---|
| 295 | } |
|---|
| 296 | |
|---|
| 297 | MatrixIter m_start; |
|---|
| 298 | VerticesSizeType m_src, m_targ, m_n; |
|---|
| 299 | }; |
|---|
| 300 | |
|---|
| 301 | } // namespace detail |
|---|
| 302 | |
|---|
| 303 | //========================================================================= |
|---|
| 304 | // Adjacency Matrix Traits |
|---|
| 305 | template <typename Directed = directedS> |
|---|
| 306 | class adjacency_matrix_traits { |
|---|
| 307 | typedef typename Directed::is_bidir_t is_bidir; |
|---|
| 308 | typedef typename Directed::is_directed_t is_directed; |
|---|
| 309 | public: |
|---|
| 310 | typedef typename boost::ct_if_t<is_bidir, |
|---|
| 311 | bidirectional_tag, |
|---|
| 312 | typename boost::ct_if_t<is_directed, |
|---|
| 313 | directed_tag, undirected_tag |
|---|
| 314 | >::type |
|---|
| 315 | >::type directed_category; |
|---|
| 316 | |
|---|
| 317 | typedef disallow_parallel_edge_tag edge_parallel_category; |
|---|
| 318 | |
|---|
| 319 | typedef std::size_t vertex_descriptor; |
|---|
| 320 | |
|---|
| 321 | typedef detail::matrix_edge_desc_impl<directed_category, |
|---|
| 322 | vertex_descriptor> edge_descriptor; |
|---|
| 323 | }; |
|---|
| 324 | |
|---|
| 325 | struct adjacency_matrix_class_tag { }; |
|---|
| 326 | |
|---|
| 327 | struct adj_matrix_traversal_tag : |
|---|
| 328 | public virtual adjacency_matrix_tag, |
|---|
| 329 | public virtual vertex_list_graph_tag, |
|---|
| 330 | public virtual incidence_graph_tag, |
|---|
| 331 | public virtual adjacency_graph_tag, |
|---|
| 332 | public virtual edge_list_graph_tag { }; |
|---|
| 333 | |
|---|
| 334 | //========================================================================= |
|---|
| 335 | // Adjacency Matrix Class |
|---|
| 336 | template <typename Directed = directedS, |
|---|
| 337 | typename VertexProperty = no_property, |
|---|
| 338 | typename EdgeProperty = no_property, |
|---|
| 339 | typename GraphProperty = no_property, |
|---|
| 340 | typename Allocator = std::allocator<bool> > |
|---|
| 341 | class adjacency_matrix { |
|---|
| 342 | typedef adjacency_matrix self; |
|---|
| 343 | typedef adjacency_matrix_traits<Directed> Traits; |
|---|
| 344 | |
|---|
| 345 | public: |
|---|
| 346 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
|---|
| 347 | typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::type |
|---|
| 348 | vertex_property_type; |
|---|
| 349 | typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type |
|---|
| 350 | edge_property_type; |
|---|
| 351 | |
|---|
| 352 | private: |
|---|
| 353 | typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::retagged |
|---|
| 354 | maybe_vertex_bundled; |
|---|
| 355 | |
|---|
| 356 | typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::retagged |
|---|
| 357 | maybe_edge_bundled; |
|---|
| 358 | |
|---|
| 359 | public: |
|---|
| 360 | // The types that are actually bundled |
|---|
| 361 | typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value), |
|---|
| 362 | no_vertex_bundle, |
|---|
| 363 | maybe_vertex_bundled>::type vertex_bundled; |
|---|
| 364 | typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value), |
|---|
| 365 | no_edge_bundle, |
|---|
| 366 | maybe_edge_bundled>::type edge_bundled; |
|---|
| 367 | #else |
|---|
| 368 | typedef EdgeProperty edge_property_type; |
|---|
| 369 | typedef VertexProperty vertex_property_type; |
|---|
| 370 | typedef no_vertex_bundle vertex_bundled; |
|---|
| 371 | typedef no_edge_bundle edge_bundled; |
|---|
| 372 | #endif |
|---|
| 373 | |
|---|
| 374 | public: // should be private |
|---|
| 375 | typedef typename ct_if_t<typename has_property<edge_property_type>::type, |
|---|
| 376 | std::pair<bool, edge_property_type>, char>::type StoredEdge; |
|---|
| 377 | #if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) || defined(BOOST_NO_STD_ALLOCATOR) |
|---|
| 378 | typedef std::vector<StoredEdge> Matrix; |
|---|
| 379 | #else |
|---|
| 380 | // This causes internal compiler error for MSVC |
|---|
| 381 | typedef typename Allocator::template rebind<StoredEdge>::other Alloc; |
|---|
| 382 | typedef std::vector<StoredEdge, Alloc> Matrix; |
|---|
| 383 | #endif |
|---|
| 384 | typedef typename Matrix::iterator MatrixIter; |
|---|
| 385 | typedef typename Matrix::size_type size_type; |
|---|
| 386 | public: |
|---|
| 387 | // Graph concept required types |
|---|
| 388 | typedef typename Traits::vertex_descriptor vertex_descriptor; |
|---|
| 389 | typedef typename Traits::edge_descriptor edge_descriptor; |
|---|
| 390 | typedef typename Traits::directed_category directed_category; |
|---|
| 391 | typedef typename Traits::edge_parallel_category edge_parallel_category; |
|---|
| 392 | typedef adj_matrix_traversal_tag traversal_category; |
|---|
| 393 | |
|---|
| 394 | static vertex_descriptor null_vertex() |
|---|
| 395 | { |
|---|
| 396 | return (std::numeric_limits<vertex_descriptor>::max)(); |
|---|
| 397 | } |
|---|
| 398 | |
|---|
| 399 | //private: if friends worked, these would be private |
|---|
| 400 | |
|---|
| 401 | typedef detail::dir_adj_matrix_out_edge_iter< |
|---|
| 402 | vertex_descriptor, MatrixIter, size_type, edge_descriptor |
|---|
| 403 | > DirOutEdgeIter; |
|---|
| 404 | |
|---|
| 405 | typedef detail::undir_adj_matrix_out_edge_iter< |
|---|
| 406 | vertex_descriptor, MatrixIter, size_type, edge_descriptor |
|---|
| 407 | > UnDirOutEdgeIter; |
|---|
| 408 | |
|---|
| 409 | typedef typename ct_if_t< |
|---|
| 410 | typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter |
|---|
| 411 | >::type unfiltered_out_edge_iter; |
|---|
| 412 | |
|---|
| 413 | typedef detail::adj_matrix_edge_iter< |
|---|
| 414 | Directed, MatrixIter, size_type, edge_descriptor |
|---|
| 415 | > unfiltered_edge_iter; |
|---|
| 416 | |
|---|
| 417 | public: |
|---|
| 418 | |
|---|
| 419 | // IncidenceGraph concept required types |
|---|
| 420 | typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter> |
|---|
| 421 | out_edge_iterator; |
|---|
| 422 | |
|---|
| 423 | typedef size_type degree_size_type; |
|---|
| 424 | |
|---|
| 425 | // BidirectionalGraph required types |
|---|
| 426 | typedef void in_edge_iterator; |
|---|
| 427 | |
|---|
| 428 | // AdjacencyGraph required types |
|---|
| 429 | typedef typename adjacency_iterator_generator<self, |
|---|
| 430 | vertex_descriptor, out_edge_iterator>::type adjacency_iterator; |
|---|
| 431 | |
|---|
| 432 | // VertexListGraph required types |
|---|
| 433 | typedef size_type vertices_size_type; |
|---|
| 434 | typedef integer_range<vertex_descriptor> VertexList; |
|---|
| 435 | typedef typename VertexList::iterator vertex_iterator; |
|---|
| 436 | |
|---|
| 437 | // EdgeListGrpah required types |
|---|
| 438 | typedef size_type edges_size_type; |
|---|
| 439 | typedef filter_iterator< |
|---|
| 440 | detail::does_edge_exist, unfiltered_edge_iter |
|---|
| 441 | > edge_iterator; |
|---|
| 442 | |
|---|
| 443 | // PropertyGraph required types |
|---|
| 444 | typedef adjacency_matrix_class_tag graph_tag; |
|---|
| 445 | |
|---|
| 446 | // Constructor required by MutableGraph |
|---|
| 447 | adjacency_matrix(vertices_size_type n_vertices) |
|---|
| 448 | : m_matrix(Directed::is_directed ? |
|---|
| 449 | (n_vertices * n_vertices) |
|---|
| 450 | : (n_vertices * (n_vertices + 1) / 2)), |
|---|
| 451 | m_vertex_set(0, n_vertices), |
|---|
| 452 | m_vertex_properties(n_vertices), |
|---|
| 453 | m_num_edges(0) { } |
|---|
| 454 | |
|---|
| 455 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
|---|
| 456 | // Directly access a vertex or edge bundle |
|---|
| 457 | vertex_bundled& operator[](vertex_descriptor v) |
|---|
| 458 | { return get(vertex_bundle, *this)[v]; } |
|---|
| 459 | |
|---|
| 460 | const vertex_bundled& operator[](vertex_descriptor v) const |
|---|
| 461 | { return get(vertex_bundle, *this)[v]; } |
|---|
| 462 | |
|---|
| 463 | edge_bundled& operator[](edge_descriptor e) |
|---|
| 464 | { return get(edge_bundle, *this)[e]; } |
|---|
| 465 | |
|---|
| 466 | const edge_bundled& operator[](edge_descriptor e) const |
|---|
| 467 | { return get(edge_bundle, *this)[e]; } |
|---|
| 468 | #endif |
|---|
| 469 | |
|---|
| 470 | //private: if friends worked, these would be private |
|---|
| 471 | |
|---|
| 472 | typename Matrix::const_reference |
|---|
| 473 | get_edge(vertex_descriptor u, vertex_descriptor v) const { |
|---|
| 474 | if (Directed::is_directed) |
|---|
| 475 | return m_matrix[u * m_vertex_set.size() + v]; |
|---|
| 476 | else { |
|---|
| 477 | if (v > u) |
|---|
| 478 | std::swap(u, v); |
|---|
| 479 | return m_matrix[u * (u + 1)/2 + v]; |
|---|
| 480 | } |
|---|
| 481 | } |
|---|
| 482 | typename Matrix::reference |
|---|
| 483 | get_edge(vertex_descriptor u, vertex_descriptor v) { |
|---|
| 484 | if (Directed::is_directed) |
|---|
| 485 | return m_matrix[u * m_vertex_set.size() + v]; |
|---|
| 486 | else { |
|---|
| 487 | if (v > u) |
|---|
| 488 | std::swap(u, v); |
|---|
| 489 | return m_matrix[u * (u + 1)/2 + v]; |
|---|
| 490 | } |
|---|
| 491 | } |
|---|
| 492 | |
|---|
| 493 | Matrix m_matrix; |
|---|
| 494 | VertexList m_vertex_set; |
|---|
| 495 | std::vector<vertex_property_type> m_vertex_properties; |
|---|
| 496 | size_type m_num_edges; |
|---|
| 497 | }; |
|---|
| 498 | |
|---|
| 499 | //========================================================================= |
|---|
| 500 | // Functions required by the AdjacencyMatrix concept |
|---|
| 501 | |
|---|
| 502 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 503 | std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, |
|---|
| 504 | bool> |
|---|
| 505 | edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 506 | typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, |
|---|
| 507 | const adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 508 | { |
|---|
| 509 | bool exists = detail::get_edge_exists(g.get_edge(u,v), 0); |
|---|
| 510 | typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor |
|---|
| 511 | e(exists, u, v, &detail::get_property(g.get_edge(u,v))); |
|---|
| 512 | return std::make_pair(e, exists); |
|---|
| 513 | } |
|---|
| 514 | |
|---|
| 515 | //========================================================================= |
|---|
| 516 | // Functions required by the IncidenceGraph concept |
|---|
| 517 | |
|---|
| 518 | // O(1) |
|---|
| 519 | template <typename VP, typename EP, typename GP, typename A> |
|---|
| 520 | std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator, |
|---|
| 521 | typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator> |
|---|
| 522 | out_edges |
|---|
| 523 | (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 524 | const adjacency_matrix<directedS,VP,EP,GP,A>& g_) |
|---|
| 525 | { |
|---|
| 526 | typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph; |
|---|
| 527 | Graph& g = const_cast<Graph&>(g_); |
|---|
| 528 | typename Graph::vertices_size_type offset = u * g.m_vertex_set.size(); |
|---|
| 529 | typename Graph::MatrixIter f = g.m_matrix.begin() + offset; |
|---|
| 530 | typename Graph::MatrixIter l = f + g.m_vertex_set.size(); |
|---|
| 531 | typename Graph::unfiltered_out_edge_iter |
|---|
| 532 | first(f, u, g.m_vertex_set.size()) |
|---|
| 533 | , last(l, u, g.m_vertex_set.size()); |
|---|
| 534 | detail::does_edge_exist pred; |
|---|
| 535 | typedef typename Graph::out_edge_iterator out_edge_iterator; |
|---|
| 536 | return std::make_pair(out_edge_iterator(pred, first, last), |
|---|
| 537 | out_edge_iterator(pred, last, last)); |
|---|
| 538 | } |
|---|
| 539 | |
|---|
| 540 | // O(1) |
|---|
| 541 | template <typename VP, typename EP, typename GP, typename A> |
|---|
| 542 | std::pair< |
|---|
| 543 | typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator, |
|---|
| 544 | typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator> |
|---|
| 545 | out_edges |
|---|
| 546 | (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 547 | const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_) |
|---|
| 548 | { |
|---|
| 549 | typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph; |
|---|
| 550 | Graph& g = const_cast<Graph&>(g_); |
|---|
| 551 | typename Graph::vertices_size_type offset = u * (u + 1) / 2; |
|---|
| 552 | typename Graph::MatrixIter f = g.m_matrix.begin() + offset; |
|---|
| 553 | typename Graph::MatrixIter l = g.m_matrix.end(); |
|---|
| 554 | |
|---|
| 555 | typename Graph::unfiltered_out_edge_iter |
|---|
| 556 | first(f, u, g.m_vertex_set.size()) |
|---|
| 557 | , last(l, u, g.m_vertex_set.size()); |
|---|
| 558 | |
|---|
| 559 | detail::does_edge_exist pred; |
|---|
| 560 | typedef typename Graph::out_edge_iterator out_edge_iterator; |
|---|
| 561 | return std::make_pair(out_edge_iterator(pred, first, last), |
|---|
| 562 | out_edge_iterator(pred, last, last)); |
|---|
| 563 | } |
|---|
| 564 | |
|---|
| 565 | // O(N) |
|---|
| 566 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 567 | typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type |
|---|
| 568 | out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 569 | const adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 570 | { |
|---|
| 571 | typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0; |
|---|
| 572 | typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l; |
|---|
| 573 | for (tie(f, l) = out_edges(u, g); f != l; ++f) |
|---|
| 574 | ++n; |
|---|
| 575 | return n; |
|---|
| 576 | } |
|---|
| 577 | |
|---|
| 578 | // O(1) |
|---|
| 579 | template <typename D, typename VP, typename EP, typename GP, typename A, |
|---|
| 580 | typename Dir, typename Vertex> |
|---|
| 581 | typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor |
|---|
| 582 | source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e, |
|---|
| 583 | const adjacency_matrix<D,VP,EP,GP,A>&) |
|---|
| 584 | { |
|---|
| 585 | return e.m_source; |
|---|
| 586 | } |
|---|
| 587 | |
|---|
| 588 | // O(1) |
|---|
| 589 | template <typename D, typename VP, typename EP, typename GP, typename A, |
|---|
| 590 | typename Dir, typename Vertex> |
|---|
| 591 | typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor |
|---|
| 592 | target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e, |
|---|
| 593 | const adjacency_matrix<D,VP,EP,GP,A>&) |
|---|
| 594 | { |
|---|
| 595 | return e.m_target; |
|---|
| 596 | } |
|---|
| 597 | |
|---|
| 598 | //========================================================================= |
|---|
| 599 | // Functions required by the AdjacencyGraph concept |
|---|
| 600 | |
|---|
| 601 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 602 | std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator, |
|---|
| 603 | typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator> |
|---|
| 604 | adjacent_vertices |
|---|
| 605 | (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 606 | const adjacency_matrix<D,VP,EP,GP,A>& g_) |
|---|
| 607 | { |
|---|
| 608 | typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
|---|
| 609 | const Graph& cg = static_cast<const Graph&>(g_); |
|---|
| 610 | Graph& g = const_cast<Graph&>(cg); |
|---|
| 611 | typedef typename Graph::adjacency_iterator adjacency_iterator; |
|---|
| 612 | typename Graph::out_edge_iterator first, last; |
|---|
| 613 | boost::tie(first, last) = out_edges(u, g); |
|---|
| 614 | return std::make_pair(adjacency_iterator(first, &g), |
|---|
| 615 | adjacency_iterator(last, &g)); |
|---|
| 616 | } |
|---|
| 617 | |
|---|
| 618 | //========================================================================= |
|---|
| 619 | // Functions required by the VertexListGraph concept |
|---|
| 620 | |
|---|
| 621 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 622 | std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator, |
|---|
| 623 | typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator> |
|---|
| 624 | vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) { |
|---|
| 625 | typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
|---|
| 626 | Graph& g = const_cast<Graph&>(g_); |
|---|
| 627 | return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end()); |
|---|
| 628 | } |
|---|
| 629 | |
|---|
| 630 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 631 | typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type |
|---|
| 632 | num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) { |
|---|
| 633 | return g.m_vertex_set.size(); |
|---|
| 634 | } |
|---|
| 635 | |
|---|
| 636 | //========================================================================= |
|---|
| 637 | // Functions required by the EdgeListGraph concept |
|---|
| 638 | |
|---|
| 639 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 640 | std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator, |
|---|
| 641 | typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator> |
|---|
| 642 | edges(const adjacency_matrix<D,VP,EP,GP,A>& g_) |
|---|
| 643 | { |
|---|
| 644 | typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
|---|
| 645 | Graph& g = const_cast<Graph&>(g_); |
|---|
| 646 | |
|---|
| 647 | typename Graph::unfiltered_edge_iter |
|---|
| 648 | first(g.m_matrix.begin(), g.m_matrix.begin(), |
|---|
| 649 | g.m_vertex_set.size()), |
|---|
| 650 | last(g.m_matrix.end(), g.m_matrix.begin(), |
|---|
| 651 | g.m_vertex_set.size()); |
|---|
| 652 | detail::does_edge_exist pred; |
|---|
| 653 | typedef typename Graph::edge_iterator edge_iterator; |
|---|
| 654 | return std::make_pair(edge_iterator(pred, first, last), |
|---|
| 655 | edge_iterator(pred, last, last)); |
|---|
| 656 | } |
|---|
| 657 | |
|---|
| 658 | // O(1) |
|---|
| 659 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 660 | typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type |
|---|
| 661 | num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 662 | { |
|---|
| 663 | return g.m_num_edges; |
|---|
| 664 | } |
|---|
| 665 | |
|---|
| 666 | //========================================================================= |
|---|
| 667 | // Functions required by the MutableGraph concept |
|---|
| 668 | |
|---|
| 669 | // O(1) |
|---|
| 670 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 671 | std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool> |
|---|
| 672 | add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 673 | typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, |
|---|
| 674 | const EP& ep, |
|---|
| 675 | adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 676 | { |
|---|
| 677 | typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor |
|---|
| 678 | edge_descriptor; |
|---|
| 679 | if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) { |
|---|
| 680 | ++(g.m_num_edges); |
|---|
| 681 | detail::set_property(g.get_edge(u,v), ep, 0); |
|---|
| 682 | detail::set_edge_exists(g.get_edge(u,v), true, 0); |
|---|
| 683 | return std::make_pair |
|---|
| 684 | (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))), |
|---|
| 685 | true); |
|---|
| 686 | } else |
|---|
| 687 | return std::make_pair |
|---|
| 688 | (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))), |
|---|
| 689 | false); |
|---|
| 690 | } |
|---|
| 691 | // O(1) |
|---|
| 692 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 693 | std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool> |
|---|
| 694 | add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 695 | typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, |
|---|
| 696 | adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 697 | { |
|---|
| 698 | EP ep; |
|---|
| 699 | return add_edge(u, v, ep, g); |
|---|
| 700 | } |
|---|
| 701 | |
|---|
| 702 | // O(1) |
|---|
| 703 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 704 | void |
|---|
| 705 | remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 706 | typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, |
|---|
| 707 | adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 708 | { |
|---|
| 709 | --(g.m_num_edges); |
|---|
| 710 | detail::set_edge_exists(g.get_edge(u,v), false, 0); |
|---|
| 711 | } |
|---|
| 712 | |
|---|
| 713 | // O(1) |
|---|
| 714 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 715 | void |
|---|
| 716 | remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e, |
|---|
| 717 | adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 718 | { |
|---|
| 719 | remove_edge(source(e, g), target(e, g), g); |
|---|
| 720 | } |
|---|
| 721 | |
|---|
| 722 | |
|---|
| 723 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 724 | inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor |
|---|
| 725 | add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) { |
|---|
| 726 | // UNDER CONSTRUCTION |
|---|
| 727 | assert(false); |
|---|
| 728 | return *vertices(g).first; |
|---|
| 729 | } |
|---|
| 730 | |
|---|
| 731 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 732 | inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor |
|---|
| 733 | add_vertex(const VP& vp, adjacency_matrix<D,VP,EP,GP,A>& g) { |
|---|
| 734 | // UNDER CONSTRUCTION |
|---|
| 735 | assert(false); |
|---|
| 736 | return *vertices(g).first; |
|---|
| 737 | } |
|---|
| 738 | |
|---|
| 739 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 740 | inline void |
|---|
| 741 | remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 742 | adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 743 | { |
|---|
| 744 | // UNDER CONSTRUCTION |
|---|
| 745 | assert(false); |
|---|
| 746 | } |
|---|
| 747 | |
|---|
| 748 | // O(V) |
|---|
| 749 | template <typename VP, typename EP, typename GP, typename A> |
|---|
| 750 | void |
|---|
| 751 | clear_vertex |
|---|
| 752 | (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 753 | adjacency_matrix<directedS,VP,EP,GP,A>& g) |
|---|
| 754 | { |
|---|
| 755 | typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator |
|---|
| 756 | vi, vi_end; |
|---|
| 757 | for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
|---|
| 758 | remove_edge(u, *vi, g); |
|---|
| 759 | for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
|---|
| 760 | remove_edge(*vi, u, g); |
|---|
| 761 | } |
|---|
| 762 | |
|---|
| 763 | // O(V) |
|---|
| 764 | template <typename VP, typename EP, typename GP, typename A> |
|---|
| 765 | void |
|---|
| 766 | clear_vertex |
|---|
| 767 | (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, |
|---|
| 768 | adjacency_matrix<undirectedS,VP,EP,GP,A>& g) |
|---|
| 769 | { |
|---|
| 770 | typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator |
|---|
| 771 | vi, vi_end; |
|---|
| 772 | for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
|---|
| 773 | remove_edge(u, *vi, g); |
|---|
| 774 | } |
|---|
| 775 | |
|---|
| 776 | //========================================================================= |
|---|
| 777 | // Vertex Property Map |
|---|
| 778 | |
|---|
| 779 | template <typename GraphPtr, typename Vertex, typename T, typename R, |
|---|
| 780 | typename Tag> |
|---|
| 781 | class adj_matrix_vertex_property_map |
|---|
| 782 | : public put_get_helper<R, |
|---|
| 783 | adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> > |
|---|
| 784 | { |
|---|
| 785 | public: |
|---|
| 786 | typedef T value_type; |
|---|
| 787 | typedef R reference; |
|---|
| 788 | typedef Vertex key_type; |
|---|
| 789 | typedef boost::lvalue_property_map_tag category; |
|---|
| 790 | adj_matrix_vertex_property_map() { } |
|---|
| 791 | adj_matrix_vertex_property_map(GraphPtr g) : m_g(g) { } |
|---|
| 792 | inline reference operator[](key_type v) const { |
|---|
| 793 | return get_property_value(m_g->m_vertex_properties[v], Tag()); |
|---|
| 794 | } |
|---|
| 795 | GraphPtr m_g; |
|---|
| 796 | }; |
|---|
| 797 | |
|---|
| 798 | template <class Property, class Vertex> |
|---|
| 799 | struct adj_matrix_vertex_id_map |
|---|
| 800 | : public boost::put_get_helper<Vertex, |
|---|
| 801 | adj_matrix_vertex_id_map<Property, Vertex> > |
|---|
| 802 | { |
|---|
| 803 | typedef Vertex value_type; |
|---|
| 804 | typedef Vertex reference; |
|---|
| 805 | typedef Vertex key_type; |
|---|
| 806 | typedef boost::readable_property_map_tag category; |
|---|
| 807 | adj_matrix_vertex_id_map() { } |
|---|
| 808 | template <class Graph> |
|---|
| 809 | inline adj_matrix_vertex_id_map(const Graph&) { } |
|---|
| 810 | inline value_type operator[](key_type v) const { return v; } |
|---|
| 811 | }; |
|---|
| 812 | |
|---|
| 813 | namespace detail { |
|---|
| 814 | |
|---|
| 815 | struct adj_matrix_any_vertex_pa { |
|---|
| 816 | template <class Tag, class Graph, class Property> |
|---|
| 817 | struct bind_ { |
|---|
| 818 | typedef typename property_value<Property,Tag>::type Value; |
|---|
| 819 | typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; |
|---|
| 820 | |
|---|
| 821 | typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&, |
|---|
| 822 | Tag> type; |
|---|
| 823 | typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value, |
|---|
| 824 | const Value&, Tag> const_type; |
|---|
| 825 | }; |
|---|
| 826 | }; |
|---|
| 827 | struct adj_matrix_id_vertex_pa { |
|---|
| 828 | template <class Tag, class Graph, class Property> |
|---|
| 829 | struct bind_ { |
|---|
| 830 | typedef typename Graph::vertex_descriptor Vertex; |
|---|
| 831 | typedef adj_matrix_vertex_id_map<Property, Vertex> type; |
|---|
| 832 | typedef adj_matrix_vertex_id_map<Property, Vertex> const_type; |
|---|
| 833 | }; |
|---|
| 834 | }; |
|---|
| 835 | |
|---|
| 836 | template <class Tag> |
|---|
| 837 | struct adj_matrix_choose_vertex_pa_helper { |
|---|
| 838 | typedef adj_matrix_any_vertex_pa type; |
|---|
| 839 | }; |
|---|
| 840 | template <> |
|---|
| 841 | struct adj_matrix_choose_vertex_pa_helper<vertex_index_t> { |
|---|
| 842 | typedef adj_matrix_id_vertex_pa type; |
|---|
| 843 | }; |
|---|
| 844 | |
|---|
| 845 | template <class Tag, class Graph, class Property> |
|---|
| 846 | struct adj_matrix_choose_vertex_pa { |
|---|
| 847 | typedef typename adj_matrix_choose_vertex_pa_helper<Tag>::type Helper; |
|---|
| 848 | typedef typename Helper::template bind_<Tag,Graph,Property> Bind; |
|---|
| 849 | typedef typename Bind::type type; |
|---|
| 850 | typedef typename Bind::const_type const_type; |
|---|
| 851 | }; |
|---|
| 852 | |
|---|
| 853 | struct adj_matrix_vertex_property_selector { |
|---|
| 854 | template <class Graph, class Property, class Tag> |
|---|
| 855 | struct bind_ { |
|---|
| 856 | typedef adj_matrix_choose_vertex_pa<Tag,Graph,Property> Choice; |
|---|
| 857 | typedef typename Choice::type type; |
|---|
| 858 | typedef typename Choice::const_type const_type; |
|---|
| 859 | }; |
|---|
| 860 | }; |
|---|
| 861 | |
|---|
| 862 | } // namespace detail |
|---|
| 863 | |
|---|
| 864 | template <> |
|---|
| 865 | struct vertex_property_selector<adjacency_matrix_class_tag> { |
|---|
| 866 | typedef detail::adj_matrix_vertex_property_selector type; |
|---|
| 867 | }; |
|---|
| 868 | |
|---|
| 869 | //========================================================================= |
|---|
| 870 | // Edge Property Map |
|---|
| 871 | |
|---|
| 872 | |
|---|
| 873 | template <typename Directed, typename Property, typename Vertex, |
|---|
| 874 | typename T, typename R, typename Tag> |
|---|
| 875 | class adj_matrix_edge_property_map |
|---|
| 876 | : public put_get_helper<R, |
|---|
| 877 | adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> > |
|---|
| 878 | { |
|---|
| 879 | public: |
|---|
| 880 | typedef T value_type; |
|---|
| 881 | typedef R reference; |
|---|
| 882 | typedef detail::matrix_edge_desc_impl<Directed, Vertex> key_type; |
|---|
| 883 | typedef boost::lvalue_property_map_tag category; |
|---|
| 884 | inline reference operator[](key_type e) const { |
|---|
| 885 | Property& p = *(Property*)e.get_property(); |
|---|
| 886 | return get_property_value(p, Tag()); |
|---|
| 887 | } |
|---|
| 888 | }; |
|---|
| 889 | struct adj_matrix_edge_property_selector { |
|---|
| 890 | template <class Graph, class Property, class Tag> |
|---|
| 891 | struct bind_ { |
|---|
| 892 | typedef typename property_value<Property,Tag>::type T; |
|---|
| 893 | typedef typename Graph::vertex_descriptor Vertex; |
|---|
| 894 | typedef adj_matrix_edge_property_map<typename Graph::directed_category, |
|---|
| 895 | Property, Vertex, T, T&, Tag> type; |
|---|
| 896 | typedef adj_matrix_edge_property_map<typename Graph::directed_category, |
|---|
| 897 | Property, Vertex, T, const T&, Tag> const_type; |
|---|
| 898 | }; |
|---|
| 899 | }; |
|---|
| 900 | template <> |
|---|
| 901 | struct edge_property_selector<adjacency_matrix_class_tag> { |
|---|
| 902 | typedef adj_matrix_edge_property_selector type; |
|---|
| 903 | }; |
|---|
| 904 | |
|---|
| 905 | //========================================================================= |
|---|
| 906 | // Functions required by PropertyGraph |
|---|
| 907 | |
|---|
| 908 | namespace detail { |
|---|
| 909 | |
|---|
| 910 | template <typename Property, typename D, typename VP, typename EP, |
|---|
| 911 | typename GP, typename A> |
|---|
| 912 | typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
|---|
| 913 | Property>::type |
|---|
| 914 | get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property, |
|---|
| 915 | vertex_property_tag) |
|---|
| 916 | { |
|---|
| 917 | typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
|---|
| 918 | typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
|---|
| 919 | Property>::type PA; |
|---|
| 920 | return PA(&g); |
|---|
| 921 | } |
|---|
| 922 | template <typename Property, typename D, typename VP, typename EP, |
|---|
| 923 | typename GP, typename A> |
|---|
| 924 | typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
|---|
| 925 | Property>::type |
|---|
| 926 | get_dispatch(adjacency_matrix<D,VP,EP,GP,A>&, Property, |
|---|
| 927 | edge_property_tag) |
|---|
| 928 | { |
|---|
| 929 | typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
|---|
| 930 | Property>::type PA; |
|---|
| 931 | return PA(); |
|---|
| 932 | } |
|---|
| 933 | template <typename Property, typename D, typename VP, typename EP, |
|---|
| 934 | typename GP, typename A> |
|---|
| 935 | typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
|---|
| 936 | Property>::const_type |
|---|
| 937 | get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>& g, Property, |
|---|
| 938 | vertex_property_tag) |
|---|
| 939 | { |
|---|
| 940 | typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
|---|
| 941 | typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
|---|
| 942 | Property>::const_type PA; |
|---|
| 943 | return PA(&g); |
|---|
| 944 | } |
|---|
| 945 | template <typename Property, typename D, typename VP, typename EP, |
|---|
| 946 | typename GP, typename A> |
|---|
| 947 | typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
|---|
| 948 | Property>::const_type |
|---|
| 949 | get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>&, Property, |
|---|
| 950 | edge_property_tag) |
|---|
| 951 | { |
|---|
| 952 | typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
|---|
| 953 | Property>::const_type PA; |
|---|
| 954 | return PA(); |
|---|
| 955 | } |
|---|
| 956 | |
|---|
| 957 | } // namespace detail |
|---|
| 958 | |
|---|
| 959 | template <typename Property, typename D, typename VP, typename EP, |
|---|
| 960 | typename GP, typename A> |
|---|
| 961 | inline |
|---|
| 962 | typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::type |
|---|
| 963 | get(Property p, adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 964 | { |
|---|
| 965 | typedef typename property_kind<Property>::type Kind; |
|---|
| 966 | return detail::get_dispatch(g, p, Kind()); |
|---|
| 967 | } |
|---|
| 968 | |
|---|
| 969 | template <typename Property, typename D, typename VP, typename EP, |
|---|
| 970 | typename GP, typename A> |
|---|
| 971 | inline |
|---|
| 972 | typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type |
|---|
| 973 | get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 974 | { |
|---|
| 975 | typedef typename property_kind<Property>::type Kind; |
|---|
| 976 | return detail::get_dispatch(g, p, Kind()); |
|---|
| 977 | } |
|---|
| 978 | |
|---|
| 979 | template <typename Property, typename D, typename VP, typename EP, |
|---|
| 980 | typename GP, typename A, typename Key> |
|---|
| 981 | inline |
|---|
| 982 | typename property_traits< |
|---|
| 983 | typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type |
|---|
| 984 | >::value_type |
|---|
| 985 | get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g, |
|---|
| 986 | const Key& key) |
|---|
| 987 | { |
|---|
| 988 | return get(get(p, g), key); |
|---|
| 989 | } |
|---|
| 990 | |
|---|
| 991 | template <typename Property, typename D, typename VP, typename EP, |
|---|
| 992 | typename GP, typename A, typename Key, typename Value> |
|---|
| 993 | inline void |
|---|
| 994 | put(Property p, adjacency_matrix<D,VP,EP,GP,A>& g, |
|---|
| 995 | const Key& key, const Value& value) |
|---|
| 996 | { |
|---|
| 997 | typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
|---|
| 998 | typedef typename boost::property_map<Graph, Property>::type Map; |
|---|
| 999 | Map pmap = get(p, g); |
|---|
| 1000 | put(pmap, key, value); |
|---|
| 1001 | } |
|---|
| 1002 | |
|---|
| 1003 | //========================================================================= |
|---|
| 1004 | // Other Functions |
|---|
| 1005 | |
|---|
| 1006 | template <typename D, typename VP, typename EP, typename GP, typename A> |
|---|
| 1007 | typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor |
|---|
| 1008 | vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n, |
|---|
| 1009 | const adjacency_matrix<D,VP,EP,GP,A>& g) |
|---|
| 1010 | { |
|---|
| 1011 | return n; |
|---|
| 1012 | } |
|---|
| 1013 | |
|---|
| 1014 | // Support for bundled properties |
|---|
| 1015 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
|---|
| 1016 | template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, |
|---|
| 1017 | typename Allocator, typename T, typename Bundle> |
|---|
| 1018 | inline |
|---|
| 1019 | typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, |
|---|
| 1020 | T Bundle::*>::type |
|---|
| 1021 | get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g) |
|---|
| 1022 | { |
|---|
| 1023 | typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, |
|---|
| 1024 | T Bundle::*>::type |
|---|
| 1025 | result_type; |
|---|
| 1026 | return result_type(&g, p); |
|---|
| 1027 | } |
|---|
| 1028 | |
|---|
| 1029 | template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, |
|---|
| 1030 | typename Allocator, typename T, typename Bundle> |
|---|
| 1031 | inline |
|---|
| 1032 | typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, |
|---|
| 1033 | T Bundle::*>::const_type |
|---|
| 1034 | get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g) |
|---|
| 1035 | { |
|---|
| 1036 | typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, |
|---|
| 1037 | T Bundle::*>::const_type |
|---|
| 1038 | result_type; |
|---|
| 1039 | return result_type(&g, p); |
|---|
| 1040 | } |
|---|
| 1041 | |
|---|
| 1042 | template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, |
|---|
| 1043 | typename Allocator, typename T, typename Bundle, typename Key> |
|---|
| 1044 | inline T |
|---|
| 1045 | get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g, |
|---|
| 1046 | const Key& key) |
|---|
| 1047 | { |
|---|
| 1048 | return get(get(p, g), key); |
|---|
| 1049 | } |
|---|
| 1050 | |
|---|
| 1051 | template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, |
|---|
| 1052 | typename Allocator, typename T, typename Bundle, typename Key> |
|---|
| 1053 | inline void |
|---|
| 1054 | put(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g, |
|---|
| 1055 | const Key& key, const T& value) |
|---|
| 1056 | { |
|---|
| 1057 | put(get(p, g), key, value); |
|---|
| 1058 | } |
|---|
| 1059 | |
|---|
| 1060 | #endif |
|---|
| 1061 | |
|---|
| 1062 | } // namespace boost |
|---|
| 1063 | |
|---|
| 1064 | #endif // BOOST_ADJACENCY_MATRIX_HPP |
|---|
