| //======================================================================= |
| // Copyright 2001 University of Notre Dame. |
| // Copyright 2006 Trustees of Indiana University |
| // Authors: Jeremy G. Siek and Douglas Gregor <dgregor@cs.indiana.edu> |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| |
| #ifndef BOOST_ADJACENCY_MATRIX_HPP |
| #define BOOST_ADJACENCY_MATRIX_HPP |
| |
| #include <boost/config.hpp> |
| #include <vector> |
| #include <memory> |
| #include <cassert> |
| #include <boost/limits.hpp> |
| #include <boost/iterator.hpp> |
| #include <boost/graph/graph_traits.hpp> |
| #include <boost/graph/graph_mutability_traits.hpp> |
| #include <boost/graph/graph_selectors.hpp> |
| #include <boost/mpl/if.hpp> |
| #include <boost/graph/adjacency_iterator.hpp> |
| #include <boost/graph/detail/edge.hpp> |
| #include <boost/iterator/iterator_adaptor.hpp> |
| #include <boost/iterator/filter_iterator.hpp> |
| #include <boost/range/irange.hpp> |
| #include <boost/graph/properties.hpp> |
| #include <boost/tuple/tuple.hpp> |
| #include <boost/static_assert.hpp> |
| #include <boost/type_traits/ice.hpp> |
| |
| namespace boost { |
| |
| namespace detail { |
| |
| template <class Directed, class Vertex> |
| class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex> |
| { |
| typedef edge_desc_impl<Directed,Vertex> Base; |
| public: |
| matrix_edge_desc_impl() { } |
| matrix_edge_desc_impl(bool exists, Vertex s, Vertex d, |
| const void* ep = 0) |
| : Base(s, d, ep), m_exists(exists) { } |
| bool exists() const { return m_exists; } |
| private: |
| bool m_exists; |
| }; |
| |
| struct does_edge_exist { |
| template <class Edge> |
| bool operator()(const Edge& e) const { return e.exists(); } |
| }; |
| |
| // Note to self... The int for get_edge_exists and set_edge exist helps |
| // make these calls unambiguous. |
| template <typename EdgeProperty> |
| bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) { |
| return stored_edge.first; |
| } |
| template <typename EdgeProperty> |
| void set_edge_exists( |
| std::pair<bool, EdgeProperty>& stored_edge, |
| bool flag, |
| int |
| ) { |
| stored_edge.first = flag; |
| } |
| |
| template <typename EdgeProxy> |
| bool get_edge_exists(const EdgeProxy& edge_proxy, ...) { |
| return edge_proxy; |
| } |
| template <typename EdgeProxy> |
| EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) { |
| edge_proxy = flag; |
| return edge_proxy; // just to avoid never used warning |
| } |
| |
| |
| // NOTE: These functions collide with the get_property function for |
| // accessing bundled graph properties. Be excplicit when using them. |
| template <typename EdgeProperty> |
| const EdgeProperty& |
| get_edge_property(const std::pair<bool, EdgeProperty>& stored_edge) { |
| return stored_edge.second; |
| } |
| template <typename EdgeProperty> |
| EdgeProperty& |
| get_edge_property(std::pair<bool, EdgeProperty>& stored_edge) { |
| return stored_edge.second; |
| } |
| |
| template <typename StoredEdgeProperty, typename EdgeProperty> |
| inline void |
| set_edge_property(std::pair<bool, StoredEdgeProperty>& stored_edge, |
| const EdgeProperty& ep, int) { |
| stored_edge.second = ep; |
| } |
| |
| inline const no_property& get_edge_property(const char&) { |
| static no_property s_prop; |
| return s_prop; |
| } |
| inline no_property& get_edge_property(char&) { |
| static no_property s_prop; |
| return s_prop; |
| } |
| template <typename EdgeProxy, typename EdgeProperty> |
| inline void set_edge_property(EdgeProxy, const EdgeProperty&, ...) {} |
| |
| //======================================================================= |
| // Directed Out Edge Iterator |
| |
| template < |
| typename VertexDescriptor, typename MatrixIter |
| , typename VerticesSizeType, typename EdgeDescriptor |
| > |
| struct dir_adj_matrix_out_edge_iter |
| : iterator_adaptor< |
| dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
| , MatrixIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , std::ptrdiff_t |
| > |
| { |
| typedef iterator_adaptor< |
| dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
| , MatrixIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , std::ptrdiff_t |
| > super_t; |
| |
| dir_adj_matrix_out_edge_iter() { } |
| |
| dir_adj_matrix_out_edge_iter( |
| const MatrixIter& i |
| , const VertexDescriptor& src |
| , const VerticesSizeType& n |
| ) |
| : super_t(i), m_src(src), m_targ(0), m_n(n) |
| { } |
| |
| void increment() { |
| ++this->base_reference(); |
| ++m_targ; |
| } |
| |
| inline EdgeDescriptor |
| dereference() const |
| { |
| return EdgeDescriptor(get_edge_exists(*this->base(), 0), |
| m_src, m_targ, |
| &get_edge_property(*this->base())); |
| } |
| VertexDescriptor m_src, m_targ; |
| VerticesSizeType m_n; |
| }; |
| |
| //======================================================================= |
| // Directed In Edge Iterator |
| |
| template < |
| typename VertexDescriptor, typename MatrixIter |
| , typename VerticesSizeType, typename EdgeDescriptor |
| > |
| struct dir_adj_matrix_in_edge_iter |
| : iterator_adaptor< |
| dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
| , MatrixIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , std::ptrdiff_t |
| > |
| { |
| typedef iterator_adaptor< |
| dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
| , MatrixIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , std::ptrdiff_t |
| > super_t; |
| |
| dir_adj_matrix_in_edge_iter() { } |
| |
| dir_adj_matrix_in_edge_iter( |
| const MatrixIter& i |
| , const MatrixIter& last |
| , const VertexDescriptor& tgt |
| , const VerticesSizeType& n |
| ) |
| : super_t(i), m_last(last), m_src(0), m_targ(tgt), m_n(n) |
| { } |
| |
| void increment() { |
| if (VerticesSizeType(m_last - this->base_reference()) >= m_n) { |
| this->base_reference() += m_n; |
| ++m_src; |
| } else { |
| this->base_reference() = m_last; |
| } |
| } |
| |
| inline EdgeDescriptor |
| dereference() const |
| { |
| return EdgeDescriptor(get_edge_exists(*this->base(), 0), |
| m_src, m_targ, |
| &get_edge_property(*this->base())); |
| } |
| MatrixIter m_last; |
| VertexDescriptor m_src, m_targ; |
| VerticesSizeType m_n; |
| }; |
| |
| //======================================================================= |
| // Undirected Out Edge Iterator |
| |
| template < |
| typename VertexDescriptor, typename MatrixIter |
| , typename VerticesSizeType, typename EdgeDescriptor |
| > |
| struct undir_adj_matrix_out_edge_iter |
| : iterator_adaptor< |
| undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
| , MatrixIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , std::ptrdiff_t |
| > |
| { |
| typedef iterator_adaptor< |
| undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
| , MatrixIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , std::ptrdiff_t |
| > super_t; |
| |
| undir_adj_matrix_out_edge_iter() { } |
| |
| undir_adj_matrix_out_edge_iter( |
| const MatrixIter& i |
| , const VertexDescriptor& src |
| , const VerticesSizeType& n |
| ) |
| : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n) |
| {} |
| |
| void increment() |
| { |
| if (m_targ < m_src) // first half |
| { |
| ++this->base_reference(); |
| } |
| else if (m_targ < m_n - 1) |
| { // second half |
| ++m_inc; |
| this->base_reference() += m_inc; |
| } |
| else |
| { // past-the-end |
| this->base_reference() += m_n - m_src; |
| } |
| ++m_targ; |
| } |
| |
| inline EdgeDescriptor |
| dereference() const |
| { |
| return EdgeDescriptor(get_edge_exists(*this->base(), 0), |
| m_src, m_targ, |
| &get_edge_property(*this->base())); |
| } |
| |
| VertexDescriptor m_src, m_inc, m_targ; |
| VerticesSizeType m_n; |
| }; |
| |
| //======================================================================= |
| // Undirected In Edge Iterator |
| |
| template < |
| typename VertexDescriptor, typename MatrixIter |
| , typename VerticesSizeType, typename EdgeDescriptor |
| > |
| struct undir_adj_matrix_in_edge_iter |
| : iterator_adaptor< |
| undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
| , MatrixIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , std::ptrdiff_t |
| > |
| { |
| typedef iterator_adaptor< |
| undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor> |
| , MatrixIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , std::ptrdiff_t |
| > super_t; |
| |
| undir_adj_matrix_in_edge_iter() { } |
| |
| undir_adj_matrix_in_edge_iter( |
| const MatrixIter& i |
| , const VertexDescriptor& src |
| , const VerticesSizeType& n |
| ) |
| : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n) |
| {} |
| |
| void increment() |
| { |
| if (m_targ < m_src) // first half |
| { |
| ++this->base_reference(); |
| } |
| else if (m_targ < m_n - 1) |
| { // second half |
| ++m_inc; |
| this->base_reference() += m_inc; |
| } |
| else |
| { // past-the-end |
| this->base_reference() += m_n - m_src; |
| } |
| ++m_targ; |
| } |
| |
| inline EdgeDescriptor |
| dereference() const |
| { |
| return EdgeDescriptor(get_edge_exists(*this->base(), 0), |
| m_targ, m_src, |
| &get_edge_property(*this->base())); |
| } |
| |
| VertexDescriptor m_src, m_inc, m_targ; |
| VerticesSizeType m_n; |
| }; |
| |
| //======================================================================= |
| // Edge Iterator |
| |
| template <typename Directed, typename MatrixIter, |
| typename VerticesSizeType, typename EdgeDescriptor> |
| struct adj_matrix_edge_iter |
| : iterator_adaptor< |
| adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor> |
| , MatrixIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , std::ptrdiff_t |
| > |
| { |
| typedef iterator_adaptor< |
| adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor> |
| , MatrixIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , std::ptrdiff_t |
| > super_t; |
| |
| adj_matrix_edge_iter() { } |
| |
| adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n) |
| : super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { } |
| |
| void increment() |
| { |
| increment_dispatch(this->base_reference(), Directed()); |
| } |
| |
| void increment_dispatch(MatrixIter& i, directedS) |
| { |
| ++i; |
| if (m_targ == m_n - 1) |
| { |
| m_targ = 0; |
| ++m_src; |
| } |
| else |
| { |
| ++m_targ; |
| } |
| } |
| |
| void increment_dispatch(MatrixIter& i, undirectedS) |
| { |
| ++i; |
| if (m_targ == m_src) |
| { |
| m_targ = 0; |
| ++m_src; |
| } |
| else |
| { |
| ++m_targ; |
| } |
| } |
| |
| inline EdgeDescriptor |
| dereference() const |
| { |
| return EdgeDescriptor(get_edge_exists(*this->base(), 0), |
| m_src, m_targ, |
| &get_edge_property(*this->base())); |
| } |
| |
| MatrixIter m_start; |
| VerticesSizeType m_src, m_targ, m_n; |
| }; |
| |
| } // namespace detail |
| |
| //========================================================================= |
| // Adjacency Matrix Traits |
| template <typename Directed = directedS> |
| class adjacency_matrix_traits { |
| typedef typename Directed::is_directed_t is_directed; |
| public: |
| // The bidirectionalS tag is not allowed with the adjacency_matrix |
| // graph type. Instead, use directedS, which also provides the |
| // functionality required for a Bidirectional Graph (in_edges, |
| // in_degree, etc.). |
| #if !defined(_MSC_VER) || _MSC_VER > 1300 |
| BOOST_STATIC_ASSERT(type_traits::ice_not<(is_same<Directed, bidirectionalS>::value)>::value); |
| #endif |
| |
| typedef typename mpl::if_<is_directed, |
| bidirectional_tag, undirected_tag>::type |
| directed_category; |
| |
| typedef disallow_parallel_edge_tag edge_parallel_category; |
| |
| typedef std::size_t vertex_descriptor; |
| |
| typedef detail::matrix_edge_desc_impl<directed_category, |
| vertex_descriptor> edge_descriptor; |
| }; |
| |
| struct adjacency_matrix_class_tag { }; |
| |
| struct adj_matrix_traversal_tag : |
| public virtual adjacency_matrix_tag, |
| public virtual vertex_list_graph_tag, |
| public virtual incidence_graph_tag, |
| public virtual adjacency_graph_tag, |
| public virtual edge_list_graph_tag { }; |
| |
| //========================================================================= |
| // Adjacency Matrix Class |
| template <typename Directed = directedS, |
| typename VertexProperty = no_property, |
| typename EdgeProperty = no_property, |
| typename GraphProperty = no_property, |
| typename Allocator = std::allocator<bool> > |
| class adjacency_matrix { |
| typedef adjacency_matrix self; |
| typedef adjacency_matrix_traits<Directed> Traits; |
| |
| public: |
| #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300 |
| // The bidirectionalS tag is not allowed with the adjacency_matrix |
| // graph type. Instead, use directedS, which also provides the |
| // functionality required for a Bidirectional Graph (in_edges, |
| // in_degree, etc.). |
| BOOST_STATIC_ASSERT(!(is_same<Directed, bidirectionalS>::value)); |
| #endif |
| |
| #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES) |
| typedef typename graph_detail::graph_prop<GraphProperty>::property graph_property_type; |
| typedef typename graph_detail::graph_prop<GraphProperty>::bundle graph_bundled; |
| |
| typedef typename graph_detail::vertex_prop<VertexProperty>::property vertex_property_type; |
| typedef typename graph_detail::vertex_prop<VertexProperty>::bundle vertex_bundled; |
| |
| typedef typename graph_detail::edge_prop<EdgeProperty>::property edge_property_type; |
| typedef typename graph_detail::edge_prop<EdgeProperty>::bundle edge_bundled; |
| #else |
| typedef GraphProperty graph_property_type; |
| typedef no_graph_bundle graph_bundled; |
| |
| typedef VertexProperty vertex_property_type; |
| typedef no_vertex_bundle vertex_bundled; |
| |
| typedef EdgeProperty edge_property_type; |
| typedef no_edge_bundle edge_bundled; |
| #endif |
| |
| public: // should be private |
| typedef typename mpl::if_<typename has_property<edge_property_type>::type, |
| std::pair<bool, edge_property_type>, char>::type StoredEdge; |
| #if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) || defined(BOOST_NO_STD_ALLOCATOR) |
| typedef std::vector<StoredEdge> Matrix; |
| #else |
| // This causes internal compiler error for MSVC |
| typedef typename Allocator::template rebind<StoredEdge>::other Alloc; |
| typedef std::vector<StoredEdge, Alloc> Matrix; |
| #endif |
| typedef typename Matrix::iterator MatrixIter; |
| typedef typename Matrix::size_type size_type; |
| public: |
| // Graph concept required types |
| typedef typename Traits::vertex_descriptor vertex_descriptor; |
| typedef typename Traits::edge_descriptor edge_descriptor; |
| typedef typename Traits::directed_category directed_category; |
| typedef typename Traits::edge_parallel_category edge_parallel_category; |
| typedef adj_matrix_traversal_tag traversal_category; |
| |
| static vertex_descriptor null_vertex() |
| { |
| return (std::numeric_limits<vertex_descriptor>::max)(); |
| } |
| |
| //private: if friends worked, these would be private |
| |
| typedef detail::dir_adj_matrix_out_edge_iter< |
| vertex_descriptor, MatrixIter, size_type, edge_descriptor |
| > DirOutEdgeIter; |
| |
| typedef detail::undir_adj_matrix_out_edge_iter< |
| vertex_descriptor, MatrixIter, size_type, edge_descriptor |
| > UnDirOutEdgeIter; |
| |
| typedef typename mpl::if_< |
| typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter |
| >::type unfiltered_out_edge_iter; |
| |
| typedef detail::dir_adj_matrix_in_edge_iter< |
| vertex_descriptor, MatrixIter, size_type, edge_descriptor |
| > DirInEdgeIter; |
| |
| typedef detail::undir_adj_matrix_in_edge_iter< |
| vertex_descriptor, MatrixIter, size_type, edge_descriptor |
| > UnDirInEdgeIter; |
| |
| typedef typename mpl::if_< |
| typename Directed::is_directed_t, DirInEdgeIter, UnDirInEdgeIter |
| >::type unfiltered_in_edge_iter; |
| |
| typedef detail::adj_matrix_edge_iter< |
| Directed, MatrixIter, size_type, edge_descriptor |
| > unfiltered_edge_iter; |
| |
| public: |
| |
| // IncidenceGraph concept required types |
| typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter> |
| out_edge_iterator; |
| |
| typedef size_type degree_size_type; |
| |
| // BidirectionalGraph required types |
| typedef filter_iterator<detail::does_edge_exist, unfiltered_in_edge_iter> |
| in_edge_iterator; |
| |
| // AdjacencyGraph required types |
| typedef typename adjacency_iterator_generator<self, |
| vertex_descriptor, out_edge_iterator>::type adjacency_iterator; |
| |
| // VertexListGraph required types |
| typedef size_type vertices_size_type; |
| typedef integer_range<vertex_descriptor> VertexList; |
| typedef typename VertexList::iterator vertex_iterator; |
| |
| // EdgeListGraph required types |
| typedef size_type edges_size_type; |
| typedef filter_iterator< |
| detail::does_edge_exist, unfiltered_edge_iter |
| > edge_iterator; |
| |
| // PropertyGraph required types |
| typedef adjacency_matrix_class_tag graph_tag; |
| |
| // Constructor required by MutableGraph |
| adjacency_matrix(vertices_size_type n_vertices, |
| const GraphProperty& p = GraphProperty()) |
| : m_matrix(Directed::is_directed ? |
| (n_vertices * n_vertices) |
| : (n_vertices * (n_vertices + 1) / 2)), |
| m_vertex_set(0, n_vertices), |
| m_vertex_properties(n_vertices), |
| m_num_edges(0), |
| m_property(p) { } |
| |
| template <typename EdgeIterator> |
| adjacency_matrix(EdgeIterator first, |
| EdgeIterator last, |
| vertices_size_type n_vertices, |
| const GraphProperty& p = GraphProperty()) |
| : m_matrix(Directed::is_directed ? |
| (n_vertices * n_vertices) |
| : (n_vertices * (n_vertices + 1) / 2)), |
| m_vertex_set(0, n_vertices), |
| m_vertex_properties(n_vertices), |
| m_num_edges(0), |
| m_property(p) |
| { |
| for (; first != last; ++first) { |
| add_edge(first->first, first->second, *this); |
| } |
| } |
| |
| template <typename EdgeIterator, typename EdgePropertyIterator> |
| adjacency_matrix(EdgeIterator first, |
| EdgeIterator last, |
| EdgePropertyIterator ep_iter, |
| vertices_size_type n_vertices, |
| const GraphProperty& p = GraphProperty()) |
| : m_matrix(Directed::is_directed ? |
| (n_vertices * n_vertices) |
| : (n_vertices * (n_vertices + 1) / 2)), |
| m_vertex_set(0, n_vertices), |
| m_vertex_properties(n_vertices), |
| m_num_edges(0), |
| m_property(p) |
| { |
| for (; first != last; ++first, ++ep_iter) { |
| add_edge(first->first, first->second, *ep_iter, *this); |
| } |
| } |
| |
| #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
| // Directly access a vertex or edge bundle |
| vertex_bundled& operator[](vertex_descriptor v) |
| { return get(vertex_bundle, *this)[v]; } |
| |
| const vertex_bundled& operator[](vertex_descriptor v) const |
| { return get(vertex_bundle, *this)[v]; } |
| |
| edge_bundled& operator[](edge_descriptor e) |
| { return get(edge_bundle, *this)[e]; } |
| |
| const edge_bundled& operator[](edge_descriptor e) const |
| { return get(edge_bundle, *this)[e]; } |
| |
| graph_bundled& operator[](graph_bundle_t) |
| { return get_property(*this); } |
| |
| const graph_bundled& operator[](graph_bundle_t) const |
| { return get_property(*this); } |
| #endif |
| |
| //private: if friends worked, these would be private |
| |
| typename Matrix::const_reference |
| get_edge(vertex_descriptor u, vertex_descriptor v) const { |
| if (Directed::is_directed) |
| return m_matrix[u * m_vertex_set.size() + v]; |
| else { |
| if (v > u) |
| std::swap(u, v); |
| return m_matrix[u * (u + 1)/2 + v]; |
| } |
| } |
| typename Matrix::reference |
| get_edge(vertex_descriptor u, vertex_descriptor v) { |
| if (Directed::is_directed) |
| return m_matrix[u * m_vertex_set.size() + v]; |
| else { |
| if (v > u) |
| std::swap(u, v); |
| return m_matrix[u * (u + 1)/2 + v]; |
| } |
| } |
| |
| Matrix m_matrix; |
| VertexList m_vertex_set; |
| std::vector<vertex_property_type> m_vertex_properties; |
| size_type m_num_edges; |
| graph_property_type m_property; |
| }; |
| |
| //========================================================================= |
| // Functions required by the AdjacencyMatrix concept |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, |
| bool> |
| edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
| typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, |
| const adjacency_matrix<D,VP,EP,GP,A>& g) |
| { |
| bool exists = detail::get_edge_exists(g.get_edge(u,v), 0); |
| typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor |
| e(exists, u, v, &detail::get_edge_property(g.get_edge(u,v))); |
| return std::make_pair(e, exists); |
| } |
| |
| //========================================================================= |
| // Functions required by the IncidenceGraph concept |
| |
| // O(1) |
| template <typename VP, typename EP, typename GP, typename A> |
| std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator, |
| typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator> |
| out_edges |
| (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, |
| const adjacency_matrix<directedS,VP,EP,GP,A>& g_) |
| { |
| typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph; |
| Graph& g = const_cast<Graph&>(g_); |
| typename Graph::vertices_size_type offset = u * g.m_vertex_set.size(); |
| typename Graph::MatrixIter f = g.m_matrix.begin() + offset; |
| typename Graph::MatrixIter l = f + g.m_vertex_set.size(); |
| typename Graph::unfiltered_out_edge_iter |
| first(f, u, g.m_vertex_set.size()) |
| , last(l, u, g.m_vertex_set.size()); |
| detail::does_edge_exist pred; |
| typedef typename Graph::out_edge_iterator out_edge_iterator; |
| return std::make_pair(out_edge_iterator(pred, first, last), |
| out_edge_iterator(pred, last, last)); |
| } |
| |
| // O(1) |
| template <typename VP, typename EP, typename GP, typename A> |
| std::pair< |
| typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator, |
| typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator> |
| out_edges |
| (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, |
| const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_) |
| { |
| typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph; |
| Graph& g = const_cast<Graph&>(g_); |
| typename Graph::vertices_size_type offset = u * (u + 1) / 2; |
| typename Graph::MatrixIter f = g.m_matrix.begin() + offset; |
| typename Graph::MatrixIter l = g.m_matrix.end(); |
| |
| typename Graph::unfiltered_out_edge_iter |
| first(f, u, g.m_vertex_set.size()) |
| , last(l, u, g.m_vertex_set.size()); |
| |
| detail::does_edge_exist pred; |
| typedef typename Graph::out_edge_iterator out_edge_iterator; |
| return std::make_pair(out_edge_iterator(pred, first, last), |
| out_edge_iterator(pred, last, last)); |
| } |
| |
| // O(N) |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type |
| out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
| const adjacency_matrix<D,VP,EP,GP,A>& g) |
| { |
| typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0; |
| typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l; |
| for (boost::tie(f, l) = out_edges(u, g); f != l; ++f) |
| ++n; |
| return n; |
| } |
| |
| // O(1) |
| template <typename D, typename VP, typename EP, typename GP, typename A, |
| typename Dir, typename Vertex> |
| typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor |
| source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e, |
| const adjacency_matrix<D,VP,EP,GP,A>&) |
| { |
| return e.m_source; |
| } |
| |
| // O(1) |
| template <typename D, typename VP, typename EP, typename GP, typename A, |
| typename Dir, typename Vertex> |
| typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor |
| target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e, |
| const adjacency_matrix<D,VP,EP,GP,A>&) |
| { |
| return e.m_target; |
| } |
| |
| //========================================================================= |
| // Functions required by the BidirectionalGraph concept |
| |
| // O(1) |
| template <typename VP, typename EP, typename GP, typename A> |
| std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator, |
| typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator> |
| in_edges |
| (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, |
| const adjacency_matrix<directedS,VP,EP,GP,A>& g_) |
| { |
| typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph; |
| Graph& g = const_cast<Graph&>(g_); |
| typename Graph::MatrixIter f = g.m_matrix.begin() + u; |
| typename Graph::MatrixIter l = g.m_matrix.end(); |
| typename Graph::unfiltered_in_edge_iter |
| first(f, l, u, g.m_vertex_set.size()) |
| , last(l, l, u, g.m_vertex_set.size()); |
| detail::does_edge_exist pred; |
| typedef typename Graph::in_edge_iterator in_edge_iterator; |
| return std::make_pair(in_edge_iterator(pred, first, last), |
| in_edge_iterator(pred, last, last)); |
| } |
| |
| // O(1) |
| template <typename VP, typename EP, typename GP, typename A> |
| std::pair< |
| typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator, |
| typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator> |
| in_edges |
| (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, |
| const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_) |
| { |
| typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph; |
| Graph& g = const_cast<Graph&>(g_); |
| typename Graph::vertices_size_type offset = u * (u + 1) / 2; |
| typename Graph::MatrixIter f = g.m_matrix.begin() + offset; |
| typename Graph::MatrixIter l = g.m_matrix.end(); |
| |
| typename Graph::unfiltered_in_edge_iter |
| first(f, u, g.m_vertex_set.size()) |
| , last(l, u, g.m_vertex_set.size()); |
| |
| detail::does_edge_exist pred; |
| typedef typename Graph::in_edge_iterator in_edge_iterator; |
| return std::make_pair(in_edge_iterator(pred, first, last), |
| in_edge_iterator(pred, last, last)); |
| } |
| |
| // O(N) |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type |
| in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
| const adjacency_matrix<D,VP,EP,GP,A>& g) |
| { |
| typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0; |
| typename adjacency_matrix<D,VP,EP,GP,A>::in_edge_iterator f, l; |
| for (boost::tie(f, l) = in_edges(u, g); f != l; ++f) |
| ++n; |
| return n; |
| } |
| |
| //========================================================================= |
| // Functions required by the AdjacencyGraph concept |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator, |
| typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator> |
| adjacent_vertices |
| (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
| const adjacency_matrix<D,VP,EP,GP,A>& g_) |
| { |
| typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
| const Graph& cg = static_cast<const Graph&>(g_); |
| Graph& g = const_cast<Graph&>(cg); |
| typedef typename Graph::adjacency_iterator adjacency_iterator; |
| typename Graph::out_edge_iterator first, last; |
| boost::tie(first, last) = out_edges(u, g); |
| return std::make_pair(adjacency_iterator(first, &g), |
| adjacency_iterator(last, &g)); |
| } |
| |
| //========================================================================= |
| // Functions required by the VertexListGraph concept |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator, |
| typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator> |
| vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) { |
| typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
| Graph& g = const_cast<Graph&>(g_); |
| return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end()); |
| } |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type |
| num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) { |
| return g.m_vertex_set.size(); |
| } |
| |
| //========================================================================= |
| // Functions required by the EdgeListGraph concept |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator, |
| typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator> |
| edges(const adjacency_matrix<D,VP,EP,GP,A>& g_) |
| { |
| typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
| Graph& g = const_cast<Graph&>(g_); |
| |
| typename Graph::unfiltered_edge_iter |
| first(g.m_matrix.begin(), g.m_matrix.begin(), |
| g.m_vertex_set.size()), |
| last(g.m_matrix.end(), g.m_matrix.begin(), |
| g.m_vertex_set.size()); |
| detail::does_edge_exist pred; |
| typedef typename Graph::edge_iterator edge_iterator; |
| return std::make_pair(edge_iterator(pred, first, last), |
| edge_iterator(pred, last, last)); |
| } |
| |
| // O(1) |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type |
| num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g) |
| { |
| return g.m_num_edges; |
| } |
| |
| //========================================================================= |
| // Functions required by the MutableGraph concept |
| |
| // O(1) |
| template <typename D, typename VP, typename EP, typename GP, typename A, |
| typename EP2> |
| std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool> |
| add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
| typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, |
| const EP2& ep, |
| adjacency_matrix<D,VP,EP,GP,A>& g) |
| { |
| typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor |
| edge_descriptor; |
| if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) { |
| ++(g.m_num_edges); |
| detail::set_edge_property(g.get_edge(u,v), EP(ep), 0); |
| detail::set_edge_exists(g.get_edge(u,v), true, 0); |
| return std::make_pair |
| (edge_descriptor(true, u, v, &detail::get_edge_property(g.get_edge(u,v))), |
| true); |
| } else |
| return std::make_pair |
| (edge_descriptor(true, u, v, &detail::get_edge_property(g.get_edge(u,v))), |
| false); |
| } |
| // O(1) |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool> |
| add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
| typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, |
| adjacency_matrix<D,VP,EP,GP,A>& g) |
| { |
| EP ep; |
| return add_edge(u, v, ep, g); |
| } |
| |
| // O(1) |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| void |
| remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, |
| typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, |
| adjacency_matrix<D,VP,EP,GP,A>& g) |
| { |
| // Don'remove the edge unless it already exists. |
| if(detail::get_edge_exists(g.get_edge(u,v), 0)) { |
| --(g.m_num_edges); |
| detail::set_edge_exists(g.get_edge(u,v), false, 0); |
| } |
| } |
| |
| // O(1) |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| void |
| remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e, |
| adjacency_matrix<D,VP,EP,GP,A>& g) |
| { |
| remove_edge(source(e, g), target(e, g), g); |
| } |
| |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor |
| add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) { |
| // UNDER CONSTRUCTION |
| assert(false); |
| return *vertices(g).first; |
| } |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A, |
| typename VP2> |
| inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor |
| add_vertex(const VP2& /*vp*/, adjacency_matrix<D,VP,EP,GP,A>& g) { |
| // UNDER CONSTRUCTION |
| assert(false); |
| return *vertices(g).first; |
| } |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| inline void |
| remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor /*u*/, |
| adjacency_matrix<D,VP,EP,GP,A>& /*g*/) |
| { |
| // UNDER CONSTRUCTION |
| assert(false); |
| } |
| |
| // O(V) |
| template <typename VP, typename EP, typename GP, typename A> |
| void |
| clear_vertex |
| (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u, |
| adjacency_matrix<directedS,VP,EP,GP,A>& g) |
| { |
| typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator |
| vi, vi_end; |
| for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
| remove_edge(u, *vi, g); |
| for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
| remove_edge(*vi, u, g); |
| } |
| |
| // O(V) |
| template <typename VP, typename EP, typename GP, typename A> |
| void |
| clear_vertex |
| (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u, |
| adjacency_matrix<undirectedS,VP,EP,GP,A>& g) |
| { |
| typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator |
| vi, vi_end; |
| for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
| remove_edge(u, *vi, g); |
| } |
| |
| //========================================================================= |
| // Functions required by the PropertyGraph concept |
| |
| // O(1) |
| template <typename D, typename VP, typename EP, typename GP, typename A, |
| typename Tag, typename Value> |
| inline void |
| set_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag, const Value& value) |
| { |
| get_property_value(g.m_property, Tag()) = value; |
| } |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A, |
| typename Tag> |
| inline typename graph_property<adjacency_matrix<D,VP,EP,GP,A>, Tag>::type& |
| get_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag) |
| { |
| return get_property_value(g.m_property, Tag()); |
| } |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A, |
| typename Tag> |
| inline const typename graph_property<adjacency_matrix<D,VP,EP,GP,A>, Tag>::type& |
| get_property(const adjacency_matrix<D,VP,EP,GP,A>& g, Tag) |
| { |
| return get_property_value(g.m_property, Tag()); |
| } |
| |
| //========================================================================= |
| // Vertex Property Map |
| |
| template <typename GraphPtr, typename Vertex, typename T, typename R, |
| typename Tag> |
| class adj_matrix_vertex_property_map |
| : public put_get_helper<R, |
| adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> > |
| { |
| public: |
| typedef T value_type; |
| typedef R reference; |
| typedef Vertex key_type; |
| typedef boost::lvalue_property_map_tag category; |
| adj_matrix_vertex_property_map() { } |
| adj_matrix_vertex_property_map(GraphPtr g) : m_g(g) { } |
| inline reference operator[](key_type v) const { |
| return get_property_value(m_g->m_vertex_properties[v], Tag()); |
| } |
| GraphPtr m_g; |
| }; |
| |
| template <class Property, class Vertex> |
| struct adj_matrix_vertex_id_map |
| : public boost::put_get_helper<Vertex, |
| adj_matrix_vertex_id_map<Property, Vertex> > |
| { |
| typedef Vertex value_type; |
| typedef Vertex reference; |
| typedef Vertex key_type; |
| typedef boost::readable_property_map_tag category; |
| adj_matrix_vertex_id_map() { } |
| template <class Graph> |
| inline adj_matrix_vertex_id_map(const Graph&) { } |
| inline value_type operator[](key_type v) const { return v; } |
| }; |
| |
| namespace detail { |
| |
| struct adj_matrix_any_vertex_pa { |
| template <class Tag, class Graph, class Property> |
| struct bind_ { |
| typedef typename property_value<Property,Tag>::type Value; |
| typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; |
| |
| typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&, |
| Tag> type; |
| typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value, |
| const Value&, Tag> const_type; |
| }; |
| }; |
| struct adj_matrix_id_vertex_pa { |
| template <class Tag, class Graph, class Property> |
| struct bind_ { |
| typedef typename Graph::vertex_descriptor Vertex; |
| typedef adj_matrix_vertex_id_map<Property, Vertex> type; |
| typedef adj_matrix_vertex_id_map<Property, Vertex> const_type; |
| }; |
| }; |
| |
| template <class Tag> |
| struct adj_matrix_choose_vertex_pa_helper { |
| typedef adj_matrix_any_vertex_pa type; |
| }; |
| template <> |
| struct adj_matrix_choose_vertex_pa_helper<vertex_index_t> { |
| typedef adj_matrix_id_vertex_pa type; |
| }; |
| |
| template <class Tag, class Graph, class Property> |
| struct adj_matrix_choose_vertex_pa { |
| typedef typename adj_matrix_choose_vertex_pa_helper<Tag>::type Helper; |
| typedef typename Helper::template bind_<Tag,Graph,Property> Bind; |
| typedef typename Bind::type type; |
| typedef typename Bind::const_type const_type; |
| }; |
| |
| struct adj_matrix_vertex_property_selector { |
| template <class Graph, class Property, class Tag> |
| struct bind_ { |
| typedef adj_matrix_choose_vertex_pa<Tag,Graph,Property> Choice; |
| typedef typename Choice::type type; |
| typedef typename Choice::const_type const_type; |
| }; |
| }; |
| |
| } // namespace detail |
| |
| template <> |
| struct vertex_property_selector<adjacency_matrix_class_tag> { |
| typedef detail::adj_matrix_vertex_property_selector type; |
| }; |
| |
| //========================================================================= |
| // Edge Property Map |
| |
| |
| template <typename Directed, typename Property, typename Vertex, |
| typename T, typename R, typename Tag> |
| class adj_matrix_edge_property_map |
| : public put_get_helper<R, |
| adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> > |
| { |
| public: |
| typedef T value_type; |
| typedef R reference; |
| typedef detail::matrix_edge_desc_impl<Directed, Vertex> key_type; |
| typedef boost::lvalue_property_map_tag category; |
| inline reference operator[](key_type e) const { |
| Property& p = *(Property*)e.get_property(); |
| return get_property_value(p, Tag()); |
| } |
| }; |
| struct adj_matrix_edge_property_selector { |
| template <class Graph, class Property, class Tag> |
| struct bind_ { |
| typedef typename property_value<Property,Tag>::type T; |
| typedef typename Graph::vertex_descriptor Vertex; |
| typedef adj_matrix_edge_property_map<typename Graph::directed_category, |
| Property, Vertex, T, T&, Tag> type; |
| typedef adj_matrix_edge_property_map<typename Graph::directed_category, |
| Property, Vertex, T, const T&, Tag> const_type; |
| }; |
| }; |
| template <> |
| struct edge_property_selector<adjacency_matrix_class_tag> { |
| typedef adj_matrix_edge_property_selector type; |
| }; |
| |
| //========================================================================= |
| // Functions required by PropertyGraph |
| |
| namespace detail { |
| |
| template <typename Property, typename D, typename VP, typename EP, |
| typename GP, typename A> |
| typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
| Property>::type |
| get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property, |
| vertex_property_tag) |
| { |
| typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
| typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
| Property>::type PA; |
| return PA(&g); |
| } |
| template <typename Property, typename D, typename VP, typename EP, |
| typename GP, typename A> |
| typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
| Property>::type |
| get_dispatch(adjacency_matrix<D,VP,EP,GP,A>&, Property, |
| edge_property_tag) |
| { |
| typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
| Property>::type PA; |
| return PA(); |
| } |
| template <typename Property, typename D, typename VP, typename EP, |
| typename GP, typename A> |
| typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
| Property>::const_type |
| get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>& g, Property, |
| vertex_property_tag) |
| { |
| typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
| typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
| Property>::const_type PA; |
| return PA(&g); |
| } |
| template <typename Property, typename D, typename VP, typename EP, |
| typename GP, typename A> |
| typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
| Property>::const_type |
| get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>&, Property, |
| edge_property_tag) |
| { |
| typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, |
| Property>::const_type PA; |
| return PA(); |
| } |
| |
| } // namespace detail |
| |
| template <typename Property, typename D, typename VP, typename EP, |
| typename GP, typename A> |
| inline |
| typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::type |
| get(Property p, adjacency_matrix<D,VP,EP,GP,A>& g) |
| { |
| typedef typename property_kind<Property>::type Kind; |
| return detail::get_dispatch(g, p, Kind()); |
| } |
| |
| template <typename Property, typename D, typename VP, typename EP, |
| typename GP, typename A> |
| inline |
| typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type |
| get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g) |
| { |
| typedef typename property_kind<Property>::type Kind; |
| return detail::get_dispatch(g, p, Kind()); |
| } |
| |
| template <typename Property, typename D, typename VP, typename EP, |
| typename GP, typename A, typename Key> |
| inline |
| typename property_traits< |
| typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type |
| >::value_type |
| get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g, |
| const Key& key) |
| { |
| return get(get(p, g), key); |
| } |
| |
| template <typename Property, typename D, typename VP, typename EP, |
| typename GP, typename A, typename Key, typename Value> |
| inline void |
| put(Property p, adjacency_matrix<D,VP,EP,GP,A>& g, |
| const Key& key, const Value& value) |
| { |
| typedef adjacency_matrix<D,VP,EP,GP,A> Graph; |
| typedef typename boost::property_map<Graph, Property>::type Map; |
| Map pmap = get(p, g); |
| put(pmap, key, value); |
| } |
| |
| //========================================================================= |
| // Other Functions |
| |
| template <typename D, typename VP, typename EP, typename GP, typename A> |
| typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor |
| vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n, |
| const adjacency_matrix<D,VP,EP,GP,A>&) |
| { |
| return n; |
| } |
| |
| // Support for bundled properties |
| #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
| template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, |
| typename Allocator, typename T, typename Bundle> |
| inline |
| typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, |
| T Bundle::*>::type |
| get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g) |
| { |
| typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, |
| T Bundle::*>::type |
| result_type; |
| return result_type(&g, p); |
| } |
| |
| template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, |
| typename Allocator, typename T, typename Bundle> |
| inline |
| typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, |
| T Bundle::*>::const_type |
| get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g) |
| { |
| typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, |
| T Bundle::*>::const_type |
| result_type; |
| return result_type(&g, p); |
| } |
| |
| template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, |
| typename Allocator, typename T, typename Bundle, typename Key> |
| inline T |
| get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g, |
| const Key& key) |
| { |
| return get(get(p, g), key); |
| } |
| |
| template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, |
| typename Allocator, typename T, typename Bundle, typename Key> |
| inline void |
| put(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g, |
| const Key& key, const T& value) |
| { |
| put(get(p, g), key, value); |
| } |
| |
| #endif |
| |
| #define ADJMAT_PARAMS \ |
| typename D, typename VP, typename EP, typename GP, typename A |
| #define ADJMAT adjacency_matrix<D,VP,EP,GP,A> |
| template <ADJMAT_PARAMS> |
| struct graph_mutability_traits<ADJMAT> { |
| typedef mutable_edge_property_graph_tag category; |
| }; |
| #undef ADJMAT_PARAMS |
| #undef ADJMAT |
| |
| |
| } // namespace boost |
| |
| #endif // BOOST_ADJACENCY_MATRIX_HPP |