epoc32/include/stdapis/boost/graph/adjacency_matrix.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
williamr@2
     1
//=======================================================================
williamr@2
     2
// Copyright 2001 University of Notre Dame.
williamr@2
     3
// Copyright 2006 Trustees of Indiana University
williamr@2
     4
// Authors: Jeremy G. Siek and Douglas Gregor <dgregor@cs.indiana.edu>
williamr@2
     5
//
williamr@2
     6
// Distributed under the Boost Software License, Version 1.0. (See
williamr@2
     7
// accompanying file LICENSE_1_0.txt or copy at
williamr@2
     8
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     9
//=======================================================================
williamr@2
    10
williamr@2
    11
#ifndef BOOST_ADJACENCY_MATRIX_HPP
williamr@2
    12
#define BOOST_ADJACENCY_MATRIX_HPP
williamr@2
    13
williamr@2
    14
#include <boost/config.hpp>
williamr@2
    15
#include <vector>
williamr@2
    16
#include <memory>
williamr@2
    17
#include <cassert>
williamr@2
    18
#include <boost/limits.hpp>
williamr@2
    19
#include <boost/iterator.hpp>
williamr@2
    20
#include <boost/graph/graph_traits.hpp>
williamr@2
    21
#include <boost/graph/graph_selectors.hpp>
williamr@2
    22
#include <boost/pending/ct_if.hpp>
williamr@2
    23
#include <boost/graph/adjacency_iterator.hpp>
williamr@2
    24
#include <boost/graph/detail/edge.hpp>
williamr@2
    25
#include <boost/iterator/iterator_adaptor.hpp>
williamr@2
    26
#include <boost/iterator/filter_iterator.hpp>
williamr@2
    27
#include <boost/pending/integer_range.hpp>
williamr@2
    28
#include <boost/graph/properties.hpp>
williamr@2
    29
#include <boost/tuple/tuple.hpp>
williamr@2
    30
#include <boost/static_assert.hpp>
williamr@2
    31
#include <boost/type_traits/ice.hpp>
williamr@2
    32
williamr@2
    33
namespace boost {
williamr@2
    34
  
williamr@2
    35
  namespace detail {
williamr@2
    36
williamr@2
    37
    template <class Directed, class Vertex>
williamr@2
    38
    class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex>
williamr@2
    39
    {
williamr@2
    40
      typedef edge_desc_impl<Directed,Vertex> Base;
williamr@2
    41
    public:
williamr@2
    42
      matrix_edge_desc_impl() { }
williamr@2
    43
      matrix_edge_desc_impl(bool exists, Vertex s, Vertex d, 
williamr@2
    44
                            const void* ep = 0)
williamr@2
    45
        : Base(s, d, ep), m_exists(exists) { }
williamr@2
    46
      bool exists() const { return m_exists; }
williamr@2
    47
    private:
williamr@2
    48
      bool m_exists;
williamr@2
    49
    };
williamr@2
    50
williamr@2
    51
    struct does_edge_exist {
williamr@2
    52
      template <class Edge>
williamr@2
    53
      bool operator()(const Edge& e) const { return e.exists(); }
williamr@2
    54
    };
williamr@2
    55
williamr@2
    56
    template <typename EdgeProperty>
williamr@2
    57
    bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) {
williamr@2
    58
      return stored_edge.first;
williamr@2
    59
    }
williamr@2
    60
    template <typename EdgeProperty>
williamr@2
    61
    void set_edge_exists(
williamr@2
    62
        std::pair<bool, EdgeProperty>& stored_edge, 
williamr@2
    63
        bool flag,
williamr@2
    64
        int
williamr@2
    65
        ) {
williamr@2
    66
      stored_edge.first = flag;
williamr@2
    67
    }
williamr@2
    68
williamr@2
    69
    template <typename EdgeProxy>
williamr@2
    70
    bool get_edge_exists(const EdgeProxy& edge_proxy, ...) {
williamr@2
    71
      return edge_proxy;
williamr@2
    72
    }
williamr@2
    73
    template <typename EdgeProxy>
williamr@2
    74
    EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) {
williamr@2
    75
      edge_proxy = flag;
williamr@2
    76
      return edge_proxy; // just to avoid never used warning
williamr@2
    77
    }
williamr@2
    78
williamr@2
    79
williamr@2
    80
williamr@2
    81
    template <typename EdgeProperty>
williamr@2
    82
    const EdgeProperty&
williamr@2
    83
    get_property(const std::pair<bool, EdgeProperty>& stored_edge) {
williamr@2
    84
      return stored_edge.second;
williamr@2
    85
    }
williamr@2
    86
    template <typename EdgeProperty>
williamr@2
    87
    EdgeProperty&
williamr@2
    88
    get_property(std::pair<bool, EdgeProperty>& stored_edge) {
williamr@2
    89
      return stored_edge.second;
williamr@2
    90
    }
williamr@2
    91
williamr@2
    92
    template <typename StoredEdgeProperty, typename EdgeProperty>
williamr@2
    93
    inline void
williamr@2
    94
    set_property(std::pair<bool, StoredEdgeProperty>& stored_edge, 
williamr@2
    95
                 const EdgeProperty& ep, int) {
williamr@2
    96
      stored_edge.second = ep;
williamr@2
    97
    }
williamr@2
    98
williamr@2
    99
    inline const no_property& get_property(const char&) {
williamr@2
   100
      static no_property s_prop;
williamr@2
   101
      return s_prop;
williamr@2
   102
    }
williamr@2
   103
    inline no_property& get_property(char&) {
williamr@2
   104
      static no_property s_prop;
williamr@2
   105
      return s_prop;
williamr@2
   106
    }
williamr@2
   107
    template <typename EdgeProxy, typename EdgeProperty>
williamr@2
   108
    inline void
williamr@2
   109
    set_property(EdgeProxy, const EdgeProperty&, ...) {}
williamr@2
   110
    
williamr@2
   111
    //=======================================================================
williamr@2
   112
    // Directed Out Edge Iterator
williamr@2
   113
williamr@2
   114
    template <
williamr@2
   115
        typename VertexDescriptor, typename MatrixIter
williamr@2
   116
      , typename VerticesSizeType, typename EdgeDescriptor
williamr@2
   117
    >
williamr@2
   118
    struct dir_adj_matrix_out_edge_iter
williamr@2
   119
      : iterator_adaptor<
williamr@2
   120
            dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
williamr@2
   121
          , MatrixIter
williamr@2
   122
          , EdgeDescriptor
williamr@2
   123
          , use_default
williamr@2
   124
          , EdgeDescriptor
williamr@2
   125
          , std::ptrdiff_t
williamr@2
   126
        >
williamr@2
   127
    {
williamr@2
   128
        typedef iterator_adaptor<
williamr@2
   129
            dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
williamr@2
   130
          , MatrixIter
williamr@2
   131
          , EdgeDescriptor
williamr@2
   132
          , use_default
williamr@2
   133
          , EdgeDescriptor
williamr@2
   134
          , std::ptrdiff_t
williamr@2
   135
        > super_t;
williamr@2
   136
        
williamr@2
   137
        dir_adj_matrix_out_edge_iter() { }
williamr@2
   138
        
williamr@2
   139
        dir_adj_matrix_out_edge_iter(
williamr@2
   140
            const MatrixIter& i
williamr@2
   141
          , const VertexDescriptor& src
williamr@2
   142
          , const VerticesSizeType& n
williamr@2
   143
           )
williamr@2
   144
            : super_t(i), m_src(src), m_targ(0), m_n(n)
williamr@2
   145
        { }
williamr@2
   146
williamr@2
   147
        void increment() {
williamr@2
   148
            ++this->base_reference();
williamr@2
   149
            ++m_targ;
williamr@2
   150
        }
williamr@2
   151
        
williamr@2
   152
        inline EdgeDescriptor
williamr@2
   153
        dereference() const 
williamr@2
   154
        {
williamr@2
   155
            return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ, 
williamr@2
   156
                                  &get_property(*this->base()));
williamr@2
   157
        }
