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