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

source code of boost/boost/graph/adjacency_matrix.hpp