williamr@2
   158
        VertexDescriptor m_src, m_targ;
williamr@2
   159
        VerticesSizeType m_n;
williamr@2
   160
    };
williamr@2
   161
williamr@2
   162
    //=======================================================================
williamr@2
   163
    // Directed In Edge Iterator
williamr@2
   164
williamr@2
   165
    template <
williamr@2
   166
        typename VertexDescriptor, typename MatrixIter
williamr@2
   167
      , typename VerticesSizeType, typename EdgeDescriptor
williamr@2
   168
    >
williamr@2
   169
    struct dir_adj_matrix_in_edge_iter
williamr@2
   170
      : iterator_adaptor<
williamr@2
   171
            dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
williamr@2
   172
          , MatrixIter
williamr@2
   173
          , EdgeDescriptor
williamr@2
   174
          , use_default
williamr@2
   175
          , EdgeDescriptor
williamr@2
   176
          , std::ptrdiff_t
williamr@2
   177
        >
williamr@2
   178
    {
williamr@2
   179
        typedef iterator_adaptor<
williamr@2
   180
            dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
williamr@2
   181
          , MatrixIter
williamr@2
   182
          , EdgeDescriptor
williamr@2
   183
          , use_default
williamr@2
   184
          , EdgeDescriptor
williamr@2
   185
          , std::ptrdiff_t
williamr@2
   186
        > super_t;
williamr@2
   187
        
williamr@2
   188
        dir_adj_matrix_in_edge_iter() { }
williamr@2
   189
        
williamr@2
   190
        dir_adj_matrix_in_edge_iter(
williamr@2
   191
            const MatrixIter& i
williamr@2
   192
          , const MatrixIter& last
williamr@2
   193
          , const VertexDescriptor& tgt
williamr@2
   194
          , const VerticesSizeType& n
williamr@2
   195
           )
williamr@2
   196
          : super_t(i), m_last(last), m_src(0), m_targ(tgt), m_n(n)
williamr@2
   197
        { }
williamr@2
   198
williamr@2
   199
        void increment() {
williamr@2
   200
          if (VerticesSizeType(m_last - this->base_reference()) >= m_n) {
williamr@2
   201
            this->base_reference() += m_n;
williamr@2
   202
            ++m_src;
williamr@2
   203
          } else {
williamr@2
   204
            this->base_reference() = m_last;
williamr@2
   205
          }
williamr@2
   206
        }
williamr@2
   207
        
williamr@2
   208
        inline EdgeDescriptor
williamr@2
   209
        dereference() const 
williamr@2
   210
        {
williamr@2
   211
            return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ, 
williamr@2
   212
                                  &get_property(*this->base()));
williamr@2
   213
        }
williamr@2
   214
        MatrixIter m_last;
williamr@2
   215
        VertexDescriptor m_src, m_targ;
williamr@2
   216
        VerticesSizeType m_n;
williamr@2
   217
    };
williamr@2
   218
williamr@2
   219
    //=======================================================================
williamr@2
   220
    // Undirected Out Edge Iterator
williamr@2
   221
williamr@2
   222
    template <
williamr@2
   223
        typename VertexDescriptor, typename MatrixIter
williamr@2
   224
      , typename VerticesSizeType, typename EdgeDescriptor
williamr@2
   225
    >
williamr@2
   226
    struct undir_adj_matrix_out_edge_iter 
williamr@2
   227
      : iterator_adaptor<
williamr@2
   228
            undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
williamr@2
   229
          , MatrixIter
williamr@2
   230
          , EdgeDescriptor
williamr@2
   231
          , use_default
williamr@2
   232
          , EdgeDescriptor
williamr@2
   233
          , std::ptrdiff_t
williamr@2
   234
        >
williamr@2
   235
    {
williamr@2
   236
        typedef iterator_adaptor<
williamr@2
   237
            undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
williamr@2
   238
          , MatrixIter
williamr@2
   239
          , EdgeDescriptor
williamr@2
   240
          , use_default
williamr@2
   241
          , EdgeDescriptor
williamr@2
   242
          , std::ptrdiff_t
williamr@2
   243
        > super_t;
williamr@2
   244
        
williamr@2
   245
        undir_adj_matrix_out_edge_iter() { }
williamr@2
   246
        
williamr@2
   247
        undir_adj_matrix_out_edge_iter(
williamr@2
   248
            const MatrixIter& i
williamr@2
   249
          , const VertexDescriptor& src
williamr@2
   250
          , const VerticesSizeType& n
williamr@2
   251
        )
williamr@2
   252
          : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)
williamr@2
   253
        {}
williamr@2
   254
williamr@2
   255
        void increment()
williamr@2
   256
        {
williamr@2
   257
            if (m_targ < m_src)     // first half
williamr@2
   258
            {
williamr@2
   259
                ++this->base_reference();
williamr@2
   260
            }
williamr@2
   261
            else if (m_targ < m_n - 1)
williamr@2
   262
            {                  // second half
williamr@2
   263
                ++m_inc;
williamr@2
   264
                this->base_reference() += m_inc;
williamr@2
   265
            }
williamr@2
   266
            else
williamr@2
   267
            {                  // past-the-end
williamr@2
   268
                this->base_reference() += m_n - m_src;
williamr@2
   269
            }
williamr@2
   270
            ++m_targ;
williamr@2
   271
        }
williamr@2
   272
        
williamr@2
   273
        inline EdgeDescriptor
williamr@2
   274
        dereference() const 
williamr@2
   275
        {
williamr@2
   276
            return EdgeDescriptor(
williamr@2
   277
                get_edge_exists(*this->base(), 0), m_src, m_targ
williamr@2
   278
              , &get_property(*this->base())
williamr@2
   279
            );
williamr@2
   280
        }
williamr@2
   281
        
williamr@2
   282
        VertexDescriptor m_src, m_inc, m_targ;
williamr@2
   283
        VerticesSizeType m_n;
williamr@2
   284
    };
williamr@2
   285
williamr@2
   286
    //=======================================================================
williamr@2
   287
    // Undirected In Edge Iterator
williamr@2
   288
williamr@2
   289
    template <
williamr@2
   290
        typename VertexDescriptor, typename MatrixIter
williamr@2
   291
      , typename VerticesSizeType, typename EdgeDescriptor
williamr@2
   292
    >
williamr@2
   293
    struct undir_adj_matrix_in_edge_iter 
williamr@2
   294
      : iterator_adaptor<
williamr@2
   295
            undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
williamr@2
   296
          , MatrixIter
williamr@2
   297
          , EdgeDescriptor
williamr@2
   298
          , use_default
williamr@2
   299
          , EdgeDescriptor
williamr@2
   300
          , std::ptrdiff_t
williamr@2
   301
        >
williamr@2
   302
    {
williamr@2
   303
        typedef iterator_adaptor<
williamr@2
   304
            undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
williamr@2
   305
          , MatrixIter
williamr@2
   306
          , EdgeDescriptor
williamr@2
   307
          , use_default
williamr@2
   308
          , EdgeDescriptor
williamr@2
   309
          , std::ptrdiff_t
williamr@2
   310
        > super_t;
williamr@2
   311
        
williamr@2
   312
        undir_adj_matrix_in_edge_iter() { }
williamr@2
   313
        
williamr@2
   314
        undir_adj_matrix_in_edge_iter(
williamr@2
   315
            const MatrixIter& i
williamr@2
   316
          , const VertexDescriptor& src
williamr@2
   317
          , const VerticesSizeType& n
williamr@2
   318
        )
williamr@2
   319
          : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)
williamr@2
   320
        {}
williamr@2
   321
williamr@2
   322
        void increment()
