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