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