williamr@2
   323
        {
williamr@2
   324
            if (m_targ < m_src)     // first half
williamr@2
   325
            {
williamr@2
   326
                ++this->base_reference();
williamr@2
   327
            }
williamr@2
   328
            else if (m_targ < m_n - 1)
williamr@2
   329
            {                  // second half
williamr@2
   330
                ++m_inc;
williamr@2
   331
                this->base_reference() += m_inc;
williamr@2
   332
            }
williamr@2
   333
            else
williamr@2
   334
            {                  // past-the-end
williamr@2
   335
                this->base_reference() += m_n - m_src;
williamr@2
   336
            }
williamr@2
   337
            ++m_targ;
williamr@2
   338
        }
williamr@2
   339
        
williamr@2
   340
        inline EdgeDescriptor
williamr@2
   341
        dereference() const 
williamr@2
   342
        {
williamr@2
   343
            return EdgeDescriptor(
williamr@2
   344
                     get_edge_exists(*this->base(), 0), m_targ, m_src
williamr@2
   345
              , &get_property(*this->base())
williamr@2
   346
            );
williamr@2
   347
        }
williamr@2
   348
        
williamr@2
   349
        VertexDescriptor m_src, m_inc, m_targ;
williamr@2
   350
        VerticesSizeType m_n;
williamr@2
   351
    };
williamr@2
   352
williamr@2
   353
    //=======================================================================
williamr@2
   354
    // Edge Iterator
williamr@2
   355
williamr@2
   356
    template <typename Directed, typename MatrixIter, 
williamr@2
   357
              typename VerticesSizeType, typename EdgeDescriptor>
williamr@2
   358
    struct adj_matrix_edge_iter
williamr@2
   359
      : iterator_adaptor<
williamr@2
   360
            adj_matrix_edge_iter<Directed, MatrixIter,  VerticesSizeType, EdgeDescriptor>
williamr@2
   361
          , MatrixIter
williamr@2
   362
          , EdgeDescriptor
williamr@2
   363
          , use_default
williamr@2
   364
          , EdgeDescriptor
williamr@2
   365
          , std::ptrdiff_t
williamr@2
   366
        >
williamr@2
   367
    {
williamr@2
   368
        typedef iterator_adaptor<
williamr@2
   369
            adj_matrix_edge_iter<Directed, MatrixIter,  VerticesSizeType, EdgeDescriptor>
williamr@2
   370
          , MatrixIter
williamr@2
   371
          , EdgeDescriptor
williamr@2
   372
          , use_default
williamr@2
   373
          , EdgeDescriptor
williamr@2
   374
          , std::ptrdiff_t
williamr@2
   375
        > super_t;
williamr@2
   376
        
williamr@2
   377
        adj_matrix_edge_iter() { }
williamr@2
   378
        
williamr@2
   379
        adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n) 
williamr@2
   380
            : super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { }
williamr@2
   381
williamr@2
   382
        void increment()
williamr@2
   383
        {
williamr@2
   384
            increment_dispatch(this->base_reference(), Directed());
williamr@2
   385
        }
williamr@2
   386
        
williamr@2
   387
        void increment_dispatch(MatrixIter& i, directedS)
williamr@2
   388
        {
williamr@2
   389
            ++i;
williamr@2
   390
            if (m_targ == m_n - 1)
williamr@2
   391
            {
williamr@2
   392
                m_targ = 0;
williamr@2
   393
                ++m_src;
williamr@2
   394
            }
williamr@2
   395
            else
williamr@2
   396
            {
williamr@2
   397
                ++m_targ;
williamr@2
   398
            }
williamr@2
   399
        }
williamr@2
   400
        
williamr@2
   401
        void increment_dispatch(MatrixIter& i, undirectedS)
williamr@2
   402
        {
williamr@2
   403
            ++i;
williamr@2
   404
            if (m_targ == m_src)
williamr@2
   405
            {
williamr@2
   406
                m_targ = 0;
williamr@2
   407
                ++m_src;
williamr@2
   408
            }
williamr@2
   409
            else
williamr@2
   410
            {
williamr@2
   411
                ++m_targ;
williamr@2
   412
            }
williamr@2
   413
        }
williamr@2
   414
williamr@2
   415
        inline EdgeDescriptor
williamr@2
   416
        dereference() const 
williamr@2
   417
        {
williamr@2
   418
            return EdgeDescriptor(
williamr@2
   419
                get_edge_exists(
williamr@2
   420
                    *this->base(), 0), m_src, m_targ, &get_property(*this->base())
williamr@2
   421
            );
williamr@2
   422
        }
williamr@2
   423
      
williamr@2
   424
        MatrixIter m_start;
williamr@2
   425
        VerticesSizeType m_src, m_targ, m_n;
williamr@2
   426
    };
williamr@2
   427
williamr@2
   428
  } // namespace detail
williamr@2
   429
williamr@2
   430
  //=========================================================================
williamr@2
   431
  // Adjacency Matrix Traits
williamr@2
   432
  template <typename Directed = directedS>
williamr@2
   433
  class adjacency_matrix_traits {
williamr@2
   434
    typedef typename Directed::is_directed_t is_directed;
williamr@2
   435
  public:
williamr@2
   436
    // The bidirectionalS tag is not allowed with the adjacency_matrix
williamr@2
   437
    // graph type. Instead, use directedS, which also provides the
williamr@2
   438
    // functionality required for a Bidirectional Graph (in_edges,
williamr@2
   439
    // in_degree, etc.).
williamr@2
   440
#if !defined(_MSC_VER) || _MSC_VER > 1300
williamr@2
   441
    BOOST_STATIC_ASSERT(type_traits::ice_not<(is_same<Directed, bidirectionalS>::value)>::value);
williamr@2
   442
#endif
williamr@2
   443
williamr@2
   444
    typedef typename boost::ct_if_t<is_directed,
williamr@2
   445
                                    bidirectional_tag, undirected_tag>::type
williamr@2
   446
      directed_category;
williamr@2
   447
    
williamr@2
   448
    typedef disallow_parallel_edge_tag edge_parallel_category;
williamr@2
   449
    
williamr@2
   450
    typedef std::size_t vertex_descriptor;
williamr@2
   451
williamr@2
   452
    typedef detail::matrix_edge_desc_impl<directed_category,
williamr@2
   453
      vertex_descriptor> edge_descriptor;
williamr@2
   454
  };
williamr@2
   455
williamr@2
   456
  struct adjacency_matrix_class_tag { };
williamr@2
   457
williamr@2
   458
  struct adj_matrix_traversal_tag :
williamr@2
   459
    public virtual adjacency_matrix_tag,
williamr@2
   460
    public virtual vertex_list_graph_tag,
williamr@2
   461
    public virtual incidence_graph_tag,
williamr@2
   462
    public virtual adjacency_graph_tag,
williamr@2
   463
    public virtual edge_list_graph_tag { };
williamr@2
   464
  
williamr@2
   465
  //=========================================================================
williamr@2
   466
  // Adjacency Matrix Class
williamr@2
   467
  template <typename Directed = directedS,
williamr@2
   468
            typename VertexProperty = no_property,
williamr@2
   469
            typename EdgeProperty = no_property,
williamr@2
   470
            typename GraphProperty = no_property,
williamr@2
   471
            typename Allocator = std::allocator<bool> >
williamr@2
   472
  class adjacency_matrix {
williamr@2
   473
    typedef adjacency_matrix self;
williamr@2
   474
    typedef adjacency_matrix_traits<Directed> Traits;
williamr@2
   475
    
williamr@2
   476
  public:
williamr@2
   477
#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
williamr@2
   478
    // The bidirectionalS tag is not allowed with the adjacency_matrix
williamr@2
   479
    // graph type. Instead, use directedS, which also provides the
williamr@2
   480
    // functionality required for a Bidirectional Graph (in_edges,
williamr@2
   481
    // in_degree, etc.).
williamr@2
   482
    BOOST_STATIC_ASSERT(!(is_same<Directed, bidirectionalS>::value));
williamr@2
   483
#endif
williamr@2
   484
williamr@2
   485
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2
   486
    typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::type
williamr@2
   487
      vertex_property_type;
williamr@2
   488
    typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type
williamr@2
   489
      edge_property_type;
williamr@2
   490
      
williamr@2
   491
  private:
williamr@2
   492
    typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::retagged
williamr@2
   493
      maybe_vertex_bundled;
williamr@2
   494
williamr@2
   495
    typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::retagged
williamr@2
   496
      maybe_edge_bundled;
williamr@2
   497
    
williamr@2
   498
  public:
williamr@2
   499
    // The types that are actually bundled
williamr@2
   500
    typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),
