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