]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(!(is_same<Directed, bidirectionalS>::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 |