williamr@2
   501
                           no_vertex_bundle,
williamr@2
   502
                           maybe_vertex_bundled>::type vertex_bundled;
williamr@2
   503
    typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),
williamr@2
   504
                           no_edge_bundle,
williamr@2
   505
                           maybe_edge_bundled>::type edge_bundled;
williamr@2
   506
#else
williamr@2
   507
    typedef EdgeProperty     edge_property_type;
williamr@2
   508
    typedef VertexProperty   vertex_property_type;
williamr@2
   509
    typedef no_vertex_bundle vertex_bundled;
williamr@2
   510
    typedef no_edge_bundle   edge_bundled;
williamr@2
   511
#endif
williamr@2
   512
williamr@2
   513
  public: // should be private
williamr@2
   514
    typedef typename ct_if_t<typename has_property<edge_property_type>::type,
williamr@2
   515
      std::pair<bool, edge_property_type>, char>::type StoredEdge;
williamr@2
   516
#if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) || defined(BOOST_NO_STD_ALLOCATOR)
williamr@2
   517
    typedef std::vector<StoredEdge> Matrix;
williamr@2
   518
#else
williamr@2
   519
    // This causes internal compiler error for MSVC
williamr@2
   520
    typedef typename Allocator::template rebind<StoredEdge>::other Alloc;
williamr@2
   521
    typedef std::vector<StoredEdge, Alloc> Matrix;
williamr@2
   522
#endif
williamr@2
   523
    typedef typename Matrix::iterator MatrixIter;
williamr@2
   524
    typedef typename Matrix::size_type size_type;
williamr@2
   525
  public:
williamr@2
   526
    // Graph concept required types
williamr@2
   527
    typedef typename Traits::vertex_descriptor vertex_descriptor;
williamr@2
   528
    typedef typename Traits::edge_descriptor edge_descriptor;
williamr@2
   529
    typedef typename Traits::directed_category directed_category;
williamr@2
   530
    typedef typename Traits::edge_parallel_category edge_parallel_category;
williamr@2
   531
    typedef adj_matrix_traversal_tag traversal_category;
williamr@2
   532
williamr@2
   533
    static vertex_descriptor null_vertex()
williamr@2
   534
    {
williamr@2
   535
      return (std::numeric_limits<vertex_descriptor>::max)();
williamr@2
   536
    }
williamr@2
   537
      
williamr@2
   538
    //private: if friends worked, these would be private
williamr@2
   539
williamr@2
   540
    typedef detail::dir_adj_matrix_out_edge_iter<
williamr@2
   541
        vertex_descriptor, MatrixIter, size_type, edge_descriptor
williamr@2
   542
    > DirOutEdgeIter;
williamr@2
   543
williamr@2
   544
    typedef detail::undir_adj_matrix_out_edge_iter<
williamr@2
   545
        vertex_descriptor, MatrixIter, size_type, edge_descriptor
williamr@2
   546
    > UnDirOutEdgeIter;
williamr@2
   547
williamr@2
   548
    typedef typename ct_if_t<
williamr@2
   549
        typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter
williamr@2
   550
    >::type unfiltered_out_edge_iter;
williamr@2
   551
williamr@2
   552
    typedef detail::dir_adj_matrix_in_edge_iter<
williamr@2
   553
        vertex_descriptor, MatrixIter, size_type, edge_descriptor
williamr@2
   554
    > DirInEdgeIter;
williamr@2
   555
williamr@2
   556
    typedef detail::undir_adj_matrix_in_edge_iter<
williamr@2
   557
        vertex_descriptor, MatrixIter, size_type, edge_descriptor
williamr@2
   558
    > UnDirInEdgeIter;
williamr@2
   559
williamr@2
   560
    typedef typename ct_if_t<
williamr@2
   561
        typename Directed::is_directed_t, DirInEdgeIter, UnDirInEdgeIter
williamr@2
   562
    >::type unfiltered_in_edge_iter;
williamr@2
   563
    
williamr@2
   564
    typedef detail::adj_matrix_edge_iter<
williamr@2
   565
        Directed, MatrixIter, size_type, edge_descriptor
williamr@2
   566
    > unfiltered_edge_iter;
williamr@2
   567
    
williamr@2
   568
  public:
williamr@2
   569
williamr@2
   570
    // IncidenceGraph concept required types
williamr@2
   571
    typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter>
williamr@2
   572
      out_edge_iterator;
williamr@2
   573
williamr@2
   574
    typedef size_type degree_size_type;
williamr@2
   575
williamr@2
   576
    // BidirectionalGraph required types
williamr@2
   577
    typedef filter_iterator<detail::does_edge_exist, unfiltered_in_edge_iter>
williamr@2
   578
      in_edge_iterator;
williamr@2
   579
williamr@2
   580
    // AdjacencyGraph required types
williamr@2
   581
     typedef typename adjacency_iterator_generator<self,
williamr@2
   582
       vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
williamr@2
   583
williamr@2
   584
    // VertexListGraph required types
williamr@2
   585
    typedef size_type vertices_size_type;
williamr@2
   586
    typedef integer_range<vertex_descriptor> VertexList;
williamr@2
   587
    typedef typename VertexList::iterator vertex_iterator;
williamr@2
   588
williamr@2
   589
    // EdgeListGraph required types
williamr@2
   590
    typedef size_type edges_size_type;
williamr@2
   591
    typedef filter_iterator<
williamr@2
   592
        detail::does_edge_exist, unfiltered_edge_iter
williamr@2
   593
    > edge_iterator;
williamr@2
   594
williamr@2
   595
    // PropertyGraph required types
williamr@2
   596
    typedef adjacency_matrix_class_tag graph_tag;
williamr@2
   597
williamr@2
   598
    // Constructor required by MutableGraph
williamr@2
   599
    adjacency_matrix(vertices_size_type n_vertices) 
williamr@2
   600
      : m_matrix(Directed::is_directed ? 
williamr@2
   601
                 (n_vertices * n_vertices)
williamr@2
   602
                 : (n_vertices * (n_vertices + 1) / 2)),
williamr@2
   603
      m_vertex_set(0, n_vertices),
williamr@2
   604
      m_vertex_properties(n_vertices),
williamr@2
   605
      m_num_edges(0) { }
williamr@2
   606
williamr@2
   607
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2
   608
    // Directly access a vertex or edge bundle
williamr@2
   609
    vertex_bundled& operator[](vertex_descriptor v)
williamr@2
   610
    { return get(vertex_bundle, *this)[v]; }
williamr@2
   611
williamr@2
   612
    const vertex_bundled& operator[](vertex_descriptor v) const
williamr@2
   613
    { return get(vertex_bundle, *this)[v]; }
williamr@2
   614
williamr@2
   615
    edge_bundled& operator[](edge_descriptor e)
williamr@2
   616
    { return get(edge_bundle, *this)[e]; }
williamr@2
   617
williamr@2
   618
    const edge_bundled& operator[](edge_descriptor e) const
williamr@2
   619
    { return get(edge_bundle, *this)[e]; }
williamr@2
   620
#endif
williamr@2
   621
    
williamr@2
   622
    //private: if friends worked, these would be private
williamr@2
   623
williamr@2
   624
    typename Matrix::const_reference
