| //======================================================================= | |
| // 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 <boost/assert.hpp> | |
| #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 | |
| BOOST_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 | |
| BOOST_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 | |
| BOOST_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 |