1 //=======================================================================

     2 // Copyright 2001 University of Notre Dame.

     3 // Copyright 2006 Trustees of Indiana University

     4 // Authors: Jeremy G. Siek and Douglas Gregor <dgregor@cs.indiana.edu>

     5 //

     6 // Distributed under the Boost Software License, Version 1.0. (See

     7 // accompanying file LICENSE_1_0.txt or copy at

     8 // http://www.boost.org/LICENSE_1_0.txt)

     9 //=======================================================================

    10 

    11 #ifndef BOOST_ADJACENCY_MATRIX_HPP

    12 #define BOOST_ADJACENCY_MATRIX_HPP

    13 

    14 #include <boost/config.hpp>

    15 #include <vector>

    16 #include <memory>

    17 #include <cassert>

    18 #include <boost/limits.hpp>

    19 #include <boost/iterator.hpp>

    20 #include <boost/graph/graph_traits.hpp>

    21 #include <boost/graph/graph_selectors.hpp>

    22 #include <boost/pending/ct_if.hpp>

    23 #include <boost/graph/adjacency_iterator.hpp>

    24 #include <boost/graph/detail/edge.hpp>

    25 #include <boost/iterator/iterator_adaptor.hpp>

    26 #include <boost/iterator/filter_iterator.hpp>

    27 #include <boost/pending/integer_range.hpp>

    28 #include <boost/graph/properties.hpp>

    29 #include <boost/tuple/tuple.hpp>

    30 #include <boost/static_assert.hpp>

    31 #include <boost/type_traits/ice.hpp>

    32 

    33 namespace boost {

    34   

    35   namespace detail {

    36 

    37     template <class Directed, class Vertex>

    38     class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex>

    39     {

    40       typedef edge_desc_impl<Directed,Vertex> Base;

    41     public:

    42       matrix_edge_desc_impl() { }

    43       matrix_edge_desc_impl(bool exists, Vertex s, Vertex d, 

    44                             const void* ep = 0)

    45         : Base(s, d, ep), m_exists(exists) { }

    46       bool exists() const { return m_exists; }

    47     private:

    48       bool m_exists;

    49     };

    50 

    51     struct does_edge_exist {

    52       template <class Edge>

    53       bool operator()(const Edge& e) const { return e.exists(); }

    54     };

    55 

    56     template <typename EdgeProperty>

    57     bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) {

    58       return stored_edge.first;

    59     }

    60     template <typename EdgeProperty>

    61     void set_edge_exists(

    62         std::pair<bool, EdgeProperty>& stored_edge, 

    63         bool flag,

    64         int

    65         ) {

    66       stored_edge.first = flag;

    67     }

    68 

    69     template <typename EdgeProxy>

    70     bool get_edge_exists(const EdgeProxy& edge_proxy, ...) {

    71       return edge_proxy;

    72     }

    73     template <typename EdgeProxy>

    74     EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) {

    75       edge_proxy = flag;

    76       return edge_proxy; // just to avoid never used warning

    77     }

    78 

    79 

    80 

    81     template <typename EdgeProperty>

    82     const EdgeProperty&

    83     get_property(const std::pair<bool, EdgeProperty>& stored_edge) {

    84       return stored_edge.second;

    85     }

    86     template <typename EdgeProperty>

    87     EdgeProperty&

    88     get_property(std::pair<bool, EdgeProperty>& stored_edge) {

    89       return stored_edge.second;

    90     }

    91 

    92     template <typename StoredEdgeProperty, typename EdgeProperty>

    93     inline void

    94     set_property(std::pair<bool, StoredEdgeProperty>& stored_edge, 

    95                  const EdgeProperty& ep, int) {

    96       stored_edge.second = ep;

    97     }

    98 

    99     inline const no_property& get_property(const char&) {

   100       static no_property s_prop;

   101       return s_prop;

   102     }

   103     inline no_property& get_property(char&) {

   104       static no_property s_prop;

   105       return s_prop;

   106     }

   107     template <typename EdgeProxy, typename EdgeProperty>

   108     inline void

   109     set_property(EdgeProxy, const EdgeProperty&, ...) {}

   110     

   111     //=======================================================================

   112     // Directed Out Edge Iterator

   113 

   114     template <

   115         typename VertexDescriptor, typename MatrixIter

   116       , typename VerticesSizeType, typename EdgeDescriptor

   117     >

   118     struct dir_adj_matrix_out_edge_iter

   119       : iterator_adaptor<

   120             dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

   121           , MatrixIter

   122           , EdgeDescriptor

   123           , use_default

   124           , EdgeDescriptor

   125           , std::ptrdiff_t

   126         >

   127     {

   128         typedef iterator_adaptor<

   129             dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

   130           , MatrixIter

   131           , EdgeDescriptor

   132           , use_default

   133           , EdgeDescriptor

   134           , std::ptrdiff_t

   135         > super_t;

   136         

   137         dir_adj_matrix_out_edge_iter() { }

   138         

   139         dir_adj_matrix_out_edge_iter(

   140             const MatrixIter& i

   141           , const VertexDescriptor& src

   142           , const VerticesSizeType& n

   143            )

   144             : super_t(i), m_src(src), m_targ(0), m_n(n)

   145         { }

   146 

   147         void increment() {

   148             ++this->base_reference();

   149             ++m_targ;

   150         }

   151         

   152         inline EdgeDescriptor

   153         dereference() const 

   154         {

   155             return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ, 

   156                                   &get_property(*this->base()));

   157         }

   158         VertexDescriptor m_src, m_targ;

   159         VerticesSizeType m_n;

   160     };

   161 

   162     //=======================================================================

   163     // Directed In Edge Iterator

   164 

   165     template <

   166         typename VertexDescriptor, typename MatrixIter

   167       , typename VerticesSizeType, typename EdgeDescriptor

   168     >

   169     struct dir_adj_matrix_in_edge_iter

   170       : iterator_adaptor<

   171             dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

   172           , MatrixIter

   173           , EdgeDescriptor

   174           , use_default

   175           , EdgeDescriptor

   176           , std::ptrdiff_t

   177         >

   178     {

   179         typedef iterator_adaptor<

   180             dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

   181           , MatrixIter

   182           , EdgeDescriptor

   183           , use_default

   184           , EdgeDescriptor

   185           , std::ptrdiff_t

   186         > super_t;

   187         

   188         dir_adj_matrix_in_edge_iter() { }

   189         

   190         dir_adj_matrix_in_edge_iter(

   191             const MatrixIter& i

   192           , const MatrixIter& last

   193           , const VertexDescriptor& tgt

   194           , const VerticesSizeType& n

   195            )

   196           : super_t(i), m_last(last), m_src(0), m_targ(tgt), m_n(n)

   197         { }

   198 

   199         void increment() {

   200           if (VerticesSizeType(m_last - this->base_reference()) >= m_n) {

   201             this->base_reference() += m_n;

   202             ++m_src;

   203           } else {

   204             this->base_reference() = m_last;

   205           }

   206         }

   207         

   208         inline EdgeDescriptor

   209         dereference() const 

   210         {

   211             return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ, 

   212                                   &get_property(*this->base()));

   213         }

   214         MatrixIter m_last;

   215         VertexDescriptor m_src, m_targ;

   216         VerticesSizeType m_n;

   217     };

   218 

   219     //=======================================================================

   220     // Undirected Out Edge Iterator

   221 

   222     template <

   223         typename VertexDescriptor, typename MatrixIter

   224       , typename VerticesSizeType, typename EdgeDescriptor

   225     >

   226     struct undir_adj_matrix_out_edge_iter 

   227       : iterator_adaptor<

   228             undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

   229           , MatrixIter

   230           , EdgeDescriptor

   231           , use_default

   232           , EdgeDescriptor

   233           , std::ptrdiff_t

   234         >

   235     {

   236         typedef iterator_adaptor<

   237             undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

   238           , MatrixIter

   239           , EdgeDescriptor

   240           , use_default

   241           , EdgeDescriptor

   242           , std::ptrdiff_t

   243         > super_t;

   244         

   245         undir_adj_matrix_out_edge_iter() { }

   246         

   247         undir_adj_matrix_out_edge_iter(

   248             const MatrixIter& i

   249           , const VertexDescriptor& src

   250           , const VerticesSizeType& n

   251         )

   252           : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)

   253         {}

   254 

   255         void increment()

   256         {

   257             if (m_targ < m_src)     // first half

   258             {

   259                 ++this->base_reference();

   260             }

   261             else if (m_targ < m_n - 1)

   262             {                  // second half

   263                 ++m_inc;

   264                 this->base_reference() += m_inc;

   265             }

   266             else

   267             {                  // past-the-end

   268                 this->base_reference() += m_n - m_src;

   269             }

   270             ++m_targ;

   271         }

   272         

   273         inline EdgeDescriptor

   274         dereference() const 

   275         {

   276             return EdgeDescriptor(

   277                 get_edge_exists(*this->base(), 0), m_src, m_targ

   278               , &get_property(*this->base())

   279             );

   280         }

   281         

   282         VertexDescriptor m_src, m_inc, m_targ;

   283         VerticesSizeType m_n;

   284     };

   285 

   286     //=======================================================================

   287     // Undirected In Edge Iterator

   288 

   289     template <

   290         typename VertexDescriptor, typename MatrixIter

   291       , typename VerticesSizeType, typename EdgeDescriptor

   292     >

   293     struct undir_adj_matrix_in_edge_iter 

   294       : iterator_adaptor<

   295             undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

   296           , MatrixIter

   297           , EdgeDescriptor

   298           , use_default

   299           , EdgeDescriptor

   300           , std::ptrdiff_t

   301         >

   302     {

   303         typedef iterator_adaptor<

   304             undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

   305           , MatrixIter

   306           , EdgeDescriptor

   307           , use_default

   308           , EdgeDescriptor

   309           , std::ptrdiff_t

   310         > super_t;

   311         

   312         undir_adj_matrix_in_edge_iter() { }

   313         

   314         undir_adj_matrix_in_edge_iter(

   315             const MatrixIter& i

   316           , const VertexDescriptor& src

   317           , const VerticesSizeType& n

   318         )

   319           : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)

   320         {}

   321 

   322         void increment()

   323         {

   324             if (m_targ < m_src)     // first half

   325             {

   326                 ++this->base_reference();

   327             }

   328             else if (m_targ < m_n - 1)

   329             {                  // second half

   330                 ++m_inc;

   331                 this->base_reference() += m_inc;

   332             }

   333             else

   334             {                  // past-the-end

   335                 this->base_reference() += m_n - m_src;

   336             }

   337             ++m_targ;

   338         }

   339         

   340         inline EdgeDescriptor

   341         dereference() const 

   342         {

   343             return EdgeDescriptor(

   344                      get_edge_exists(*this->base(), 0), m_targ, m_src

   345               , &get_property(*this->base())

   346             );

   347         }

   348         

   349         VertexDescriptor m_src, m_inc, m_targ;

   350         VerticesSizeType m_n;

   351     };

   352 

   353     //=======================================================================

   354     // Edge Iterator

   355 

   356     template <typename Directed, typename MatrixIter, 

   357               typename VerticesSizeType, typename EdgeDescriptor>

   358     struct adj_matrix_edge_iter

   359       : iterator_adaptor<

   360             adj_matrix_edge_iter<Directed, MatrixIter,  VerticesSizeType, EdgeDescriptor>

   361           , MatrixIter

   362           , EdgeDescriptor

   363           , use_default

   364           , EdgeDescriptor

   365           , std::ptrdiff_t

   366         >

   367     {

   368         typedef iterator_adaptor<

   369             adj_matrix_edge_iter<Directed, MatrixIter,  VerticesSizeType, EdgeDescriptor>

   370           , MatrixIter

   371           , EdgeDescriptor

   372           , use_default

   373           , EdgeDescriptor

   374           , std::ptrdiff_t

   375         > super_t;

   376         

   377         adj_matrix_edge_iter() { }

   378         

   379         adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n) 

   380             : super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { }

   381 

   382         void increment()

   383         {

   384             increment_dispatch(this->base_reference(), Directed());

   385         }

   386         

   387         void increment_dispatch(MatrixIter& i, directedS)

   388         {

   389             ++i;

   390             if (m_targ == m_n - 1)

   391             {

   392                 m_targ = 0;

   393                 ++m_src;

   394             }

   395             else

   396             {

   397                 ++m_targ;

   398             }

   399         }

   400         

   401         void increment_dispatch(MatrixIter& i, undirectedS)

   402         {

   403             ++i;

   404             if (m_targ == m_src)

   405             {

   406                 m_targ = 0;

   407                 ++m_src;

   408             }

   409             else

   410             {

   411                 ++m_targ;

   412             }

   413         }

   414 

   415         inline EdgeDescriptor

   416         dereference() const 

   417         {

   418             return EdgeDescriptor(

   419                 get_edge_exists(

   420                     *this->base(), 0), m_src, m_targ, &get_property(*this->base())

   421             );

   422         }

   423       

   424         MatrixIter m_start;

   425         VerticesSizeType m_src, m_targ, m_n;

   426     };

   427 

   428   } // namespace detail

   429 

   430   //=========================================================================

   431   // Adjacency Matrix Traits

   432   template <typename Directed = directedS>

   433   class adjacency_matrix_traits {

   434     typedef typename Directed::is_directed_t is_directed;

   435   public:

   436     // The bidirectionalS tag is not allowed with the adjacency_matrix

   437     // graph type. Instead, use directedS, which also provides the

   438     // functionality required for a Bidirectional Graph (in_edges,

   439     // in_degree, etc.).

   440 #if !defined(_MSC_VER) || _MSC_VER > 1300

   441     BOOST_STATIC_ASSERT(type_traits::ice_not<(is_same<Directed, bidirectionalS>::value)>::value);

   442 #endif

   443 

   444     typedef typename boost::ct_if_t<is_directed,

   445                                     bidirectional_tag, undirected_tag>::type

   446       directed_category;

   447     

   448     typedef disallow_parallel_edge_tag edge_parallel_category;

   449     

   450     typedef std::size_t vertex_descriptor;

   451 

   452     typedef detail::matrix_edge_desc_impl<directed_category,

   453       vertex_descriptor> edge_descriptor;

   454   };

   455 

   456   struct adjacency_matrix_class_tag { };

   457 

   458   struct adj_matrix_traversal_tag :

   459     public virtual adjacency_matrix_tag,

   460     public virtual vertex_list_graph_tag,

   461     public virtual incidence_graph_tag,

   462     public virtual adjacency_graph_tag,

   463     public virtual edge_list_graph_tag { };

   464   

   465   //=========================================================================

   466   // Adjacency Matrix Class

   467   template <typename Directed = directedS,

   468             typename VertexProperty = no_property,

   469             typename EdgeProperty = no_property,

   470             typename GraphProperty = no_property,

   471             typename Allocator = std::allocator<bool> >

   472   class adjacency_matrix {

   473     typedef adjacency_matrix self;

   474     typedef adjacency_matrix_traits<Directed> Traits;

   475     

   476   public:

   477 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300

   478     // The bidirectionalS tag is not allowed with the adjacency_matrix

   479     // graph type. Instead, use directedS, which also provides the

   480     // functionality required for a Bidirectional Graph (in_edges,

   481     // in_degree, etc.).

   482     BOOST_STATIC_ASSERT(!(is_same<Directed, bidirectionalS>::value));

   483 #endif

   484 

   485 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

   486     typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::type

   487       vertex_property_type;

   488     typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type

   489       edge_property_type;

   490       

   491   private:

   492     typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::retagged

   493       maybe_vertex_bundled;

   494 

   495     typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::retagged

   496       maybe_edge_bundled;

   497     

   498   public:

   499     // The types that are actually bundled

   500     typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),

   501                            no_vertex_bundle,

   502                            maybe_vertex_bundled>::type vertex_bundled;

   503     typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),

   504                            no_edge_bundle,

   505                            maybe_edge_bundled>::type edge_bundled;

   506 #else

   507     typedef EdgeProperty     edge_property_type;

   508     typedef VertexProperty   vertex_property_type;

   509     typedef no_vertex_bundle vertex_bundled;

   510     typedef no_edge_bundle   edge_bundled;

   511 #endif

   512 

   513   public: // should be private

   514     typedef typename ct_if_t<typename has_property<edge_property_type>::type,

   515       std::pair<bool, edge_property_type>, char>::type StoredEdge;

   516 #if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) || defined(BOOST_NO_STD_ALLOCATOR)

   517     typedef std::vector<StoredEdge> Matrix;

   518 #else

   519     // This causes internal compiler error for MSVC

   520     typedef typename Allocator::template rebind<StoredEdge>::other Alloc;

   521     typedef std::vector<StoredEdge, Alloc> Matrix;

   522 #endif

   523     typedef typename Matrix::iterator MatrixIter;

   524     typedef typename Matrix::size_type size_type;

   525   public:

   526     // Graph concept required types

   527     typedef typename Traits::vertex_descriptor vertex_descriptor;

   528     typedef typename Traits::edge_descriptor edge_descriptor;

   529     typedef typename Traits::directed_category directed_category;

   530     typedef typename Traits::edge_parallel_category edge_parallel_category;

   531     typedef adj_matrix_traversal_tag traversal_category;

   532 

   533     static vertex_descriptor null_vertex()

   534     {

   535       return (std::numeric_limits<vertex_descriptor>::max)();

   536     }

   537       

   538     //private: if friends worked, these would be private

   539 

   540     typedef detail::dir_adj_matrix_out_edge_iter<

   541         vertex_descriptor, MatrixIter, size_type, edge_descriptor

   542     > DirOutEdgeIter;

   543 

   544     typedef detail::undir_adj_matrix_out_edge_iter<

   545         vertex_descriptor, MatrixIter, size_type, edge_descriptor

   546     > UnDirOutEdgeIter;

   547 

   548     typedef typename ct_if_t<

   549         typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter

   550     >::type unfiltered_out_edge_iter;

   551 

   552     typedef detail::dir_adj_matrix_in_edge_iter<

   553         vertex_descriptor, MatrixIter, size_type, edge_descriptor

   554     > DirInEdgeIter;

   555 

   556     typedef detail::undir_adj_matrix_in_edge_iter<

   557         vertex_descriptor, MatrixIter, size_type, edge_descriptor

   558     > UnDirInEdgeIter;

   559 

   560     typedef typename ct_if_t<

   561         typename Directed::is_directed_t, DirInEdgeIter, UnDirInEdgeIter

   562     >::type unfiltered_in_edge_iter;

   563     

   564     typedef detail::adj_matrix_edge_iter<

   565         Directed, MatrixIter, size_type, edge_descriptor

   566     > unfiltered_edge_iter;

   567     

   568   public:

   569 

   570     // IncidenceGraph concept required types

   571     typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter>

   572       out_edge_iterator;

   573 

   574     typedef size_type degree_size_type;

   575 

   576     // BidirectionalGraph required types

   577     typedef filter_iterator<detail::does_edge_exist, unfiltered_in_edge_iter>

   578       in_edge_iterator;

   579 

   580     // AdjacencyGraph required types

   581      typedef typename adjacency_iterator_generator<self,

   582        vertex_descriptor, out_edge_iterator>::type adjacency_iterator;

   583 

   584     // VertexListGraph required types

   585     typedef size_type vertices_size_type;

   586     typedef integer_range<vertex_descriptor> VertexList;

   587     typedef typename VertexList::iterator vertex_iterator;

   588 

   589     // EdgeListGraph required types

   590     typedef size_type edges_size_type;

   591     typedef filter_iterator<

   592         detail::does_edge_exist, unfiltered_edge_iter

   593     > edge_iterator;

   594 

   595     // PropertyGraph required types

   596     typedef adjacency_matrix_class_tag graph_tag;

   597 

   598     // Constructor required by MutableGraph

   599     adjacency_matrix(vertices_size_type n_vertices) 

   600       : m_matrix(Directed::is_directed ? 

   601                  (n_vertices * n_vertices)

   602                  : (n_vertices * (n_vertices + 1) / 2)),

   603       m_vertex_set(0, n_vertices),

   604       m_vertex_properties(n_vertices),

   605       m_num_edges(0) { }

   606 

   607 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

   608     // Directly access a vertex or edge bundle

   609     vertex_bundled& operator[](vertex_descriptor v)

   610     { return get(vertex_bundle, *this)[v]; }

   611 

   612     const vertex_bundled& operator[](vertex_descriptor v) const

   613     { return get(vertex_bundle, *this)[v]; }

   614 

   615     edge_bundled& operator[](edge_descriptor e)

   616     { return get(edge_bundle, *this)[e]; }

   617 

   618     const edge_bundled& operator[](edge_descriptor e) const

   619     { return get(edge_bundle, *this)[e]; }

   620 #endif

   621     

   622     //private: if friends worked, these would be private

   623 

   624     typename Matrix::const_reference

   625     get_edge(vertex_descriptor u, vertex_descriptor v) const {

   626       if (Directed::is_directed)

   627         return m_matrix[u * m_vertex_set.size() + v];

   628       else {

   629         if (v > u)

   630           std::swap(u, v);

   631         return m_matrix[u * (u + 1)/2 + v];

   632       }

   633     }

   634     typename Matrix::reference

   635     get_edge(vertex_descriptor u, vertex_descriptor v) {

   636       if (Directed::is_directed)

   637         return m_matrix[u * m_vertex_set.size() + v];

   638       else {

   639         if (v > u)

   640           std::swap(u, v);

   641         return m_matrix[u * (u + 1)/2 + v];

   642       }

   643     }

   644 

   645     Matrix m_matrix;

   646     VertexList m_vertex_set;

   647     std::vector<vertex_property_type> m_vertex_properties;

   648     size_type m_num_edges;

   649   };

   650   

   651   //=========================================================================

   652   // Functions required by the AdjacencyMatrix concept 

   653 

   654   template <typename D, typename VP, typename EP, typename GP, typename A>

   655   std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor,

   656             bool>

   657   edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

   658        typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,

   659        const adjacency_matrix<D,VP,EP,GP,A>& g)

   660   {

   661     bool exists = detail::get_edge_exists(g.get_edge(u,v), 0);

   662     typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor

   663       e(exists, u, v, &detail::get_property(g.get_edge(u,v)));

   664     return std::make_pair(e, exists);

   665   }

   666 

   667   //=========================================================================

   668   // Functions required by the IncidenceGraph concept 

   669 

   670   // O(1)

   671   template <typename VP, typename EP, typename GP, typename A>

   672   std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator,

   673             typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator>

   674   out_edges

   675     (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,

   676      const adjacency_matrix<directedS,VP,EP,GP,A>& g_)

   677   {

   678     typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;

   679     Graph& g = const_cast<Graph&>(g_);

   680     typename Graph::vertices_size_type offset = u * g.m_vertex_set.size();

   681     typename Graph::MatrixIter f = g.m_matrix.begin() + offset;

   682     typename Graph::MatrixIter l = f + g.m_vertex_set.size();

   683     typename Graph::unfiltered_out_edge_iter

   684           first(f, u, g.m_vertex_set.size())

   685         , last(l, u, g.m_vertex_set.size());

   686     detail::does_edge_exist pred;

   687     typedef typename Graph::out_edge_iterator out_edge_iterator;

   688     return std::make_pair(out_edge_iterator(pred, first, last), 

   689                           out_edge_iterator(pred, last, last));

   690   }

   691 

   692   // O(1)

   693   template <typename VP, typename EP, typename GP, typename A>

   694   std::pair<

   695     typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator,

   696     typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator>

   697   out_edges

   698     (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,

   699      const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)

   700   {

   701     typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;

   702     Graph& g = const_cast<Graph&>(g_);

   703     typename Graph::vertices_size_type offset = u * (u + 1) / 2;

   704     typename Graph::MatrixIter f = g.m_matrix.begin() + offset;

   705     typename Graph::MatrixIter l = g.m_matrix.end();

   706 

   707     typename Graph::unfiltered_out_edge_iter

   708         first(f, u, g.m_vertex_set.size())

   709       , last(l, u, g.m_vertex_set.size());

   710     

   711     detail::does_edge_exist pred;

   712     typedef typename Graph::out_edge_iterator out_edge_iterator;

   713     return std::make_pair(out_edge_iterator(pred, first, last), 

   714                           out_edge_iterator(pred, last, last));

   715   }

   716   

   717   // O(N)

   718   template <typename D, typename VP, typename EP, typename GP, typename A>  

   719   typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type

   720   out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

   721              const adjacency_matrix<D,VP,EP,GP,A>& g)

   722   {

   723     typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;

   724     typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l;

   725     for (tie(f, l) = out_edges(u, g); f != l; ++f)

   726       ++n;

   727     return n;

   728   }

   729 

   730   // O(1)

   731   template <typename D, typename VP, typename EP, typename GP, typename A,

   732     typename Dir, typename Vertex>  

   733   typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor

   734   source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,

   735          const adjacency_matrix<D,VP,EP,GP,A>&)

   736   {

   737     return e.m_source;

   738   }

   739 

   740   // O(1)

   741   template <typename D, typename VP, typename EP, typename GP, typename A,

   742     typename Dir, typename Vertex>  

   743   typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor

   744   target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,

   745          const adjacency_matrix<D,VP,EP,GP,A>&)

   746   {

   747     return e.m_target;

   748   }

   749 

   750   //=========================================================================

   751   // Functions required by the BidirectionalGraph concept 

   752 

   753   // O(1)

   754   template <typename VP, typename EP, typename GP, typename A>

   755   std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator,

   756             typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator>

   757   in_edges

   758     (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,

   759      const adjacency_matrix<directedS,VP,EP,GP,A>& g_)

   760   {

   761     typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;

   762     Graph& g = const_cast<Graph&>(g_);

   763     typename Graph::MatrixIter f = g.m_matrix.begin() + u;

   764     typename Graph::MatrixIter l = g.m_matrix.end();

   765     typename Graph::unfiltered_in_edge_iter

   766         first(f, l, u, g.m_vertex_set.size())

   767       , last(l, l, u, g.m_vertex_set.size());

   768     detail::does_edge_exist pred;

   769     typedef typename Graph::in_edge_iterator in_edge_iterator;

   770     return std::make_pair(in_edge_iterator(pred, first, last), 

   771                           in_edge_iterator(pred, last, last));

   772   }

   773 

   774   // O(1)

   775   template <typename VP, typename EP, typename GP, typename A>

   776   std::pair<

   777     typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator,

   778     typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator>

   779   in_edges

   780     (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,

   781      const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)

   782   {

   783     typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;

   784     Graph& g = const_cast<Graph&>(g_);

   785     typename Graph::vertices_size_type offset = u * (u + 1) / 2;

   786     typename Graph::MatrixIter f = g.m_matrix.begin() + offset;

   787     typename Graph::MatrixIter l = g.m_matrix.end();

   788 

   789     typename Graph::unfiltered_in_edge_iter

   790         first(f, u, g.m_vertex_set.size())

   791       , last(l, u, g.m_vertex_set.size());

   792     

   793     detail::does_edge_exist pred;

   794     typedef typename Graph::in_edge_iterator in_edge_iterator;

   795     return std::make_pair(in_edge_iterator(pred, first, last), 

   796                           in_edge_iterator(pred, last, last));

   797   }

   798   

   799   // O(N)

   800   template <typename D, typename VP, typename EP, typename GP, typename A>  

   801   typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type

   802   in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

   803              const adjacency_matrix<D,VP,EP,GP,A>& g)

   804   {

   805     typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;

   806     typename adjacency_matrix<D,VP,EP,GP,A>::in_edge_iterator f, l;

   807     for (tie(f, l) = in_edges(u, g); f != l; ++f)

   808       ++n;

   809     return n;

   810   }

   811 

   812   //=========================================================================

   813   // Functions required by the AdjacencyGraph concept 

   814 

   815   template <typename D, typename VP, typename EP, typename GP, typename A>

   816   std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator,

   817             typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator>

   818   adjacent_vertices

   819     (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

   820      const adjacency_matrix<D,VP,EP,GP,A>& g_)

   821   {

   822       typedef adjacency_matrix<D,VP,EP,GP,A> Graph;

   823       const Graph& cg = static_cast<const Graph&>(g_);

   824       Graph& g = const_cast<Graph&>(cg);

   825       typedef typename Graph::adjacency_iterator adjacency_iterator;

   826       typename Graph::out_edge_iterator first, last;

   827       boost::tie(first, last) = out_edges(u, g);

   828       return std::make_pair(adjacency_iterator(first, &g),

   829                             adjacency_iterator(last, &g));

   830   }

   831 

   832   //=========================================================================

   833   // Functions required by the VertexListGraph concept 

   834 

   835   template <typename D, typename VP, typename EP, typename GP, typename A>

   836   std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator,

   837             typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator>

   838   vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) {

   839     typedef adjacency_matrix<D,VP,EP,GP,A> Graph;

   840     Graph& g = const_cast<Graph&>(g_);

   841     return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end());

   842   }

   843 

   844   template <typename D, typename VP, typename EP, typename GP, typename A>

   845   typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type

   846   num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) {

   847     return g.m_vertex_set.size();

   848   }

   849   

   850   //=========================================================================

   851   // Functions required by the EdgeListGraph concept 

   852   

   853   template <typename D, typename VP, typename EP, typename GP, typename A>

   854   std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator,

   855             typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator>

   856   edges(const adjacency_matrix<D,VP,EP,GP,A>& g_)

   857   {

   858     typedef adjacency_matrix<D,VP,EP,GP,A> Graph;

   859     Graph& g = const_cast<Graph&>(g_);

   860     

   861     typename Graph::unfiltered_edge_iter

   862       first(g.m_matrix.begin(), g.m_matrix.begin(), 

   863                                     g.m_vertex_set.size()),

   864       last(g.m_matrix.end(), g.m_matrix.begin(), 

   865                                     g.m_vertex_set.size());

   866     detail::does_edge_exist pred;

   867     typedef typename Graph::edge_iterator edge_iterator;

   868     return std::make_pair(edge_iterator(pred, first, last),

   869                           edge_iterator(pred, last, last));

   870   }

   871 

   872   // O(1)

   873   template <typename D, typename VP, typename EP, typename GP, typename A>

   874   typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type

   875   num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g)

   876   {

   877     return g.m_num_edges;

   878   }

   879   

   880   //=========================================================================

   881   // Functions required by the MutableGraph concept 

   882 

   883   // O(1)

   884   template <typename D, typename VP, typename EP, typename GP, typename A>

   885   std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>

   886   add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

   887            typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,

   888            const EP& ep,

   889            adjacency_matrix<D,VP,EP,GP,A>& g)

   890   {

   891     typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor 

   892       edge_descriptor;

   893     if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) {

   894       ++(g.m_num_edges);

   895       detail::set_property(g.get_edge(u,v), ep, 0);

   896       detail::set_edge_exists(g.get_edge(u,v), true, 0);

   897       return std::make_pair

   898         (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))), 

   899          true);

   900     } else

   901       return std::make_pair

   902         (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),

   903          false);

   904   }

   905   // O(1)

   906   template <typename D, typename VP, typename EP, typename GP, typename A>

   907   std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>

   908   add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

   909            typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,

   910            adjacency_matrix<D,VP,EP,GP,A>& g)

   911   {

   912     EP ep;

   913     return add_edge(u, v, ep, g);

   914   }

   915 

   916   // O(1)  

   917   template <typename D, typename VP, typename EP, typename GP, typename A>

   918   void

   919   remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

   920               typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,

   921               adjacency_matrix<D,VP,EP,GP,A>& g)

   922   {

   923     --(g.m_num_edges);

   924     detail::set_edge_exists(g.get_edge(u,v), false, 0);

   925   }

   926 

   927   // O(1)

   928   template <typename D, typename VP, typename EP, typename GP, typename A>

   929   void

   930   remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e,

   931               adjacency_matrix<D,VP,EP,GP,A>& g)

   932   {

   933     remove_edge(source(e, g), target(e, g), g);

   934   }

   935 

   936   

   937   template <typename D, typename VP, typename EP, typename GP, typename A>

   938   inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor

   939   add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) {

   940     // UNDER CONSTRUCTION

   941     assert(false);

   942     return *vertices(g).first;

   943   }

   944 

   945   template <typename D, typename VP, typename EP, typename GP, typename A>

   946   inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor

   947   add_vertex(const VP& vp, adjacency_matrix<D,VP,EP,GP,A>& g) {

   948     // UNDER CONSTRUCTION

   949     assert(false);

   950     return *vertices(g).first;

   951   }

   952 

   953   template <typename D, typename VP, typename EP, typename GP, typename A>

   954   inline void

   955   remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

   956                 adjacency_matrix<D,VP,EP,GP,A>& g)

   957   {

   958     // UNDER CONSTRUCTION

   959     assert(false);

   960   }

   961 

   962   // O(V)

   963   template <typename VP, typename EP, typename GP, typename A>

   964   void

   965   clear_vertex

   966     (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,

   967      adjacency_matrix<directedS,VP,EP,GP,A>& g)

   968   {

   969     typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator 

   970       vi, vi_end;

   971     for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

   972       remove_edge(u, *vi, g);

   973     for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

   974       remove_edge(*vi, u, g);

   975   }

   976 

   977   // O(V)

   978   template <typename VP, typename EP, typename GP, typename A>

   979   void

   980   clear_vertex

   981     (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,

   982      adjacency_matrix<undirectedS,VP,EP,GP,A>& g)

   983   {

   984     typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator

   985       vi, vi_end;

   986     for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

   987       remove_edge(u, *vi, g);

   988   }

   989 

   990   //=========================================================================

   991   // Vertex Property Map

   992   

   993   template <typename GraphPtr, typename Vertex, typename T, typename R, 

   994     typename Tag> 

   995   class adj_matrix_vertex_property_map 

   996     : public put_get_helper<R,

   997          adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> >

   998   {

   999   public:

  1000     typedef T value_type;

  1001     typedef R reference;

  1002     typedef Vertex key_type;

  1003     typedef boost::lvalue_property_map_tag category;

  1004     adj_matrix_vertex_property_map() { }

  1005     adj_matrix_vertex_property_map(GraphPtr g) : m_g(g) { }

  1006     inline reference operator[](key_type v) const {

  1007       return get_property_value(m_g->m_vertex_properties[v], Tag());

  1008     }

  1009     GraphPtr m_g;

  1010   };

  1011 

  1012   template <class Property, class Vertex>

  1013   struct adj_matrix_vertex_id_map

  1014     : public boost::put_get_helper<Vertex,

  1015         adj_matrix_vertex_id_map<Property, Vertex> >

  1016   {

  1017     typedef Vertex value_type;

  1018     typedef Vertex reference;

  1019     typedef Vertex key_type;

  1020     typedef boost::readable_property_map_tag category;

  1021      adj_matrix_vertex_id_map() { }

  1022     template <class Graph>

  1023     inline adj_matrix_vertex_id_map(const Graph&) { }

  1024     inline value_type operator[](key_type v) const { return v; }

  1025   };

  1026 

  1027   namespace detail {

  1028 

  1029     struct adj_matrix_any_vertex_pa {

  1030       template <class Tag, class Graph, class Property>

  1031       struct bind_ {

  1032         typedef typename property_value<Property,Tag>::type Value;

  1033         typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;

  1034         

  1035         typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&,

  1036           Tag> type;

  1037         typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value, 

  1038           const Value&, Tag> const_type;

  1039       };

  1040     };

  1041     struct adj_matrix_id_vertex_pa {

  1042       template <class Tag, class Graph, class Property>

  1043       struct bind_ {

  1044         typedef typename Graph::vertex_descriptor Vertex;

  1045         typedef adj_matrix_vertex_id_map<Property, Vertex> type;

  1046         typedef adj_matrix_vertex_id_map<Property, Vertex> const_type;

  1047       };

  1048     };

  1049 

  1050     template <class Tag>

  1051     struct adj_matrix_choose_vertex_pa_helper {

  1052       typedef adj_matrix_any_vertex_pa type;

  1053     };

  1054     template <>

  1055     struct adj_matrix_choose_vertex_pa_helper<vertex_index_t> {

  1056       typedef adj_matrix_id_vertex_pa type;

  1057     };

  1058 

  1059     template <class Tag, class Graph, class Property>

  1060     struct adj_matrix_choose_vertex_pa {

  1061       typedef typename adj_matrix_choose_vertex_pa_helper<Tag>::type Helper;

  1062       typedef typename Helper::template bind_<Tag,Graph,Property> Bind;

  1063       typedef typename Bind::type type;

  1064       typedef typename Bind::const_type const_type;

  1065     };

  1066 

  1067     struct adj_matrix_vertex_property_selector {

  1068       template <class Graph, class Property, class Tag>

  1069       struct bind_ {

  1070         typedef adj_matrix_choose_vertex_pa<Tag,Graph,Property> Choice;

  1071         typedef typename Choice::type type;

  1072         typedef typename Choice::const_type const_type;

  1073       };

  1074     };

  1075 

  1076   } // namespace detail

  1077 

  1078   template <>

  1079   struct vertex_property_selector<adjacency_matrix_class_tag> {

  1080     typedef detail::adj_matrix_vertex_property_selector type;

  1081   };

  1082   

  1083   //=========================================================================

  1084   // Edge Property Map

  1085 

  1086 

  1087   template <typename Directed, typename Property, typename Vertex, 

  1088     typename T, typename R, typename Tag> 

  1089   class adj_matrix_edge_property_map 

  1090     : public put_get_helper<R,

  1091          adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> >

  1092   {

  1093   public:

  1094     typedef T value_type;

  1095     typedef R reference;

  1096     typedef detail::matrix_edge_desc_impl<Directed, Vertex> key_type;

  1097     typedef boost::lvalue_property_map_tag category;

  1098     inline reference operator[](key_type e) const {

  1099       Property& p = *(Property*)e.get_property();

  1100       return get_property_value(p, Tag());

  1101     }

  1102   };

  1103   struct adj_matrix_edge_property_selector {

  1104     template <class Graph, class Property, class Tag>

  1105     struct bind_ {

  1106       typedef typename property_value<Property,Tag>::type T;

  1107       typedef typename Graph::vertex_descriptor Vertex;

  1108       typedef adj_matrix_edge_property_map<typename Graph::directed_category,

  1109         Property, Vertex, T, T&, Tag> type;

  1110       typedef adj_matrix_edge_property_map<typename Graph::directed_category,

  1111         Property, Vertex, T, const T&, Tag> const_type;

  1112     };

  1113   };

  1114   template <>

  1115   struct edge_property_selector<adjacency_matrix_class_tag> {

  1116     typedef adj_matrix_edge_property_selector type;

  1117   };

  1118 

  1119   //=========================================================================

  1120   // Functions required by PropertyGraph

  1121 

  1122   namespace detail {

  1123 

  1124     template <typename Property, typename D, typename VP, typename EP, 

  1125               typename GP, typename A>

  1126     typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 

  1127       Property>::type

  1128     get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property,

  1129                  vertex_property_tag)

  1130     {

  1131       typedef adjacency_matrix<D,VP,EP,GP,A> Graph;

  1132       typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 

  1133         Property>::type PA;

  1134       return PA(&g);

  1135     }