williamr@2
   625
    get_edge(vertex_descriptor u, vertex_descriptor v) const {
williamr@2
   626
      if (Directed::is_directed)
williamr@2
   627
        return m_matrix[u * m_vertex_set.size() + v];
williamr@2
   628
      else {
williamr@2
   629
        if (v > u)
williamr@2
   630
          std::swap(u, v);
williamr@2
   631
        return m_matrix[u * (u + 1)/2 + v];
williamr@2
   632
      }
williamr@2
   633
    }
williamr@2
   634
    typename Matrix::reference
williamr@2
   635
    get_edge(vertex_descriptor u, vertex_descriptor v) {
williamr@2
   636
      if (Directed::is_directed)
williamr@2
   637
        return m_matrix[u * m_vertex_set.size() + v];
williamr@2
   638
      else {
williamr@2
   639
        if (v > u)
williamr@2
   640
          std::swap(u, v);
williamr@2
   641
        return m_matrix[u * (u + 1)/2 + v];
williamr@2
   642
      }
williamr@2
   643
    }
williamr@2
   644
williamr@2
   645
    Matrix m_matrix;
williamr@2
   646
    VertexList m_vertex_set;
williamr@2
   647
    std::vector<vertex_property_type> m_vertex_properties;
williamr@2
   648
    size_type m_num_edges;
williamr@2
   649
  };
williamr@2
   650
  
williamr@2
   651
  //=========================================================================
williamr@2
   652
  // Functions required by the AdjacencyMatrix concept 
williamr@2
   653
williamr@2
   654
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   655
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor,
williamr@2
   656
            bool>
williamr@2
   657
  edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   658
       typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
williamr@2
   659
       const adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
   660
  {
williamr@2
   661
    bool exists = detail::get_edge_exists(g.get_edge(u,v), 0);
williamr@2
   662
    typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
williamr@2
   663
      e(exists, u, v, &detail::get_property(g.get_edge(u,v)));
williamr@2
   664
    return std::make_pair(e, exists);
williamr@2
   665
  }
williamr@2
   666
williamr@2
   667
  //=========================================================================
williamr@2
   668
  // Functions required by the IncidenceGraph concept 
williamr@2
   669
williamr@2
   670
  // O(1)
williamr@2
   671
  template <typename VP, typename EP, typename GP, typename A>
williamr@2
   672
  std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator,
williamr@2
   673
            typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator>
williamr@2
   674
  out_edges
williamr@2
   675
    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   676
     const adjacency_matrix<directedS,VP,EP,GP,A>& g_)
williamr@2
   677
  {
williamr@2
   678
    typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;
williamr@2
   679
    Graph& g = const_cast<Graph&>(g_);
williamr@2
   680
    typename Graph::vertices_size_type offset = u * g.m_vertex_set.size();
williamr@2
   681
    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
williamr@2
   682
    typename Graph::MatrixIter l = f + g.m_vertex_set.size();
williamr@2
   683
    typename Graph::unfiltered_out_edge_iter
williamr@2
   684
          first(f, u, g.m_vertex_set.size())
williamr@2
   685
        , last(l, u, g.m_vertex_set.size());
williamr@2
   686
    detail::does_edge_exist pred;
williamr@2
   687
    typedef typename Graph::out_edge_iterator out_edge_iterator;
williamr@2
   688
    return std::make_pair(out_edge_iterator(pred, first, last), 
williamr@2
   689
                          out_edge_iterator(pred, last, last));
williamr@2
   690
  }
williamr@2
   691
williamr@2
   692
  // O(1)
williamr@2
   693
  template <typename VP, typename EP, typename GP, typename A>
williamr@2
   694
  std::pair<
williamr@2
   695
    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator,
williamr@2
   696
    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator>
williamr@2
   697
  out_edges
williamr@2
   698
    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   699
     const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)
williamr@2
   700
  {
williamr@2
   701
    typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;
williamr@2
   702
    Graph& g = const_cast<Graph&>(g_);
williamr@2
   703
    typename Graph::vertices_size_type offset = u * (u + 1) / 2;
williamr@2
   704
    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
williamr@2
   705
    typename Graph::MatrixIter l = g.m_matrix.end();
williamr@2
   706
williamr@2
   707
    typename Graph::unfiltered_out_edge_iter
williamr@2
   708
        first(f, u, g.m_vertex_set.size())
williamr@2
   709
      , last(l, u, g.m_vertex_set.size());
williamr@2
   710
    
williamr@2
   711
    detail::does_edge_exist pred;
williamr@2
   712
    typedef typename Graph::out_edge_iterator out_edge_iterator;
williamr@2
   713
    return std::make_pair(out_edge_iterator(pred, first, last), 
williamr@2
   714
                          out_edge_iterator(pred, last, last));
williamr@2
   715
  }
williamr@2
   716
  
williamr@2
   717
  // O(N)
williamr@2
   718
  template <typename D, typename VP, typename EP, typename GP, typename A>  
williamr@2
   719
  typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
williamr@2
   720
  out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   721
             const adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
   722
  {
williamr@2
   723
    typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;
williamr@2
   724
    typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l;
williamr@2
   725
    for (tie(f, l) = out_edges(u, g); f != l; ++f)
williamr@2
   726
      ++n;
williamr@2
   727
    return n;
williamr@2
   728
  }
williamr@2
   729
williamr@2
   730
  // O(1)
williamr@2
   731
  template <typename D, typename VP, typename EP, typename GP, typename A,
williamr@2
   732
    typename Dir, typename Vertex>  
williamr@2
   733
  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
williamr@2
   734
  source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
williamr@2
   735
         const adjacency_matrix<D,VP,EP,GP,A>&)
williamr@2
   736
  {
williamr@2
   737
    return e.m_source;
williamr@2
   738
  }
williamr@2
   739
williamr@2
   740
  // O(1)
williamr@2
   741
  template <typename D, typename VP, typename EP, typename GP, typename A,
williamr@2
   742
    typename Dir, typename Vertex>  
williamr@2
   743
  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
williamr@2
   744
  target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
williamr@2
   745
         const adjacency_matrix<D,VP,EP,GP,A>&)
williamr@2
   746
  {
williamr@2
   747
    return e.m_target;
williamr@2
   748
  }
williamr@2
   749
williamr@2
   750
  //=========================================================================
williamr@2
   751
  // Functions required by the BidirectionalGraph concept 
williamr@2
   752
williamr@2
   753
  // O(1)
williamr@2
   754
  template <typename VP, typename EP, typename GP, typename A>
williamr@2
   755
  std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator,
williamr@2
   756
            typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator>
williamr@2
   757
  in_edges
williamr@2
   758
    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   759
     const adjacency_matrix<directedS,VP,EP,GP,A>& g_)
williamr@2
   760
  {
williamr@2
   761
    typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;
williamr@2
   762
    Graph& g = const_cast<Graph&>(g_);
williamr@2
   763
    typename Graph::MatrixIter f = g.m_matrix.begin() + u;
williamr@2
   764
    typename Graph::MatrixIter l = g.m_matrix.end();
williamr@2
   765
    typename Graph::unfiltered_in_edge_iter
williamr@2
   766
        first(f, l, u, g.m_vertex_set.size())
williamr@2
   767
      , last(l, l, u, g.m_vertex_set.size());
williamr@2
   768
    detail::does_edge_exist pred;
williamr@2
   769
    typedef typename Graph::in_edge_iterator in_edge_iterator;
williamr@2
   770
    return std::make_pair(in_edge_iterator(pred, first, last), 
williamr@2
   771
                          in_edge_iterator(pred, last, last));
williamr@2
   772
  }
williamr@2
   773
williamr@2
   774
  // O(1)
williamr@2
   775
  template <typename VP, typename EP, typename GP, typename A>
williamr@2
   776
  std::pair<
williamr@2
   777
    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator,
williamr@2
   778
    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator>
williamr@2
   779
  in_edges
williamr@2
   780
    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   781
     const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)
