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