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