williamr@2
   782
  {
williamr@2
   783
    typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;
williamr@2
   784
    Graph& g = const_cast<Graph&>(g_);
williamr@2
   785
    typename Graph::vertices_size_type offset = u * (u + 1) / 2;
williamr@2
   786
    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
williamr@2
   787
    typename Graph::MatrixIter l = g.m_matrix.end();
williamr@2
   788
williamr@2
   789
    typename Graph::unfiltered_in_edge_iter
williamr@2
   790
        first(f, u, g.m_vertex_set.size())
williamr@2
   791
      , last(l, u, g.m_vertex_set.size());
williamr@2
   792
    
williamr@2
   793
    detail::does_edge_exist pred;
williamr@2
   794
    typedef typename Graph::in_edge_iterator in_edge_iterator;
williamr@2
   795
    return std::make_pair(in_edge_iterator(pred, first, last), 
williamr@2
   796
                          in_edge_iterator(pred, last, last));
williamr@2
   797
  }
williamr@2
   798
  
williamr@2
   799
  // O(N)
williamr@2
   800
  template <typename D, typename VP, typename EP, typename GP, typename A>  
williamr@2
   801
  typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
williamr@2
   802
  in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   803
             const adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
   804
  {
williamr@2
   805
    typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;
williamr@2
   806
    typename adjacency_matrix<D,VP,EP,GP,A>::in_edge_iterator f, l;
williamr@2
   807
    for (tie(f, l) = in_edges(u, g); f != l; ++f)
williamr@2
   808
      ++n;
williamr@2
   809
    return n;
williamr@2
   810
  }
williamr@2
   811
williamr@2
   812
  //=========================================================================
williamr@2
   813
  // Functions required by the AdjacencyGraph concept 
williamr@2
   814
williamr@2
   815
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   816
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator,
williamr@2
   817
            typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator>
williamr@2
   818
  adjacent_vertices
williamr@2
   819
    (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   820
     const adjacency_matrix<D,VP,EP,GP,A>& g_)
williamr@2
   821
  {
williamr@2
   822
      typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
williamr@2
   823
      const Graph& cg = static_cast<const Graph&>(g_);
williamr@2
   824
      Graph& g = const_cast<Graph&>(cg);
williamr@2
   825
      typedef typename Graph::adjacency_iterator adjacency_iterator;
williamr@2
   826
      typename Graph::out_edge_iterator first, last;
williamr@2
   827
      boost::tie(first, last) = out_edges(u, g);
williamr@2
   828
      return std::make_pair(adjacency_iterator(first, &g),
williamr@2
   829
                            adjacency_iterator(last, &g));
williamr@2
   830
  }
williamr@2
   831
williamr@2
   832
  //=========================================================================
williamr@2
   833
  // Functions required by the VertexListGraph concept 
williamr@2
   834
williamr@2
   835
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   836
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator,
williamr@2
   837
            typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator>
williamr@2
   838
  vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) {
williamr@2
   839
    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
williamr@2
   840
    Graph& g = const_cast<Graph&>(g_);
williamr@2
   841
    return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end());
williamr@2
   842
  }
williamr@2
   843
williamr@2
   844
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   845
  typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type
williamr@2
   846
  num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) {
williamr@2
   847
    return g.m_vertex_set.size();
williamr@2
   848
  }
williamr@2
   849
  
williamr@2
   850
  //=========================================================================
williamr@2
   851
  // Functions required by the EdgeListGraph concept 
williamr@2
   852
  
williamr@2
   853
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   854
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator,
williamr@2
   855
            typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator>
williamr@2
   856
  edges(const adjacency_matrix<D,VP,EP,GP,A>& g_)
williamr@2
   857
  {
williamr@2
   858
    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
williamr@2
   859
    Graph& g = const_cast<Graph&>(g_);
williamr@2
   860
    
williamr@2
   861
    typename Graph::unfiltered_edge_iter
williamr@2
   862
      first(g.m_matrix.begin(), g.m_matrix.begin(), 
williamr@2
   863
                                    g.m_vertex_set.size()),
williamr@2
   864
      last(g.m_matrix.end(), g.m_matrix.begin(), 
williamr@2
   865
                                    g.m_vertex_set.size());
williamr@2
   866
    detail::does_edge_exist pred;
williamr@2
   867
    typedef typename Graph::edge_iterator edge_iterator;
williamr@2
   868
    return std::make_pair(edge_iterator(pred, first, last),
williamr@2
   869
                          edge_iterator(pred, last, last));
williamr@2
   870
  }
williamr@2
   871
williamr@2
   872
  // O(1)
williamr@2
   873
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   874
  typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type
williamr@2
   875
  num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
   876
  {
williamr@2
   877
    return g.m_num_edges;
williamr@2
   878
  }
williamr@2
   879
  
williamr@2
   880
  //=========================================================================
williamr@2
   881
  // Functions required by the MutableGraph concept 
williamr@2
   882
williamr@2
   883
  // O(1)
williamr@2
   884
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   885
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
williamr@2
   886
  add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   887
           typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
williamr@2
   888
           const EP& ep,
williamr@2
   889
           adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
   890
  {
williamr@2
   891
    typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor 
williamr@2
   892
      edge_descriptor;
williamr@2
   893
    if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) {
williamr@2
   894
      ++(g.m_num_edges);
williamr@2
   895
      detail::set_property(g.get_edge(u,v), ep, 0);
williamr@2
   896
      detail::set_edge_exists(g.get_edge(u,v), true, 0);
williamr@2
   897
      return std::make_pair
williamr@2
   898
        (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))), 
williamr@2
   899
         true);
williamr@2
   900
    } else
williamr@2
   901
      return std::make_pair
williamr@2
   902
        (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
williamr@2
   903
         false);
williamr@2
   904
  }
williamr@2
   905
  // O(1)
williamr@2
   906
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   907
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
williamr@2
   908
  add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   909
           typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
williamr@2
   910
           adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
   911
  {
williamr@2
   912
    EP ep;
williamr@2
   913
    return add_edge(u, v, ep, g);
williamr@2
   914
  }
williamr@2
   915
williamr@2
   916
  // O(1)  
williamr@2
   917
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   918
  void
williamr@2
   919
  remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   920
              typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
williamr@2
   921
              adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
   922
  {
williamr@2
   923
    --(g.m_num_edges);
williamr@2
   924
    detail::set_edge_exists(g.get_edge(u,v), false, 0);
williamr@2
   925
  }
williamr@2
   926
williamr@2
   927
  // O(1)
williamr@2
   928
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   929
  void
williamr@2
   930
  remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e,
williamr@2
   931
              adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
   932
  {
williamr@2
   933
    remove_edge(source(e, g), target(e, g), g);
williamr@2
   934
  }
williamr@2
   935
williamr@2
   936
  
williamr@2
   937
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   938
  inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
williamr@2
   939
  add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) {
williamr@2
   940
    // UNDER CONSTRUCTION
williamr@2
   941
    assert(false);
williamr@2
   942
    return *vertices(g).first;
williamr@2
   943
  }
williamr@2
   944
williamr@2
   945
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   946
  inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
williamr@2
   947
  add_vertex(const VP& vp, adjacency_matrix<D,VP,EP,GP,A>& g) {
williamr@2
   948
    // UNDER CONSTRUCTION
williamr@2
   949
    assert(false);
williamr@2
   950
    return *vertices(g).first;
williamr@2
   951
  }
williamr@2
   952
williamr@2
   953
  template <typename D, typename VP, typename EP, typename GP, typename A>
williamr@2
   954
  inline void
williamr@2
   955
  remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   956
                adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
   957
  {
williamr@2
   958
    // UNDER CONSTRUCTION
williamr@2
   959
    assert(false);
williamr@2
   960
  }
williamr@2
   961
williamr@2
   962
  // O(V)
williamr@2
   963
  template <typename VP, typename EP, typename GP, typename A>
