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