1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/adjacency_matrix.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,1278 @@
1.4 +//=======================================================================
1.5 +// Copyright 2001 University of Notre Dame.
1.6 +// Copyright 2006 Trustees of Indiana University
1.7 +// Authors: Jeremy G. Siek and Douglas Gregor <dgregor@cs.indiana.edu>
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +
1.14 +#ifndef BOOST_ADJACENCY_MATRIX_HPP
1.15 +#define BOOST_ADJACENCY_MATRIX_HPP
1.16 +
1.17 +#include <boost/config.hpp>
1.18 +#include <vector>
1.19 +#include <memory>
1.20 +#include <cassert>
1.21 +#include <boost/limits.hpp>
1.22 +#include <boost/iterator.hpp>
1.23 +#include <boost/graph/graph_traits.hpp>
1.24 +#include <boost/graph/graph_selectors.hpp>
1.25 +#include <boost/pending/ct_if.hpp>
1.26 +#include <boost/graph/adjacency_iterator.hpp>
1.27 +#include <boost/graph/detail/edge.hpp>
1.28 +#include <boost/iterator/iterator_adaptor.hpp>
1.29 +#include <boost/iterator/filter_iterator.hpp>
1.30 +#include <boost/pending/integer_range.hpp>
1.31 +#include <boost/graph/properties.hpp>
1.32 +#include <boost/tuple/tuple.hpp>
1.33 +#include <boost/static_assert.hpp>
1.34 +#include <boost/type_traits/ice.hpp>
1.35 +
1.36 +namespace boost {
1.37 +
1.38 + namespace detail {
1.39 +
1.40 + template <class Directed, class Vertex>
1.41 + class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex>
1.42 + {
1.43 + typedef edge_desc_impl<Directed,Vertex> Base;
1.44 + public:
1.45 + matrix_edge_desc_impl() { }
1.46 + matrix_edge_desc_impl(bool exists, Vertex s, Vertex d,
1.47 + const void* ep = 0)
1.48 + : Base(s, d, ep), m_exists(exists) { }
1.49 + bool exists() const { return m_exists; }
1.50 + private:
1.51 + bool m_exists;
1.52 + };
1.53 +
1.54 + struct does_edge_exist {
1.55 + template <class Edge>
1.56 + bool operator()(const Edge& e) const { return e.exists(); }
1.57 + };
1.58 +
1.59 + template <typename EdgeProperty>
1.60 + bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) {
1.61 + return stored_edge.first;
1.62 + }
1.63 + template <typename EdgeProperty>
1.64 + void set_edge_exists(
1.65 + std::pair<bool, EdgeProperty>& stored_edge,
1.66 + bool flag,
1.67 + int
1.68 + ) {
1.69 + stored_edge.first = flag;
1.70 + }
1.71 +
1.72 + template <typename EdgeProxy>
1.73 + bool get_edge_exists(const EdgeProxy& edge_proxy, ...) {
1.74 + return edge_proxy;
1.75 + }
1.76 + template <typename EdgeProxy>
1.77 + EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) {
1.78 + edge_proxy = flag;
1.79 + return edge_proxy; // just to avoid never used warning
1.80 + }
1.81 +
1.82 +
1.83 +
1.84 + template <typename EdgeProperty>
1.85 + const EdgeProperty&
1.86 + get_property(const std::pair<bool, EdgeProperty>& stored_edge) {
1.87 + return stored_edge.second;
1.88 + }
1.89 + template <typename EdgeProperty>
1.90 + EdgeProperty&
1.91 + get_property(std::pair<bool, EdgeProperty>& stored_edge) {
1.92 + return stored_edge.second;
1.93 + }
1.94 +
1.95 + template <typename StoredEdgeProperty, typename EdgeProperty>
1.96 + inline void
1.97 + set_property(std::pair<bool, StoredEdgeProperty>& stored_edge,
1.98 + const EdgeProperty& ep, int) {
1.99 + stored_edge.second = ep;
1.100 + }
1.101 +
1.102 + inline const no_property& get_property(const char&) {
1.103 + static no_property s_prop;
1.104 + return s_prop;
1.105 + }
1.106 + inline no_property& get_property(char&) {
1.107 + static no_property s_prop;
1.108 + return s_prop;
1.109 + }
1.110 + template <typename EdgeProxy, typename EdgeProperty>
1.111 + inline void
1.112 + set_property(EdgeProxy, const EdgeProperty&, ...) {}
1.113 +
1.114 + //=======================================================================
1.115 + // Directed Out Edge Iterator
1.116 +
1.117 + template <
1.118 + typename VertexDescriptor, typename MatrixIter
1.119 + , typename VerticesSizeType, typename EdgeDescriptor
1.120 + >
1.121 + struct dir_adj_matrix_out_edge_iter
1.122 + : iterator_adaptor<
1.123 + dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
1.124 + , MatrixIter
1.125 + , EdgeDescriptor
1.126 + , use_default
1.127 + , EdgeDescriptor
1.128 + , std::ptrdiff_t
1.129 + >
1.130 + {
1.131 + typedef iterator_adaptor<
1.132 + dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
1.133 + , MatrixIter
1.134 + , EdgeDescriptor
1.135 + , use_default
1.136 + , EdgeDescriptor
1.137 + , std::ptrdiff_t
1.138 + > super_t;
1.139 +
1.140 + dir_adj_matrix_out_edge_iter() { }
1.141 +
1.142 + dir_adj_matrix_out_edge_iter(
1.143 + const MatrixIter& i
1.144 + , const VertexDescriptor& src
1.145 + , const VerticesSizeType& n
1.146 + )
1.147 + : super_t(i), m_src(src), m_targ(0), m_n(n)
1.148 + { }
1.149 +
1.150 + void increment() {
1.151 + ++this->base_reference();
1.152 + ++m_targ;
1.153 + }
1.154 +
1.155 + inline EdgeDescriptor
1.156 + dereference() const
1.157 + {
1.158 + return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ,
1.159 + &get_property(*this->base()));
1.160 + }
1.161 + VertexDescriptor m_src, m_targ;
1.162 + VerticesSizeType m_n;
1.163 + };
1.164 +
1.165 + //=======================================================================
1.166 + // Directed In Edge Iterator
1.167 +
1.168 + template <
1.169 + typename VertexDescriptor, typename MatrixIter
1.170 + , typename VerticesSizeType, typename EdgeDescriptor
1.171 + >
1.172 + struct dir_adj_matrix_in_edge_iter
1.173 + : iterator_adaptor<
1.174 + dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
1.175 + , MatrixIter
1.176 + , EdgeDescriptor
1.177 + , use_default
1.178 + , EdgeDescriptor
1.179 + , std::ptrdiff_t
1.180 + >
1.181 + {
1.182 + typedef iterator_adaptor<
1.183 + dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
1.184 + , MatrixIter
1.185 + , EdgeDescriptor
1.186 + , use_default
1.187 + , EdgeDescriptor
1.188 + , std::ptrdiff_t
1.189 + > super_t;
1.190 +
1.191 + dir_adj_matrix_in_edge_iter() { }
1.192 +
1.193 + dir_adj_matrix_in_edge_iter(
1.194 + const MatrixIter& i
1.195 + , const MatrixIter& last
1.196 + , const VertexDescriptor& tgt
1.197 + , const VerticesSizeType& n
1.198 + )
1.199 + : super_t(i), m_last(last), m_src(0), m_targ(tgt), m_n(n)
1.200 + { }
1.201 +
1.202 + void increment() {
1.203 + if (VerticesSizeType(m_last - this->base_reference()) >= m_n) {
1.204 + this->base_reference() += m_n;
1.205 + ++m_src;
1.206 + } else {
1.207 + this->base_reference() = m_last;
1.208 + }
1.209 + }
1.210 +
1.211 + inline EdgeDescriptor
1.212 + dereference() const
1.213 + {
1.214 + return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ,
1.215 + &get_property(*this->base()));
1.216 + }
1.217 + MatrixIter m_last;
1.218 + VertexDescriptor m_src, m_targ;
1.219 + VerticesSizeType m_n;
1.220 + };
1.221 +
1.222 + //=======================================================================
1.223 + // Undirected Out Edge Iterator
1.224 +
1.225 + template <
1.226 + typename VertexDescriptor, typename MatrixIter
1.227 + , typename VerticesSizeType, typename EdgeDescriptor
1.228 + >
1.229 + struct undir_adj_matrix_out_edge_iter
1.230 + : iterator_adaptor<
1.231 + undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
1.232 + , MatrixIter
1.233 + , EdgeDescriptor
1.234 + , use_default
1.235 + , EdgeDescriptor
1.236 + , std::ptrdiff_t
1.237 + >
1.238 + {
1.239 + typedef iterator_adaptor<
1.240 + undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
1.241 + , MatrixIter
1.242 + , EdgeDescriptor
1.243 + , use_default
1.244 + , EdgeDescriptor
1.245 + , std::ptrdiff_t
1.246 + > super_t;
1.247 +
1.248 + undir_adj_matrix_out_edge_iter() { }
1.249 +
1.250 + undir_adj_matrix_out_edge_iter(
1.251 + const MatrixIter& i
1.252 + , const VertexDescriptor& src
1.253 + , const VerticesSizeType& n
1.254 + )
1.255 + : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)
1.256 + {}
1.257 +
1.258 + void increment()
1.259 + {
1.260 + if (m_targ < m_src) // first half
1.261 + {
1.262 + ++this->base_reference();
1.263 + }
1.264 + else if (m_targ < m_n - 1)
1.265 + { // second half
1.266 + ++m_inc;
1.267 + this->base_reference() += m_inc;
1.268 + }
1.269 + else
1.270 + { // past-the-end
1.271 + this->base_reference() += m_n - m_src;
1.272 + }
1.273 + ++m_targ;
1.274 + }
1.275 +
1.276 + inline EdgeDescriptor
1.277 + dereference() const
1.278 + {
1.279 + return EdgeDescriptor(
1.280 + get_edge_exists(*this->base(), 0), m_src, m_targ
1.281 + , &get_property(*this->base())
1.282 + );
1.283 + }
1.284 +
1.285 + VertexDescriptor m_src, m_inc, m_targ;
1.286 + VerticesSizeType m_n;
1.287 + };
1.288 +
1.289 + //=======================================================================
1.290 + // Undirected In Edge Iterator
1.291 +
1.292 + template <
1.293 + typename VertexDescriptor, typename MatrixIter
1.294 + , typename VerticesSizeType, typename EdgeDescriptor
1.295 + >
1.296 + struct undir_adj_matrix_in_edge_iter
1.297 + : iterator_adaptor<
1.298 + undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
1.299 + , MatrixIter
1.300 + , EdgeDescriptor
1.301 + , use_default
1.302 + , EdgeDescriptor
1.303 + , std::ptrdiff_t
1.304 + >
1.305 + {
1.306 + typedef iterator_adaptor<
1.307 + undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
1.308 + , MatrixIter
1.309 + , EdgeDescriptor
1.310 + , use_default
1.311 + , EdgeDescriptor
1.312 + , std::ptrdiff_t
1.313 + > super_t;
1.314 +
1.315 + undir_adj_matrix_in_edge_iter() { }
1.316 +
1.317 + undir_adj_matrix_in_edge_iter(
1.318 + const MatrixIter& i
1.319 + , const VertexDescriptor& src
1.320 + , const VerticesSizeType& n
1.321 + )
1.322 + : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)
1.323 + {}
1.324 +
1.325 + void increment()
1.326 + {
1.327 + if (m_targ < m_src) // first half
1.328 + {
1.329 + ++this->base_reference();
1.330 + }
1.331 + else if (m_targ < m_n - 1)
1.332 + { // second half
1.333 + ++m_inc;
1.334 + this->base_reference() += m_inc;
1.335 + }
1.336 + else
1.337 + { // past-the-end
1.338 + this->base_reference() += m_n - m_src;
1.339 + }
1.340 + ++m_targ;
1.341 + }
1.342 +
1.343 + inline EdgeDescriptor
1.344 + dereference() const
1.345 + {
1.346 + return EdgeDescriptor(
1.347 + get_edge_exists(*this->base(), 0), m_targ, m_src
1.348 + , &get_property(*this->base())
1.349 + );
1.350 + }
1.351 +
1.352 + VertexDescriptor m_src, m_inc, m_targ;
1.353 + VerticesSizeType m_n;
1.354 + };
1.355 +
1.356 + //=======================================================================
1.357 + // Edge Iterator
1.358 +
1.359 + template <typename Directed, typename MatrixIter,
1.360 + typename VerticesSizeType, typename EdgeDescriptor>
1.361 + struct adj_matrix_edge_iter
1.362 + : iterator_adaptor<
1.363 + adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor>
1.364 + , MatrixIter
1.365 + , EdgeDescriptor
1.366 + , use_default
1.367 + , EdgeDescriptor
1.368 + , std::ptrdiff_t
1.369 + >
1.370 + {
1.371 + typedef iterator_adaptor<
1.372 + adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor>
1.373 + , MatrixIter
1.374 + , EdgeDescriptor
1.375 + , use_default
1.376 + , EdgeDescriptor
1.377 + , std::ptrdiff_t
1.378 + > super_t;
1.379 +
1.380 + adj_matrix_edge_iter() { }
1.381 +
1.382 + adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n)
1.383 + : super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { }
1.384 +
1.385 + void increment()
1.386 + {
1.387 + increment_dispatch(this->base_reference(), Directed());
1.388 + }
1.389 +
1.390 + void increment_dispatch(MatrixIter& i, directedS)
1.391 + {
1.392 + ++i;
1.393 + if (m_targ == m_n - 1)
1.394 + {
1.395 + m_targ = 0;
1.396 + ++m_src;
1.397 + }
1.398 + else
1.399 + {
1.400 + ++m_targ;
1.401 + }
1.402 + }
1.403 +
1.404 + void increment_dispatch(MatrixIter& i, undirectedS)
1.405 + {
1.406 + ++i;
1.407 + if (m_targ == m_src)
1.408 + {
1.409 + m_targ = 0;
1.410 + ++m_src;
1.411 + }
1.412 + else
1.413 + {
1.414 + ++m_targ;
1.415 + }
1.416 + }
1.417 +
1.418 + inline EdgeDescriptor
1.419 + dereference() const
1.420 + {
1.421 + return EdgeDescriptor(
1.422 + get_edge_exists(
1.423 + *this->base(), 0), m_src, m_targ, &get_property(*this->base())
1.424 + );
1.425 + }
1.426 +
1.427 + MatrixIter m_start;
1.428 + VerticesSizeType m_src, m_targ, m_n;
1.429 + };
1.430 +
1.431 + } // namespace detail
1.432 +
1.433 + //=========================================================================
1.434 + // Adjacency Matrix Traits
1.435 + template <typename Directed = directedS>
1.436 + class adjacency_matrix_traits {
1.437 + typedef typename Directed::is_directed_t is_directed;
1.438 + public:
1.439 + // The bidirectionalS tag is not allowed with the adjacency_matrix
1.440 + // graph type. Instead, use directedS, which also provides the
1.441 + // functionality required for a Bidirectional Graph (in_edges,
1.442 + // in_degree, etc.).
1.443 +#if !defined(_MSC_VER) || _MSC_VER > 1300
1.444 + BOOST_STATIC_ASSERT(type_traits::ice_not<(is_same<Directed, bidirectionalS>::value)>::value);
1.445 +#endif
1.446 +
1.447 + typedef typename boost::ct_if_t<is_directed,
1.448 + bidirectional_tag, undirected_tag>::type
1.449 + directed_category;
1.450 +
1.451 + typedef disallow_parallel_edge_tag edge_parallel_category;
1.452 +
1.453 + typedef std::size_t vertex_descriptor;
1.454 +
1.455 + typedef detail::matrix_edge_desc_impl<directed_category,
1.456 + vertex_descriptor> edge_descriptor;
1.457 + };
1.458 +
1.459 + struct adjacency_matrix_class_tag { };
1.460 +
1.461 + struct adj_matrix_traversal_tag :
1.462 + public virtual adjacency_matrix_tag,
1.463 + public virtual vertex_list_graph_tag,
1.464 + public virtual incidence_graph_tag,
1.465 + public virtual adjacency_graph_tag,
1.466 + public virtual edge_list_graph_tag { };
1.467 +
1.468 + //=========================================================================
1.469 + // Adjacency Matrix Class
1.470 + template <typename Directed = directedS,
1.471 + typename VertexProperty = no_property,
1.472 + typename EdgeProperty = no_property,
1.473 + typename GraphProperty = no_property,
1.474 + typename Allocator = std::allocator<bool> >
1.475 + class adjacency_matrix {
1.476 + typedef adjacency_matrix self;
1.477 + typedef adjacency_matrix_traits<Directed> Traits;
1.478 +
1.479 + public:
1.480 +#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1.481 + // The bidirectionalS tag is not allowed with the adjacency_matrix
1.482 + // graph type. Instead, use directedS, which also provides the
1.483 + // functionality required for a Bidirectional Graph (in_edges,
1.484 + // in_degree, etc.).
1.485 + BOOST_STATIC_ASSERT(!(is_same<Directed, bidirectionalS>::value));
1.486 +#endif
1.487 +
1.488 +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.489 + typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::type
1.490 + vertex_property_type;
1.491 + typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type
1.492 + edge_property_type;
1.493 +
1.494 + private:
1.495 + typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::retagged
1.496 + maybe_vertex_bundled;
1.497 +
1.498 + typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::retagged
1.499 + maybe_edge_bundled;
1.500 +
1.501 + public:
1.502 + // The types that are actually bundled
1.503 + typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),
1.504 + no_vertex_bundle,
1.505 + maybe_vertex_bundled>::type vertex_bundled;
1.506 + typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),
1.507 + no_edge_bundle,
1.508 + maybe_edge_bundled>::type edge_bundled;
1.509 +#else
1.510 + typedef EdgeProperty edge_property_type;
1.511 + typedef VertexProperty vertex_property_type;
1.512 + typedef no_vertex_bundle vertex_bundled;
1.513 + typedef no_edge_bundle edge_bundled;
1.514 +#endif
1.515 +
1.516 + public: // should be private
1.517 + typedef typename ct_if_t<typename has_property<edge_property_type>::type,
1.518 + std::pair<bool, edge_property_type>, char>::type StoredEdge;
1.519 +#if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) || defined(BOOST_NO_STD_ALLOCATOR)
1.520 + typedef std::vector<StoredEdge> Matrix;
1.521 +#else
1.522 + // This causes internal compiler error for MSVC
1.523 + typedef typename Allocator::template rebind<StoredEdge>::other Alloc;
1.524 + typedef std::vector<StoredEdge, Alloc> Matrix;
1.525 +#endif
1.526 + typedef typename Matrix::iterator MatrixIter;
1.527 + typedef typename Matrix::size_type size_type;
1.528 + public:
1.529 + // Graph concept required types
1.530 + typedef typename Traits::vertex_descriptor vertex_descriptor;
1.531 + typedef typename Traits::edge_descriptor edge_descriptor;
1.532 + typedef typename Traits::directed_category directed_category;
1.533 + typedef typename Traits::edge_parallel_category edge_parallel_category;
1.534 + typedef adj_matrix_traversal_tag traversal_category;
1.535 +
1.536 + static vertex_descriptor null_vertex()
1.537 + {
1.538 + return (std::numeric_limits<vertex_descriptor>::max)();
1.539 + }
1.540 +
1.541 + //private: if friends worked, these would be private
1.542 +
1.543 + typedef detail::dir_adj_matrix_out_edge_iter<
1.544 + vertex_descriptor, MatrixIter, size_type, edge_descriptor
1.545 + > DirOutEdgeIter;
1.546 +
1.547 + typedef detail::undir_adj_matrix_out_edge_iter<
1.548 + vertex_descriptor, MatrixIter, size_type, edge_descriptor
1.549 + > UnDirOutEdgeIter;
1.550 +
1.551 + typedef typename ct_if_t<
1.552 + typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter
1.553 + >::type unfiltered_out_edge_iter;
1.554 +
1.555 + typedef detail::dir_adj_matrix_in_edge_iter<
1.556 + vertex_descriptor, MatrixIter, size_type, edge_descriptor
1.557 + > DirInEdgeIter;
1.558 +
1.559 + typedef detail::undir_adj_matrix_in_edge_iter<
1.560 + vertex_descriptor, MatrixIter, size_type, edge_descriptor
1.561 + > UnDirInEdgeIter;
1.562 +
1.563 + typedef typename ct_if_t<
1.564 + typename Directed::is_directed_t, DirInEdgeIter, UnDirInEdgeIter
1.565 + >::type unfiltered_in_edge_iter;
1.566 +
1.567 + typedef detail::adj_matrix_edge_iter<
1.568 + Directed, MatrixIter, size_type, edge_descriptor
1.569 + > unfiltered_edge_iter;
1.570 +
1.571 + public:
1.572 +
1.573 + // IncidenceGraph concept required types
1.574 + typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter>
1.575 + out_edge_iterator;
1.576 +
1.577 + typedef size_type degree_size_type;
1.578 +
1.579 + // BidirectionalGraph required types
1.580 + typedef filter_iterator<detail::does_edge_exist, unfiltered_in_edge_iter>
1.581 + in_edge_iterator;
1.582 +
1.583 + // AdjacencyGraph required types
1.584 + typedef typename adjacency_iterator_generator<self,
1.585 + vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
1.586 +
1.587 + // VertexListGraph required types
1.588 + typedef size_type vertices_size_type;
1.589 + typedef integer_range<vertex_descriptor> VertexList;
1.590 + typedef typename VertexList::iterator vertex_iterator;
1.591 +
1.592 + // EdgeListGraph required types
1.593 + typedef size_type edges_size_type;
1.594 + typedef filter_iterator<
1.595 + detail::does_edge_exist, unfiltered_edge_iter
1.596 + > edge_iterator;
1.597 +
1.598 + // PropertyGraph required types
1.599 + typedef adjacency_matrix_class_tag graph_tag;
1.600 +
1.601 + // Constructor required by MutableGraph
1.602 + adjacency_matrix(vertices_size_type n_vertices)
1.603 + : m_matrix(Directed::is_directed ?
1.604 + (n_vertices * n_vertices)
1.605 + : (n_vertices * (n_vertices + 1) / 2)),
1.606 + m_vertex_set(0, n_vertices),
1.607 + m_vertex_properties(n_vertices),
1.608 + m_num_edges(0) { }
1.609 +
1.610 +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.611 + // Directly access a vertex or edge bundle
1.612 + vertex_bundled& operator[](vertex_descriptor v)
1.613 + { return get(vertex_bundle, *this)[v]; }
1.614 +
1.615 + const vertex_bundled& operator[](vertex_descriptor v) const
1.616 + { return get(vertex_bundle, *this)[v]; }
1.617 +
1.618 + edge_bundled& operator[](edge_descriptor e)
1.619 + { return get(edge_bundle, *this)[e]; }
1.620 +
1.621 + const edge_bundled& operator[](edge_descriptor e) const
1.622 + { return get(edge_bundle, *this)[e]; }
1.623 +#endif
1.624 +
1.625 + //private: if friends worked, these would be private
1.626 +
1.627 + typename Matrix::const_reference
1.628 + get_edge(vertex_descriptor u, vertex_descriptor v) const {
1.629 + if (Directed::is_directed)
1.630 + return m_matrix[u * m_vertex_set.size() + v];
1.631 + else {
1.632 + if (v > u)
1.633 + std::swap(u, v);
1.634 + return m_matrix[u * (u + 1)/2 + v];
1.635 + }
1.636 + }
1.637 + typename Matrix::reference
1.638 + get_edge(vertex_descriptor u, vertex_descriptor v) {
1.639 + if (Directed::is_directed)
1.640 + return m_matrix[u * m_vertex_set.size() + v];
1.641 + else {
1.642 + if (v > u)
1.643 + std::swap(u, v);
1.644 + return m_matrix[u * (u + 1)/2 + v];
1.645 + }
1.646 + }
1.647 +
1.648 + Matrix m_matrix;
1.649 + VertexList m_vertex_set;
1.650 + std::vector<vertex_property_type> m_vertex_properties;
1.651 + size_type m_num_edges;
1.652 + };
1.653 +
1.654 + //=========================================================================
1.655 + // Functions required by the AdjacencyMatrix concept
1.656 +
1.657 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.658 + std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor,
1.659 + bool>
1.660 + edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
1.661 + typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
1.662 + const adjacency_matrix<D,VP,EP,GP,A>& g)
1.663 + {
1.664 + bool exists = detail::get_edge_exists(g.get_edge(u,v), 0);
1.665 + typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
1.666 + e(exists, u, v, &detail::get_property(g.get_edge(u,v)));
1.667 + return std::make_pair(e, exists);
1.668 + }
1.669 +
1.670 + //=========================================================================
1.671 + // Functions required by the IncidenceGraph concept
1.672 +
1.673 + // O(1)
1.674 + template <typename VP, typename EP, typename GP, typename A>
1.675 + std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator,
1.676 + typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator>
1.677 + out_edges
1.678 + (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
1.679 + const adjacency_matrix<directedS,VP,EP,GP,A>& g_)
1.680 + {
1.681 + typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;
1.682 + Graph& g = const_cast<Graph&>(g_);
1.683 + typename Graph::vertices_size_type offset = u * g.m_vertex_set.size();
1.684 + typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
1.685 + typename Graph::MatrixIter l = f + g.m_vertex_set.size();
1.686 + typename Graph::unfiltered_out_edge_iter
1.687 + first(f, u, g.m_vertex_set.size())
1.688 + , last(l, u, g.m_vertex_set.size());
1.689 + detail::does_edge_exist pred;
1.690 + typedef typename Graph::out_edge_iterator out_edge_iterator;
1.691 + return std::make_pair(out_edge_iterator(pred, first, last),
1.692 + out_edge_iterator(pred, last, last));
1.693 + }
1.694 +
1.695 + // O(1)
1.696 + template <typename VP, typename EP, typename GP, typename A>
1.697 + std::pair<
1.698 + typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator,
1.699 + typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator>
1.700 + out_edges
1.701 + (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
1.702 + const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)
1.703 + {
1.704 + typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;
1.705 + Graph& g = const_cast<Graph&>(g_);
1.706 + typename Graph::vertices_size_type offset = u * (u + 1) / 2;
1.707 + typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
1.708 + typename Graph::MatrixIter l = g.m_matrix.end();
1.709 +
1.710 + typename Graph::unfiltered_out_edge_iter
1.711 + first(f, u, g.m_vertex_set.size())
1.712 + , last(l, u, g.m_vertex_set.size());
1.713 +
1.714 + detail::does_edge_exist pred;
1.715 + typedef typename Graph::out_edge_iterator out_edge_iterator;
1.716 + return std::make_pair(out_edge_iterator(pred, first, last),
1.717 + out_edge_iterator(pred, last, last));
1.718 + }
1.719 +
1.720 + // O(N)
1.721 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.722 + typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
1.723 + out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
1.724 + const adjacency_matrix<D,VP,EP,GP,A>& g)
1.725 + {
1.726 + typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;
1.727 + typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l;
1.728 + for (tie(f, l) = out_edges(u, g); f != l; ++f)
1.729 + ++n;
1.730 + return n;
1.731 + }
1.732 +
1.733 + // O(1)
1.734 + template <typename D, typename VP, typename EP, typename GP, typename A,
1.735 + typename Dir, typename Vertex>
1.736 + typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
1.737 + source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
1.738 + const adjacency_matrix<D,VP,EP,GP,A>&)
1.739 + {
1.740 + return e.m_source;
1.741 + }
1.742 +
1.743 + // O(1)
1.744 + template <typename D, typename VP, typename EP, typename GP, typename A,
1.745 + typename Dir, typename Vertex>
1.746 + typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
1.747 + target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
1.748 + const adjacency_matrix<D,VP,EP,GP,A>&)
1.749 + {
1.750 + return e.m_target;
1.751 + }
1.752 +
1.753 + //=========================================================================
1.754 + // Functions required by the BidirectionalGraph concept
1.755 +
1.756 + // O(1)
1.757 + template <typename VP, typename EP, typename GP, typename A>
1.758 + std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator,
1.759 + typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator>
1.760 + in_edges
1.761 + (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
1.762 + const adjacency_matrix<directedS,VP,EP,GP,A>& g_)
1.763 + {
1.764 + typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;
1.765 + Graph& g = const_cast<Graph&>(g_);
1.766 + typename Graph::MatrixIter f = g.m_matrix.begin() + u;
1.767 + typename Graph::MatrixIter l = g.m_matrix.end();
1.768 + typename Graph::unfiltered_in_edge_iter
1.769 + first(f, l, u, g.m_vertex_set.size())
1.770 + , last(l, l, u, g.m_vertex_set.size());
1.771 + detail::does_edge_exist pred;
1.772 + typedef typename Graph::in_edge_iterator in_edge_iterator;
1.773 + return std::make_pair(in_edge_iterator(pred, first, last),
1.774 + in_edge_iterator(pred, last, last));
1.775 + }
1.776 +
1.777 + // O(1)
1.778 + template <typename VP, typename EP, typename GP, typename A>
1.779 + std::pair<
1.780 + typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator,
1.781 + typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator>
1.782 + in_edges
1.783 + (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
1.784 + const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)
1.785 + {
1.786 + typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;
1.787 + Graph& g = const_cast<Graph&>(g_);
1.788 + typename Graph::vertices_size_type offset = u * (u + 1) / 2;
1.789 + typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
1.790 + typename Graph::MatrixIter l = g.m_matrix.end();
1.791 +
1.792 + typename Graph::unfiltered_in_edge_iter
1.793 + first(f, u, g.m_vertex_set.size())
1.794 + , last(l, u, g.m_vertex_set.size());
1.795 +
1.796 + detail::does_edge_exist pred;
1.797 + typedef typename Graph::in_edge_iterator in_edge_iterator;
1.798 + return std::make_pair(in_edge_iterator(pred, first, last),
1.799 + in_edge_iterator(pred, last, last));
1.800 + }
1.801 +
1.802 + // O(N)
1.803 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.804 + typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
1.805 + in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
1.806 + const adjacency_matrix<D,VP,EP,GP,A>& g)
1.807 + {
1.808 + typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;
1.809 + typename adjacency_matrix<D,VP,EP,GP,A>::in_edge_iterator f, l;
1.810 + for (tie(f, l) = in_edges(u, g); f != l; ++f)
1.811 + ++n;
1.812 + return n;
1.813 + }
1.814 +
1.815 + //=========================================================================
1.816 + // Functions required by the AdjacencyGraph concept
1.817 +
1.818 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.819 + std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator,
1.820 + typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator>
1.821 + adjacent_vertices
1.822 + (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
1.823 + const adjacency_matrix<D,VP,EP,GP,A>& g_)
1.824 + {
1.825 + typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
1.826 + const Graph& cg = static_cast<const Graph&>(g_);
1.827 + Graph& g = const_cast<Graph&>(cg);
1.828 + typedef typename Graph::adjacency_iterator adjacency_iterator;
1.829 + typename Graph::out_edge_iterator first, last;
1.830 + boost::tie(first, last) = out_edges(u, g);
1.831 + return std::make_pair(adjacency_iterator(first, &g),
1.832 + adjacency_iterator(last, &g));
1.833 + }
1.834 +
1.835 + //=========================================================================
1.836 + // Functions required by the VertexListGraph concept
1.837 +
1.838 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.839 + std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator,
1.840 + typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator>
1.841 + vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) {
1.842 + typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
1.843 + Graph& g = const_cast<Graph&>(g_);
1.844 + return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end());
1.845 + }
1.846 +
1.847 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.848 + typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type
1.849 + num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) {
1.850 + return g.m_vertex_set.size();
1.851 + }
1.852 +
1.853 + //=========================================================================
1.854 + // Functions required by the EdgeListGraph concept
1.855 +
1.856 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.857 + std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator,
1.858 + typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator>
1.859 + edges(const adjacency_matrix<D,VP,EP,GP,A>& g_)
1.860 + {
1.861 + typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
1.862 + Graph& g = const_cast<Graph&>(g_);
1.863 +
1.864 + typename Graph::unfiltered_edge_iter
1.865 + first(g.m_matrix.begin(), g.m_matrix.begin(),
1.866 + g.m_vertex_set.size()),
1.867 + last(g.m_matrix.end(), g.m_matrix.begin(),
1.868 + g.m_vertex_set.size());
1.869 + detail::does_edge_exist pred;
1.870 + typedef typename Graph::edge_iterator edge_iterator;
1.871 + return std::make_pair(edge_iterator(pred, first, last),
1.872 + edge_iterator(pred, last, last));
1.873 + }
1.874 +
1.875 + // O(1)
1.876 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.877 + typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type
1.878 + num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g)
1.879 + {
1.880 + return g.m_num_edges;
1.881 + }
1.882 +
1.883 + //=========================================================================
1.884 + // Functions required by the MutableGraph concept
1.885 +
1.886 + // O(1)
1.887 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.888 + std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
1.889 + add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
1.890 + typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
1.891 + const EP& ep,
1.892 + adjacency_matrix<D,VP,EP,GP,A>& g)
1.893 + {
1.894 + typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
1.895 + edge_descriptor;
1.896 + if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) {
1.897 + ++(g.m_num_edges);
1.898 + detail::set_property(g.get_edge(u,v), ep, 0);
1.899 + detail::set_edge_exists(g.get_edge(u,v), true, 0);
1.900 + return std::make_pair
1.901 + (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
1.902 + true);
1.903 + } else
1.904 + return std::make_pair
1.905 + (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
1.906 + false);
1.907 + }
1.908 + // O(1)
1.909 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.910 + std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
1.911 + add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
1.912 + typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
1.913 + adjacency_matrix<D,VP,EP,GP,A>& g)
1.914 + {
1.915 + EP ep;
1.916 + return add_edge(u, v, ep, g);
1.917 + }
1.918 +
1.919 + // O(1)
1.920 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.921 + void
1.922 + remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
1.923 + typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
1.924 + adjacency_matrix<D,VP,EP,GP,A>& g)
1.925 + {
1.926 + --(g.m_num_edges);
1.927 + detail::set_edge_exists(g.get_edge(u,v), false, 0);
1.928 + }
1.929 +
1.930 + // O(1)
1.931 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.932 + void
1.933 + remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e,
1.934 + adjacency_matrix<D,VP,EP,GP,A>& g)
1.935 + {
1.936 + remove_edge(source(e, g), target(e, g), g);
1.937 + }
1.938 +
1.939 +
1.940 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.941 + inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
1.942 + add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) {
1.943 + // UNDER CONSTRUCTION
1.944 + assert(false);
1.945 + return *vertices(g).first;
1.946 + }
1.947 +
1.948 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.949 + inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
1.950 + add_vertex(const VP& vp, adjacency_matrix<D,VP,EP,GP,A>& g) {
1.951 + // UNDER CONSTRUCTION
1.952 + assert(false);
1.953 + return *vertices(g).first;
1.954 + }
1.955 +
1.956 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.957 + inline void
1.958 + remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
1.959 + adjacency_matrix<D,VP,EP,GP,A>& g)
1.960 + {
1.961 + // UNDER CONSTRUCTION
1.962 + assert(false);
1.963 + }
1.964 +
1.965 + // O(V)
1.966 + template <typename VP, typename EP, typename GP, typename A>
1.967 + void
1.968 + clear_vertex
1.969 + (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
1.970 + adjacency_matrix<directedS,VP,EP,GP,A>& g)
1.971 + {
1.972 + typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator
1.973 + vi, vi_end;
1.974 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1.975 + remove_edge(u, *vi, g);
1.976 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1.977 + remove_edge(*vi, u, g);
1.978 + }
1.979 +
1.980 + // O(V)
1.981 + template <typename VP, typename EP, typename GP, typename A>
1.982 + void
1.983 + clear_vertex
1.984 + (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
1.985 + adjacency_matrix<undirectedS,VP,EP,GP,A>& g)
1.986 + {
1.987 + typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator
1.988 + vi, vi_end;
1.989 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1.990 + remove_edge(u, *vi, g);
1.991 + }
1.992 +
1.993 + //=========================================================================
1.994 + // Vertex Property Map
1.995 +
1.996 + template <typename GraphPtr, typename Vertex, typename T, typename R,
1.997 + typename Tag>
1.998 + class adj_matrix_vertex_property_map
1.999 + : public put_get_helper<R,
1.1000 + adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> >
1.1001 + {
1.1002 + public:
1.1003 + typedef T value_type;
1.1004 + typedef R reference;
1.1005 + typedef Vertex key_type;
1.1006 + typedef boost::lvalue_property_map_tag category;
1.1007 + adj_matrix_vertex_property_map() { }
1.1008 + adj_matrix_vertex_property_map(GraphPtr g) : m_g(g) { }
1.1009 + inline reference operator[](key_type v) const {
1.1010 + return get_property_value(m_g->m_vertex_properties[v], Tag());
1.1011 + }
1.1012 + GraphPtr m_g;
1.1013 + };
1.1014 +
1.1015 + template <class Property, class Vertex>
1.1016 + struct adj_matrix_vertex_id_map
1.1017 + : public boost::put_get_helper<Vertex,
1.1018 + adj_matrix_vertex_id_map<Property, Vertex> >
1.1019 + {
1.1020 + typedef Vertex value_type;
1.1021 + typedef Vertex reference;
1.1022 + typedef Vertex key_type;
1.1023 + typedef boost::readable_property_map_tag category;
1.1024 + adj_matrix_vertex_id_map() { }
1.1025 + template <class Graph>
1.1026 + inline adj_matrix_vertex_id_map(const Graph&) { }
1.1027 + inline value_type operator[](key_type v) const { return v; }
1.1028 + };
1.1029 +
1.1030 + namespace detail {
1.1031 +
1.1032 + struct adj_matrix_any_vertex_pa {
1.1033 + template <class Tag, class Graph, class Property>
1.1034 + struct bind_ {
1.1035 + typedef typename property_value<Property,Tag>::type Value;
1.1036 + typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
1.1037 +
1.1038 + typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&,
1.1039 + Tag> type;
1.1040 + typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value,
1.1041 + const Value&, Tag> const_type;
1.1042 + };
1.1043 + };
1.1044 + struct adj_matrix_id_vertex_pa {
1.1045 + template <class Tag, class Graph, class Property>
1.1046 + struct bind_ {
1.1047 + typedef typename Graph::vertex_descriptor Vertex;
1.1048 + typedef adj_matrix_vertex_id_map<Property, Vertex> type;
1.1049 + typedef adj_matrix_vertex_id_map<Property, Vertex> const_type;
1.1050 + };
1.1051 + };
1.1052 +
1.1053 + template <class Tag>
1.1054 + struct adj_matrix_choose_vertex_pa_helper {
1.1055 + typedef adj_matrix_any_vertex_pa type;
1.1056 + };
1.1057 + template <>
1.1058 + struct adj_matrix_choose_vertex_pa_helper<vertex_index_t> {
1.1059 + typedef adj_matrix_id_vertex_pa type;
1.1060 + };
1.1061 +
1.1062 + template <class Tag, class Graph, class Property>
1.1063 + struct adj_matrix_choose_vertex_pa {
1.1064 + typedef typename adj_matrix_choose_vertex_pa_helper<Tag>::type Helper;
1.1065 + typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
1.1066 + typedef typename Bind::type type;
1.1067 + typedef typename Bind::const_type const_type;
1.1068 + };
1.1069 +
1.1070 + struct adj_matrix_vertex_property_selector {
1.1071 + template <class Graph, class Property, class Tag>
1.1072 + struct bind_ {
1.1073 + typedef adj_matrix_choose_vertex_pa<Tag,Graph,Property> Choice;
1.1074 + typedef typename Choice::type type;
1.1075 + typedef typename Choice::const_type const_type;
1.1076 + };
1.1077 + };
1.1078 +
1.1079 + } // namespace detail
1.1080 +
1.1081 + template <>
1.1082 + struct vertex_property_selector<adjacency_matrix_class_tag> {
1.1083 + typedef detail::adj_matrix_vertex_property_selector type;
1.1084 + };
1.1085 +
1.1086 + //=========================================================================
1.1087 + // Edge Property Map
1.1088 +
1.1089 +
1.1090 + template <typename Directed, typename Property, typename Vertex,
1.1091 + typename T, typename R, typename Tag>
1.1092 + class adj_matrix_edge_property_map
1.1093 + : public put_get_helper<R,
1.1094 + adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> >
1.1095 + {
1.1096 + public:
1.1097 + typedef T value_type;
1.1098 + typedef R reference;
1.1099 + typedef detail::matrix_edge_desc_impl<Directed, Vertex> key_type;
1.1100 + typedef boost::lvalue_property_map_tag category;
1.1101 + inline reference operator[](key_type e) const {
1.1102 + Property& p = *(Property*)e.get_property();
1.1103 + return get_property_value(p, Tag());
1.1104 + }
1.1105 + };
1.1106 + struct adj_matrix_edge_property_selector {
1.1107 + template <class Graph, class Property, class Tag>
1.1108 + struct bind_ {
1.1109 + typedef typename property_value<Property,Tag>::type T;
1.1110 + typedef typename Graph::vertex_descriptor Vertex;
1.1111 + typedef adj_matrix_edge_property_map<typename Graph::directed_category,
1.1112 + Property, Vertex, T, T&, Tag> type;
1.1113 + typedef adj_matrix_edge_property_map<typename Graph::directed_category,
1.1114 + Property, Vertex, T, const T&, Tag> const_type;
1.1115 + };
1.1116 + };
1.1117 + template <>
1.1118 + struct edge_property_selector<adjacency_matrix_class_tag> {
1.1119 + typedef adj_matrix_edge_property_selector type;
1.1120 + };
1.1121 +
1.1122 + //=========================================================================
1.1123 + // Functions required by PropertyGraph
1.1124 +
1.1125 + namespace detail {
1.1126 +
1.1127 + template <typename Property, typename D, typename VP, typename EP,
1.1128 + typename GP, typename A>
1.1129 + typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1.1130 + Property>::type
1.1131 + get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property,
1.1132 + vertex_property_tag)
1.1133 + {
1.1134 + typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
1.1135 + typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1.1136 + Property>::type PA;
1.1137 + return PA(&g);
1.1138 + }
1.1139 + template <typename Property, typename D, typename VP, typename EP,
1.1140 + typename GP, typename A>
1.1141 + typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1.1142 + Property>::type
1.1143 + get_dispatch(adjacency_matrix<D,VP,EP,GP,A>&, Property,
1.1144 + edge_property_tag)
1.1145 + {
1.1146 + typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1.1147 + Property>::type PA;
1.1148 + return PA();
1.1149 + }
1.1150 + template <typename Property, typename D, typename VP, typename EP,
1.1151 + typename GP, typename A>
1.1152 + typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1.1153 + Property>::const_type
1.1154 + get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>& g, Property,
1.1155 + vertex_property_tag)
1.1156 + {
1.1157 + typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
1.1158 + typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1.1159 + Property>::const_type PA;
1.1160 + return PA(&g);
1.1161 + }
1.1162 + template <typename Property, typename D, typename VP, typename EP,
1.1163 + typename GP, typename A>
1.1164 + typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1.1165 + Property>::const_type
1.1166 + get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>&, Property,
1.1167 + edge_property_tag)
1.1168 + {
1.1169 + typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1.1170 + Property>::const_type PA;
1.1171 + return PA();
1.1172 + }
1.1173 +
1.1174 + } // namespace detail
1.1175 +
1.1176 + template <typename Property, typename D, typename VP, typename EP,
1.1177 + typename GP, typename A>
1.1178 + inline
1.1179 + typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::type
1.1180 + get(Property p, adjacency_matrix<D,VP,EP,GP,A>& g)
1.1181 + {
1.1182 + typedef typename property_kind<Property>::type Kind;
1.1183 + return detail::get_dispatch(g, p, Kind());
1.1184 + }
1.1185 +
1.1186 + template <typename Property, typename D, typename VP, typename EP,
1.1187 + typename GP, typename A>
1.1188 + inline
1.1189 + typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
1.1190 + get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g)
1.1191 + {
1.1192 + typedef typename property_kind<Property>::type Kind;
1.1193 + return detail::get_dispatch(g, p, Kind());
1.1194 + }
1.1195 +
1.1196 + template <typename Property, typename D, typename VP, typename EP,
1.1197 + typename GP, typename A, typename Key>
1.1198 + inline
1.1199 + typename property_traits<
1.1200 + typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
1.1201 + >::value_type
1.1202 + get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g,
1.1203 + const Key& key)
1.1204 + {
1.1205 + return get(get(p, g), key);
1.1206 + }
1.1207 +
1.1208 + template <typename Property, typename D, typename VP, typename EP,
1.1209 + typename GP, typename A, typename Key, typename Value>
1.1210 + inline void
1.1211 + put(Property p, adjacency_matrix<D,VP,EP,GP,A>& g,
1.1212 + const Key& key, const Value& value)
1.1213 + {
1.1214 + typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
1.1215 + typedef typename boost::property_map<Graph, Property>::type Map;
1.1216 + Map pmap = get(p, g);
1.1217 + put(pmap, key, value);
1.1218 + }
1.1219 +
1.1220 + //=========================================================================
1.1221 + // Other Functions
1.1222 +
1.1223 + template <typename D, typename VP, typename EP, typename GP, typename A>
1.1224 + typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
1.1225 + vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n,
1.1226 + const adjacency_matrix<D,VP,EP,GP,A>& g)
1.1227 + {
1.1228 + return n;
1.1229 + }
1.1230 +
1.1231 + // Support for bundled properties
1.1232 +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.1233 + template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1.1234 + typename Allocator, typename T, typename Bundle>
1.1235 + inline
1.1236 + typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1.1237 + T Bundle::*>::type
1.1238 + get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g)
1.1239 + {
1.1240 + typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1.1241 + T Bundle::*>::type
1.1242 + result_type;
1.1243 + return result_type(&g, p);
1.1244 + }
1.1245 +
1.1246 + template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1.1247 + typename Allocator, typename T, typename Bundle>
1.1248 + inline
1.1249 + typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1.1250 + T Bundle::*>::const_type
1.1251 + get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g)
1.1252 + {
1.1253 + typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1.1254 + T Bundle::*>::const_type
1.1255 + result_type;
1.1256 + return result_type(&g, p);
1.1257 + }
1.1258 +
1.1259 + template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1.1260 + typename Allocator, typename T, typename Bundle, typename Key>
1.1261 + inline T
1.1262 + get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g,
1.1263 + const Key& key)
1.1264 + {
1.1265 + return get(get(p, g), key);
1.1266 + }
1.1267 +
1.1268 + template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1.1269 + typename Allocator, typename T, typename Bundle, typename Key>
1.1270 + inline void
1.1271 + put(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g,
1.1272 + const Key& key, const T& value)
1.1273 + {
1.1274 + put(get(p, g), key, value);
1.1275 + }
1.1276 +
1.1277 +#endif
1.1278 +
1.1279 +} // namespace boost
1.1280 +
1.1281 +#endif // BOOST_ADJACENCY_MATRIX_HPP