williamr@2
   964
  void
williamr@2
   965
  clear_vertex
williamr@2
   966
    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   967
     adjacency_matrix<directedS,VP,EP,GP,A>& g)
williamr@2
   968
  {
williamr@2
   969
    typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator 
williamr@2
   970
      vi, vi_end;
williamr@2
   971
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
williamr@2
   972
      remove_edge(u, *vi, g);
williamr@2
   973
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
williamr@2
   974
      remove_edge(*vi, u, g);
williamr@2
   975
  }
williamr@2
   976
williamr@2
   977
  // O(V)
williamr@2
   978
  template <typename VP, typename EP, typename GP, typename A>
williamr@2
   979
  void
williamr@2
   980
  clear_vertex
williamr@2
   981
    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
williamr@2
   982
     adjacency_matrix<undirectedS,VP,EP,GP,A>& g)
williamr@2
   983
  {
williamr@2
   984
    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator
williamr@2
   985
      vi, vi_end;
williamr@2
   986
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
williamr@2
   987
      remove_edge(u, *vi, g);
williamr@2
   988
  }
williamr@2
   989
williamr@2
   990
  //=========================================================================
williamr@2
   991
  // Vertex Property Map
williamr@2
   992
  
williamr@2
   993
  template <typename GraphPtr, typename Vertex, typename T, typename R, 
williamr@2
   994
    typename Tag> 
williamr@2
   995
  class adj_matrix_vertex_property_map 
williamr@2
   996
    : public put_get_helper<R,
williamr@2
   997
         adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> >
williamr@2
   998
  {
williamr@2
   999
  public:
williamr@2
  1000
    typedef T value_type;
williamr@2
  1001
    typedef R reference;
williamr@2
  1002
    typedef Vertex key_type;
williamr@2
  1003
    typedef boost::lvalue_property_map_tag category;
williamr@2
  1004
    adj_matrix_vertex_property_map() { }
williamr@2
  1005
    adj_matrix_vertex_property_map(GraphPtr g) : m_g(g) { }
williamr@2
  1006
    inline reference operator[](key_type v) const {
williamr@2
  1007
      return get_property_value(m_g->m_vertex_properties[v], Tag());
williamr@2
  1008
    }
williamr@2
  1009
    GraphPtr m_g;
williamr@2
  1010
  };
williamr@2
  1011
williamr@2
  1012
  template <class Property, class Vertex>
williamr@2
  1013
  struct adj_matrix_vertex_id_map
williamr@2
  1014
    : public boost::put_get_helper<Vertex,
williamr@2
  1015
        adj_matrix_vertex_id_map<Property, Vertex> >
williamr@2
  1016
  {
williamr@2
  1017
    typedef Vertex value_type;
williamr@2
  1018
    typedef Vertex reference;
williamr@2
  1019
    typedef Vertex key_type;
williamr@2
  1020
    typedef boost::readable_property_map_tag category;
williamr@2
  1021
     adj_matrix_vertex_id_map() { }
williamr@2
  1022
    template <class Graph>
williamr@2
  1023
    inline adj_matrix_vertex_id_map(const Graph&) { }
williamr@2
  1024
    inline value_type operator[](key_type v) const { return v; }
williamr@2
  1025
  };
williamr@2
  1026
williamr@2
  1027
  namespace detail {
williamr@2
  1028
williamr@2
  1029
    struct adj_matrix_any_vertex_pa {
williamr@2
  1030
      template <class Tag, class Graph, class Property>
williamr@2
  1031
      struct bind_ {
williamr@2
  1032
        typedef typename property_value<Property,Tag>::type Value;
williamr@2
  1033
        typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2
  1034
        
williamr@2
  1035
        typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&,
williamr@2
  1036
          Tag> type;
williamr@2
  1037
        typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value, 
williamr@2
  1038
          const Value&, Tag> const_type;
williamr@2
  1039
      };
williamr@2
  1040
    };
williamr@2
  1041
    struct adj_matrix_id_vertex_pa {
williamr@2
  1042
      template <class Tag, class Graph, class Property>
williamr@2
  1043
      struct bind_ {
williamr@2
  1044
        typedef typename Graph::vertex_descriptor Vertex;
williamr@2
  1045
        typedef adj_matrix_vertex_id_map<Property, Vertex> type;
williamr@2
  1046
        typedef adj_matrix_vertex_id_map<Property, Vertex> const_type;
williamr@2
  1047
      };
williamr@2
  1048
    };
williamr@2
  1049
williamr@2
  1050
    template <class Tag>
williamr@2
  1051
    struct adj_matrix_choose_vertex_pa_helper {
williamr@2
  1052
      typedef adj_matrix_any_vertex_pa type;
williamr@2
  1053
    };
williamr@2
  1054
    template <>
williamr@2
  1055
    struct adj_matrix_choose_vertex_pa_helper<vertex_index_t> {
williamr@2
  1056
      typedef adj_matrix_id_vertex_pa type;
williamr@2
  1057
    };
williamr@2
  1058
williamr@2
  1059
    template <class Tag, class Graph, class Property>
williamr@2
  1060
    struct adj_matrix_choose_vertex_pa {
williamr@2
  1061
      typedef typename adj_matrix_choose_vertex_pa_helper<Tag>::type Helper;
williamr@2
  1062
      typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
williamr@2
  1063
      typedef typename Bind::type type;
williamr@2
  1064
      typedef typename Bind::const_type const_type;
williamr@2
  1065
    };
williamr@2
  1066
williamr@2
  1067
    struct adj_matrix_vertex_property_selector {
williamr@2
  1068
      template <class Graph, class Property, class Tag>
williamr@2
  1069
      struct bind_ {
williamr@2
  1070
        typedef adj_matrix_choose_vertex_pa<Tag,Graph,Property> Choice;
williamr@2
  1071
        typedef typename Choice::type type;
williamr@2
  1072
        typedef typename Choice::const_type const_type;
williamr@2
  1073
      };
williamr@2
  1074
    };
williamr@2
  1075
williamr@2
  1076
  } // namespace detail
williamr@2
  1077
williamr@2
  1078
  template <>
williamr@2
  1079
  struct vertex_property_selector<adjacency_matrix_class_tag> {
williamr@2
  1080
    typedef detail::adj_matrix_vertex_property_selector type;
williamr@2
  1081
  };
williamr@2
  1082
  
williamr@2
  1083
  //=========================================================================
williamr@2
  1084
  // Edge Property Map
williamr@2
  1085
williamr@2
  1086
williamr@2
  1087
  template <typename Directed, typename Property, typename Vertex, 
williamr@2
  1088
    typename T, typename R, typename Tag> 
williamr@2
  1089
  class adj_matrix_edge_property_map 
williamr@2
  1090
    : public put_get_helper<R,
williamr@2
  1091
         adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> >
williamr@2
  1092
  {
williamr@2
  1093
  public:
williamr@2
  1094
    typedef T value_type;
williamr@2
  1095
    typedef R reference;
williamr@2
  1096
    typedef detail::matrix_edge_desc_impl<Directed, Vertex> key_type;
williamr@2
  1097
    typedef boost::lvalue_property_map_tag category;
williamr@2
  1098
    inline reference operator[](key_type e) const {
williamr@2
  1099
      Property& p = *(Property*)e.get_property();
williamr@2
  1100
      return get_property_value(p, Tag());
williamr@2
  1101
    }
williamr@2
  1102
  };
williamr@2
  1103
  struct adj_matrix_edge_property_selector {
williamr@2
  1104
    template <class Graph, class Property, class Tag>
williamr@2
  1105
    struct bind_ {
williamr@2
  1106
      typedef typename property_value<Property,Tag>::type T;
williamr@2
  1107
      typedef typename Graph::vertex_descriptor Vertex;
williamr@2
  1108
      typedef adj_matrix_edge_property_map<typename Graph::directed_category,
williamr@2
  1109
        Property, Vertex, T, T&, Tag> type;
williamr@2
  1110
      typedef adj_matrix_edge_property_map<typename Graph::directed_category,
williamr@2
  1111
        Property, Vertex, T, const T&, Tag> const_type;
williamr@2
  1112
    };
williamr@2
  1113
  };
williamr@2
  1114
  template <>
williamr@2
  1115
  struct edge_property_selector<adjacency_matrix_class_tag> {
williamr@2
  1116
    typedef adj_matrix_edge_property_selector type;
williamr@2
  1117
  };
williamr@2
  1118
williamr@2
  1119
  //=========================================================================
williamr@2
  1120
  // Functions required by PropertyGraph
williamr@2
  1121
williamr@2
  1122
  namespace detail {
williamr@2
  1123
williamr@2
  1124
    template <typename Property, typename D, typename VP, typename EP, 
williamr@2
  1125
              typename GP, typename A>
williamr@2
  1126
    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
williamr@2
  1127
      Property>::type
williamr@2
  1128
    get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property,
williamr@2
  1129
                 vertex_property_tag)
williamr@2
  1130
    {
williamr@2
  1131
      typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
williamr@2
  1132
      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
williamr@2
  1133
        Property>::type PA;
williamr@2
  1134
      return PA(&g);
williamr@2
  1135
    }
williamr@2
  1136
    template <typename Property, typename D, typename VP, typename EP, 
williamr@2
  1137
              typename GP, typename A>
williamr@2
  1138
    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
williamr@2
  1139
      Property>::type
williamr@2
  1140
    get_dispatch(adjacency_matrix<D,VP,EP,GP,A>&, Property,
williamr@2
  1141
                 edge_property_tag)
williamr@2
  1142
    {
williamr@2
  1143
      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
williamr@2
  1144
        Property>::type PA;
williamr@2
  1145
      return PA();
williamr@2
  1146
    }
williamr@2
  1147
    template <typename Property, typename D, typename VP, typename EP, 
williamr@2
  1148
              typename GP, typename A>
williamr@2
  1149
    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
williamr@2
  1150
      Property>::const_type
williamr@2
  1151
    get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>& g, Property,
williamr@2
  1152
                 vertex_property_tag)
williamr@2
  1153
    {
williamr@2
  1154
      typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
williamr@2
  1155
      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
williamr@2
  1156
        Property>::const_type PA;
williamr@2
  1157
      return PA(&g);
williamr@2
  1158
    }
williamr@2
  1159
    template <typename Property, typename D, typename VP, typename EP, 
williamr@2
  1160
              typename GP, typename A>
williamr@2
  1161
    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
williamr@2
  1162
      Property>::const_type
williamr@2
  1163
    get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>&, Property,
williamr@2
  1164
                 edge_property_tag)
williamr@2
  1165
    {
williamr@2
  1166
      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
williamr@2
  1167
        Property>::const_type PA;
williamr@2
  1168
      return PA();
williamr@2
  1169
    }
williamr@2
  1170
williamr@2
  1171
  } // namespace detail
williamr@2
  1172
williamr@2
  1173
  template <typename Property, typename D, typename VP, typename EP, 
williamr@2
  1174
            typename GP, typename A>
williamr@2
  1175
  inline
williamr@2
  1176
  typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::type
williamr@2
  1177
  get(Property p, adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
  1178
  {
williamr@2
  1179
    typedef typename property_kind<Property>::type Kind;
williamr@2
  1180
    return detail::get_dispatch(g, p, Kind());
williamr@2
  1181
  }
williamr@2
  1182
williamr@2
  1183
  template <typename Property, typename D, typename VP, typename EP, 
williamr@2
  1184
            typename GP, typename A>
williamr@2
  1185
  inline
williamr@2
  1186
  typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
williamr@2
  1187
  get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
  1188
  {
williamr@2
  1189
    typedef typename property_kind<Property>::type Kind;
williamr@2
  1190
    return detail::get_dispatch(g, p, Kind());
williamr@2
  1191
  }
williamr@2
  1192
williamr@2
  1193
  template <typename Property, typename D, typename VP, typename EP, 
williamr@2
  1194
            typename GP, typename A, typename Key>
williamr@2
  1195
  inline
williamr@2
  1196
  typename property_traits<
williamr@2
  1197
    typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
williamr@2
  1198
  >::value_type
williamr@2
  1199
  get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g,
williamr@2
  1200
      const Key& key)
williamr@2
  1201
  {
williamr@2
  1202
    return get(get(p, g), key);
williamr@2
  1203
  }
williamr@2
  1204
williamr@2
  1205
  template <typename Property, typename D, typename VP, typename EP, 
williamr@2
  1206
            typename GP, typename A, typename Key, typename Value>
williamr@2
  1207
  inline void
williamr@2
  1208
  put(Property p, adjacency_matrix<D,VP,EP,GP,A>& g,
williamr@2
  1209
      const Key& key, const Value& value)
williamr@2
  1210
  {
williamr@2
  1211
    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
williamr@2
  1212
    typedef typename boost::property_map<Graph, Property>::type Map;
williamr@2
  1213
    Map pmap = get(p, g);
williamr@2
  1214
    put(pmap, key, value);
williamr@2
  1215
  }
williamr@2
  1216
  
williamr@2
  1217
  //=========================================================================
williamr@2
  1218
  // Other Functions
williamr@2
  1219
williamr@2
  1220
  template <typename D, typename VP, typename EP, typename GP, typename A>  
williamr@2
  1221
  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
williamr@2
  1222
  vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n,
williamr@2
  1223
         const adjacency_matrix<D,VP,EP,GP,A>& g)
williamr@2
  1224
  {
williamr@2
  1225
    return n;
williamr@2
  1226
  }
williamr@2
  1227
williamr@2
  1228
  // Support for bundled properties
williamr@2
  1229
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2
  1230
  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
williamr@2
  1231
            typename Allocator, typename T, typename Bundle>
williamr@2
  1232
  inline
williamr@2
  1233
  typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
williamr@2
  1234
                        T Bundle::*>::type
williamr@2
  1235
  get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g)
williamr@2
  1236
  {
williamr@2
  1237
    typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
williamr@2
  1238
                                  T Bundle::*>::type
williamr@2
  1239
      result_type;
williamr@2
  1240
    return result_type(&g, p);
williamr@2
  1241
  }
williamr@2
  1242
williamr@2
  1243
  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
williamr@2
  1244
            typename Allocator, typename T, typename Bundle>
williamr@2
  1245
  inline
williamr@2
  1246
  typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
williamr@2
  1247
                        T Bundle::*>::const_type
williamr@2
  1248
  get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g)
williamr@2
  1249
  {
williamr@2
  1250
    typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
williamr@2
  1251
                                  T Bundle::*>::const_type
williamr@2
  1252
      result_type;
williamr@2
  1253
    return result_type(&g, p);
williamr@2
  1254
  }
williamr@2
  1255
    
williamr@2
  1256
  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
williamr@2
  1257
            typename Allocator, typename T, typename Bundle, typename Key>
williamr@2
  1258
  inline T
williamr@2
  1259
  get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g,
williamr@2
  1260
      const Key& key)
williamr@2
  1261
  {
williamr@2
  1262
    return get(get(p, g), key);
williamr@2
  1263
  }
williamr@2
  1264
williamr@2
  1265
  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
williamr@2
  1266
            typename Allocator, typename T, typename Bundle, typename Key>
williamr@2
  1267
  inline void
williamr@2
  1268
  put(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g,
williamr@2
  1269
      const Key& key, const T& value)
williamr@2
  1270
  {
williamr@2
  1271
    put(get(p, g), key, value);
williamr@2
  1272
  }
williamr@2
  1273
williamr@2
  1274
#endif
williamr@2
  1275
williamr@2
  1276
} // namespace boost
williamr@2
  1277
williamr@2
  1278
#endif // BOOST_ADJACENCY_MATRIX_HPP