Debian Codegraph @

dune/istl/paamg/graph.hh

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5 #ifndef DUNE_AMG_GRAPH_HH
6 #define DUNE_AMG_GRAPH_HH
7
8 #include <cstddef>
9 #include <algorithm>
10 #include <vector>
11 #include <cassert>
12 #include <limits>
13 #include <dune/common/typetraits.hh>
14 #include <dune/common/iteratorfacades.hh>
15 #include <dune/istl/istlexception.hh>
16 #include <dune/common/propertymap.hh>
17
18 namespace Dune
19 {
20 namespace Amg
21 {
22 /**
23 * @addtogroup ISTL_PAAMG
24 *
25 * @{
26 */
27 /** @file
28 * @author Markus Blatt
29 * @brief Provides classes for building the matrix graph.
30 *
31 * During the coarsening process in AMG the matrix graph together
32 * with the dependencies, what connections in the graph are considered
33 * strong or weak, what vertices are isolated, etc., have to build.
34 * This information will be contained in the MatrixGraph class.
35 */
36
37 /**
38 * @brief The (undirected) graph of a matrix.
39 *
40 * The graph of a sparse matrix essentially describes the sparsity
41 * pattern (nonzero entries) of a matrix.
42 * It is assumed that the underlying sparsity pattern is symmetric,
43 * i.e if entry a_ij is present in the storage scheme of the matrix
44 * (i.e. nonzero) so is a_ji.
45 *
46 * The matrix entries can be accessed as weights of the vertices and
47 * edges.
48 */
49 template<class M>
50 class MatrixGraph
51 {
52 public:
53 /**
54 * @brief The type of the matrix we are a graph for.
55 */
56 typedef M Matrix;
57
58 /**
59 * @brief The mutable type of the matrix we are a graph for.
60 */
61 typedef typename std::remove_const<M>::type MutableMatrix;
62
63 /**
64 * @brief The type of the weights
65 */
66 typedef typename M::block_type Weight;
67
68 /**
69 * @brief The vertex descriptor.
70 *
71 * Each descriptor describes exactly one vertex.
72 */
73 typedef typename M::size_type VertexDescriptor;
74
75 /**
76 * @brief The edge descriptor.
77 *
78 * Each edge is identifies by exactly one descriptor.
79 */
80 typedef std::ptrdiff_t EdgeDescriptor;
81
82 enum {
83 /*
84 * @brief Whether Matrix is mutable.
85 */
86 mutableMatrix = std::is_same<M, typename std::remove_const<M>::type>::value
87 };
88
89
90 /**
91 * @brief Iterator over all edges starting from a vertex.
92 */
93 template<class C>
94 class EdgeIteratorT
95 {
96
97 public:
98 /**
99 * @brief The mutable type of the container type.
100 */
101 typedef typename std::remove_const<C>::type MutableContainer;
102 /**
103 * @brief The constant type of the container type.
104 */
105 typedef const typename std::remove_const<C>::type ConstContainer;
106
107 friend class EdgeIteratorT<MutableContainer>;
108 friend class EdgeIteratorT<ConstContainer>;
109
110 enum {
111 /** @brief whether C is mutable. */
112 isMutable = std::is_same<C, MutableContainer>::value
113 };
114
115 /**
116 * @brief The column iterator of the matrix we use.
117 */
118 typedef typename std::conditional<isMutable && C::mutableMatrix,typename Matrix::row_type::Iterator,
119 typename Matrix::row_type::ConstIterator>::type
120 ColIterator;
121
122 /**
123 * @brief The matrix block type we use as weights.
124 */
125 typedef typename std::conditional<isMutable && C::mutableMatrix,typename M::block_type,
126 const typename M::block_type>::type
127 Weight;
128
129 /**
130 * @brief Constructor.
131 * @param source The source vertex of the edges.
132 * @param block The matrix column block the iterator is initialized to,
133 * @param end The end iterator of the matrix row.
134 * @param edge The edge descriptor of the current edge.
135 */
136 EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block,
137 const ColIterator& end, const EdgeDescriptor& edge);
138
139 /**
140 * @brief Constructor for the end iterator.
141 *
142 * Variables not needed by operator== or operator!= will not be initialized.
143 * @param block The matrix column block the iterator is initialized to.
144 */
145 EdgeIteratorT(const ColIterator& block);
146
147 /**
148 * @brief Copy Constructor.
149 * @param other The iterator to copy.
150 */
151 template<class C1>
152 EdgeIteratorT(const EdgeIteratorT<C1>& other);
153
154 typedef typename std::conditional<std::is_same<C, typename std::remove_const<C>::type>::value && C::mutableMatrix,
155 typename M::block_type, const typename M::block_type>::type
156 WeightType;
157
158 /**
159 * @brief Access the edge weight
160 */
161 WeightType& weight() const;
162
163 /** @brief preincrement operator. */
164 EdgeIteratorT<C>& operator++();
165
166 /** @brief Inequality operator. */
167 bool operator!=(const EdgeIteratorT<typename std::remove_const<C>::type>& other) const;
168
169 /** @brief Inequality operator. */
170 bool operator!=(const EdgeIteratorT<const typename std::remove_const<C>::type>& other) const;
171
172 /** @brief Equality operator. */
173 bool operator==(const EdgeIteratorT<typename std::remove_const<C>::type>& other) const;
174
175 /** @brief Equality operator. */
176 bool operator==(const EdgeIteratorT<const typename std::remove_const<C>::type>& other) const;
177
178 /** @brief The index of the target vertex of the current edge. */
179 VertexDescriptor target() const;
180
181 /** @brief The index of the source vertex of the current edge. */
182 VertexDescriptor source() const;
183
184 /** @brief Get the edge descriptor. */
185 const EdgeDescriptor& operator*() const;
186
187 /** @brief Get the edge descriptor. */
188 const EdgeDescriptor* operator->() const;
189
190 private:
191 /** @brief Start vertex of the edges. */
192 VertexDescriptor source_;
193 /** @brief The column iterator describing the current edge. */
194 ColIterator block_;
195 /***
196 * @brief The column iterator positioned at the end of the row
197 * of vertex source_
198 */
199 ColIterator blockEnd_;
200 /** @brief The edge descriptor. */
201 EdgeDescriptor edge_;
202 };
203
204 /**
205 * @brief The vertex iterator type of the graph.
206 */
207 template<class C>
208 class VertexIteratorT
209 {
210 public:
211 /**
212 * @brief The mutable type of the container type.
213 */
214 typedef typename std::remove_const<C>::type MutableContainer;
215 /**
216 * @brief The constant type of the container type.
217 */
218 typedef const typename std::remove_const<C>::type ConstContainer;
219
220 friend class VertexIteratorT<MutableContainer>;
221 friend class VertexIteratorT<ConstContainer>;
222
223 enum {
224 /** @brief whether C is mutable. */
225 isMutable = std::is_same<C, MutableContainer>::value
226 };
227
228 /**
229 * @brief Constructor.
230 * @param graph The graph we are a vertex iterator for.
231 * @param current The current vertex to position on.
232 */
233 explicit VertexIteratorT(C* graph, const VertexDescriptor& current);
234
235 /**
236 * @brief Constructor for the end iterator.
237 *
238 * only operator== or operator!= may be called safely on an
239 * iterator constructed this way.
240 * @param current The current vertex to position on.
241 */
242 explicit VertexIteratorT(const VertexDescriptor& current);
243
244 VertexIteratorT(const VertexIteratorT<MutableContainer>& other);
245
246 /**
247 * @brief Move to the next vertex.
248 * @return This iterator positioned at the next vertex.
249 */
250 VertexIteratorT<C>& operator++();
251
252 /** @brief Inequality operator. */
253 bool operator!=(const VertexIteratorT<ConstContainer>& other) const;
254
255 /** @brief Equality operator. */
256 bool operator==(const VertexIteratorT<ConstContainer>& other) const;
257
258 /** @brief Inequality operator. */
259 bool operator!=(const VertexIteratorT<MutableContainer>& other) const;
260
261 /** @brief Equality operator. */
262 bool operator==(const VertexIteratorT<MutableContainer>& other) const;
263
264 typedef typename std::conditional<std::is_same<C, typename std::remove_const<C>::type>::value && C::mutableMatrix,
265 typename M::block_type, const typename M::block_type>::type
266 WeightType;
267 /** @brief Access the weight of the vertex. */
268 WeightType& weight() const;
269
270 /**
271 * @brief Get the descriptor of the current vertex.
272 * @return The index of the currently referenced vertex.
273 */
274 const VertexDescriptor& operator*() const;
275
276 /**
277 * @brief Get an iterator over all edges starting at the
278 * current vertex.
279 * @return Iterator position on the first edge to another vertex.
280 */
281 EdgeIteratorT<C> begin() const;
282
283 /**
284 * @brief Get an iterator over all edges starting at the
285 * current vertex.
286 * @return Iterator position on the first edge to another vertex.
287 */
288 EdgeIteratorT<C> end() const;
289
290 private:
291 C* graph_;
292 VertexDescriptor current_;
293 };
294
295 /**
296 * @brief The constant edge iterator type.
297 */
298 typedef EdgeIteratorT<const MatrixGraph<Matrix> > ConstEdgeIterator;
299
300 /**
301 * @brief The mutable edge iterator type.
302 */
303 typedef EdgeIteratorT<MatrixGraph<Matrix> > EdgeIterator;
304
305 /**
306 * @brief The constant vertex iterator type.
307 */
308 typedef VertexIteratorT<const MatrixGraph<Matrix> > ConstVertexIterator;
309
310 /**
311 * @brief The mutable vertex iterator type.
312 */
313 typedef VertexIteratorT<MatrixGraph<Matrix> > VertexIterator;
314
315 /**
316 * @brief Constructor.
317 * @param matrix The matrix we are a graph for.
318 */
319 MatrixGraph(Matrix& matrix);
320
321 /**
322 * @brief Destructor.
323 */
324 ~MatrixGraph();
325
326 /**
327 * @brief Get an iterator over the vertices.
328 * @return A vertex Iterator positioned at the first vertex.
329 */
330 VertexIterator begin();
331
332 /**
333 * @brief Get an iterator over the vertices.
334 * @return A vertex Iterator positioned behind the last vertex.
335 */
336 VertexIterator end();
337
338 /**
339 * @brief Get an iterator over the vertices.
340 * @return A vertex Iterator positioned at the first vertex.
341 */
342 ConstVertexIterator begin() const;
343
344 /**
345 * @brief Get an iterator over the vertices.
346 * @return A vertex Iterator positioned behind the last vertex.
347 */
348 ConstVertexIterator end() const;
349
350 /**
351 * @brief Get an iterator over the edges starting at a vertex.
352 * @param source The vertex where the edges should start.
353 * @return An edge iterator positioned at the first edge starting
354 * from vertex source.
355 */
356 EdgeIterator beginEdges(const VertexDescriptor& source);
357
358 /**
359 * @brief Get an iterator over the edges starting at a vertex.
360 * @param source The vertex where the edges should start.
361 * @return An edge iterator positioned behind the last edge starting
362 * from vertex source.
363 */
364 EdgeIterator endEdges(const VertexDescriptor& source);
365
366
367 /**
368 * @brief Get an iterator over the edges starting at a vertex.
369 * @param source The vertex where the edges should start.
370 * @return An edge iterator positioned at the first edge starting
371 * from vertex source.
372 */
373 ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
374
375 /**
376 * @brief Get an iterator over the edges starting at a vertex.
377 * @param source The vertex where the edges should start.
378 * @return An edge iterator positioned behind the last edge starting
379 * from vertex source.
380 */
381 ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
382
383 /**
384 * @brief Get the underlying matrix.
385 * @return The matrix of the graph.
386 */
387 Matrix& matrix();
388
389 /**
390 * @brief Get the underlying matrix.
391 * @return The matrix of the graph.
392 */
393 const Matrix& matrix() const;
394
395 /**
396 * @brief Get the number of vertices in the graph.
397 */
398 std::size_t noVertices() const;
399
400 /**
401 * @brief Get the maximal vertex descriptor.
402 *
403 * @return The minimum value v such that for
404 * all vertices w in the graph w&lt;v holds.
405 */
406 VertexDescriptor maxVertex() const;
407
408 /**
409 * @brief Get the number of edges in the graph.
410 */
411 std::size_t noEdges() const;
412
413 /**
414 * @brief Find the descriptor of an edge.
415 * @param source The source vertex of the edge we search for.
416 * @param target The target vertex of the edge we search for.
417 * @return The edge we found or numeric_limits<EdgeIterator>::max() if it does not exist.
418 */
419 EdgeDescriptor findEdge(const VertexDescriptor& source,
420 const VertexDescriptor& target) const;
421
422 private:
423 /** @brief The matrix we are the graph for. */
424 Matrix& matrix_;
425 /** @brief The edge descriptor of the first edge of each row. */
426 EdgeDescriptor* start_;
427 /** Prevent copying. */
428 MatrixGraph(const MatrixGraph&);
429
430 };
431
432 /**
433 * @brief A subgraph of a graph.
434 *
435 * This is a (cached) view of a graph where certain
436 * vertices and edges pointing to and leading from them
437 * are skipped.
438 *
439 * The vertex descriptors are not changed.
440 */
441 template<class G, class T>
442 class SubGraph
443 {
444 public:
445 /**
446 * @brief The type of the graph we are a sub graph for.
447 */
448 typedef G Graph;
449
450 /**
451 * @brief Random access container providing information about
452 * which vertices are excluded.
453 */
454 typedef T Excluded;
455
456 /**
457 * @brief The vertex descriptor.
458 */
459 typedef typename Graph::VertexDescriptor VertexDescriptor;
460
461 typedef VertexDescriptor* EdgeDescriptor;
462
463 /**
464 * @brief An index map for mapping the edges to indices.
465 *
466 * This should be used for attaching properties to a SubGraph
467 * using VertexPropertiesGraph od PropertiesGraph.
468 */
469 class EdgeIndexMap
470 {
471 public:
472 typedef ReadablePropertyMapTag Category;
473
474 EdgeIndexMap(const EdgeDescriptor& firstEdge)
475 : firstEdge_(firstEdge)
476 {}
477
478 /** @brief Protect copy construction. */
479 EdgeIndexMap(const EdgeIndexMap& emap)
480 : firstEdge_(emap.firstEdge_)
481 {}
482
483 std::size_t operator[](const EdgeDescriptor& edge) const
484 {
485 return edge-firstEdge_;
486 }
487 private:
488 /** @brief The first edge of the graph. */
489 EdgeDescriptor firstEdge_;
490 /** @brief Protect default construction. */
491 EdgeIndexMap()
492 {}
493 };
494
495 /**
496 * @brief Get an edge index map for the graph.
497 * @return An edge index map for the graph.
498 */
499 EdgeIndexMap getEdgeIndexMap();
500
501 /**
502 * @brief The edge iterator of the graph.
503 */
504 class EdgeIterator : public RandomAccessIteratorFacade<EdgeIterator,const EdgeDescriptor>
505 {
506 public:
507 /**
508 * @brief Constructor.
509 * @param source The source vertex of the edge.
510 * @param edge Pointer to the edge the iterator should point to.
511 */
512 explicit EdgeIterator(const VertexDescriptor& source, const EdgeDescriptor& edge);
513
514 /**
515 * @brief Constructor for the end iterator.
516 *
517 * Only operator== or operator!= can be called safely on an iterator constructed
518 * this way!
519 * @param edge Pointer to the end of the graph's edge array.
520 */
521 explicit EdgeIterator(const EdgeDescriptor& edge);
522
523 /** @brief Equality operator. */
524 bool equals(const EdgeIterator& other) const;
525
526 /** @brief Preincrement operator. */
527 EdgeIterator& increment();
528
529 /** @brief Preincrement operator. */
530 EdgeIterator& decrement();
531
532 EdgeIterator& advance(std::ptrdiff_t n);
533
534 /** @brief The descriptor of the current edge. */
535 const EdgeDescriptor& dereference() const;
536
537 /** @brief The index of the target vertex of the current edge. */
538 const VertexDescriptor& target() const;
539
540 /** @brief The index of the source vertex of the current edge. */
541 const VertexDescriptor& source() const;
542
543 std::ptrdiff_t distanceTo(const EdgeIterator& other) const;
544
545 private:
546 /** @brief The source vertex of the edge. */
547 VertexDescriptor source_;
548 /**
549 * @brief The offset of the current edge to the first
550 * one starting at the vertex source_.
551 */
552 EdgeDescriptor edge_;
553 };
554
555 /**
556 * @brief The vertex iterator of the graph.
557 */
558 class VertexIterator
559 : public ForwardIteratorFacade<VertexIterator,const VertexDescriptor>
560 {
561 public:
562 /**
563 * @brief Constructor.
564 * @param graph The graph over whose vertices to iterate.
565 * @param current The position of the iterator.
566 * @param end The last vertex of the graph.
567 */
568 explicit VertexIterator(const SubGraph<G,T>* graph, const VertexDescriptor& current,
569 const VertexDescriptor& end);
570
571
572 /**
573 * @brief Constructor for end iterator.
574 *
575 * Use with care! All operations except operator== or operator!= will fail!
576 * @param current The position of the iterator.
577 */
578 explicit VertexIterator(const VertexDescriptor& current);
579
580 /** @brief Preincrement operator. */
581 VertexIterator& increment();
582
583 /** @brief Equality iterator. */
584 bool equals(const VertexIterator& other) const;
585
586 /**
587 * @brief Get the descriptor of the current vertex.
588 * @return The index of the currently referenced vertex.
589 */
590 const VertexDescriptor& dereference() const;
591
592 /**
593 * @brief Get an iterator over all edges starting at the
594 * current vertex.
595 * @return Iterator position on the first edge to another vertex.
596 */
597 EdgeIterator begin() const;
598
599 /**
600 * @brief Get an iterator over all edges starting at the
601 * current vertex.
602 * @return Iterator position on the first edge to another vertex.
603 */
604 EdgeIterator end() const;
605
606 private:
607 /** @brief The graph we are a vertex iterator for. */
608 const SubGraph<Graph,T>* graph_;
609 /** @brief The current position. */
610 VertexDescriptor current_;
611 /** @brief The number of vertices of the graph. */
612 VertexDescriptor end_;
613 };
614
615 /**
616 * @brief The constant edge iterator type.
617 */
618 typedef EdgeIterator ConstEdgeIterator;
619
620 /**
621 * @brief The constant vertex iterator type.
622 */
623 typedef VertexIterator ConstVertexIterator;
624
625 /**
626 * @brief Get an iterator over the vertices.
627 * @return A vertex Iterator positioned at the first vertex.
628 */
629 ConstVertexIterator begin() const;
630
631 /**
632 * @brief Get an iterator over the vertices.
633 * @return A vertex Iterator positioned behind the last vertex.
634 */
635 ConstVertexIterator end() const;
636
637 /**
638 * @brief Get an iterator over the edges starting at a vertex.
639 * @param source The vertex where the edges should start.
640 * @return An edge iterator positioned at the first edge starting
641 * from vertex source.
642 */
643 ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
644
645 /**
646 * @brief Get an iterator over the edges starting at a vertex.
647 * @param source The vertex where the edges should start.
648 * @return An edge iterator positioned behind the last edge starting
649 * from vertex source.
650 */
651 ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
652
653 /**
654 * @brief Get the number of vertices in the graph.
655 */
656 std::size_t noVertices() const;
657
658 /**
659 * @brief Get the maximal vertex descriptor.
660 *
661 * @return The minimum value v such that for
662 * all vertices w in the graph w&lt;v holds.
663 */
664 VertexDescriptor maxVertex() const;
665
666 /**
667 * @brief Get the number of edges in the graph.
668 */
669 std::size_t noEdges() const;
670 /**
671 * @brief Find the descriptor of an edge.
672 * @param source The source vertex of the edge we search for.
673 * @param target The target vertex of the edge we search for.
674 * @return The edge we found or numeric_limits<EdgeIterator>::max() if it does not exist.
675 */
676 EdgeDescriptor findEdge(const VertexDescriptor& source,
677 const VertexDescriptor& target) const;
678 /**
679 * @brief Constructor.
680 *
681 * @param graph The graph we are a sub graph for.
682 * @param excluded If excluded[i] is true then vertex i will not appear
683 * in the sub graph.
684 */
685 SubGraph(const Graph& graph, const T& excluded);
686
687 /**
688 * @brief Destructor.
689 */
690 ~SubGraph();
691
692 private:
693 /** @brief flags indication which vertices are excluded. */
694 const T& excluded_;
695 /** @brief The number of vertices in this sub graph. */
696 std::size_t noVertices_;
697 /** @brief Vertex behind the last valid vertex of this sub graph. */
698 VertexDescriptor endVertex_;
699 /** @brief The number of edges in this sub graph.*/
700 int noEdges_;
701 /**
702 * @brief The maximum vertex descriptor of the graph
703 * we are a subgraph for.
704 */
705 VertexDescriptor maxVertex_;
706 /** @brief The edges of this sub graph. */
707 VertexDescriptor* edges_;
708 /** @brief The start of the out edges of each vertex. */
709 std::ptrdiff_t* start_;
710 /** @brief The edge behind the last out edge of each vertex. */
711 std::ptrdiff_t* end_;
712 /** prevent copying */
713 SubGraph(const SubGraph&)
714 {}
715 };
716
717
718 /**
719 * @brief Attaches properties to the vertices of a graph.
720 */
721 template<class G, class VP, class VM=IdentityMap>
722 class VertexPropertiesGraph
723 {
724 public:
725 /**
726 * @brief The graph we attach properties to.
727 */
728 typedef G Graph;
729
730 /**
731 * @brief The vertex descriptor.
732 */
733 typedef typename Graph::VertexDescriptor VertexDescriptor;
734
735 /**
736 * @brief The edge descritor.
737 */
738 typedef typename Graph::EdgeDescriptor EdgeDescriptor;
739
740 /**
741 * @brief The type of the properties of the vertices.
742 */
743 typedef VP VertexProperties;
744
745 /**
746 * @brief The type of the map for converting the VertexDescriptor
747 * to std::size_t
748 *
749 * Has to provide the following method:
750 * std::size_t operator[](const VertexDescriptor& vertex)
751 *
752 * The following condition has to be met:
753 * Let v1 and v2 be two vertex descriptors with v1 < v2 and map be the
754 * index map. Then map[v1]<map[v2] has to hold.
755 */
756 typedef VM VertexMap;
757
758 /**
759 * @brief The type of the mutable edge iterator.
760 */
761 typedef typename Graph::EdgeIterator EdgeIterator;
762
763 /**
764 * @brief The type of the constant edge iterator.
765 */
766 typedef typename Graph::ConstEdgeIterator ConstEdgeIterator;
767
768 /**
769 * @brief Get the mutable edge iterator over edges starting at a vertex.
770 * @return An edge iterator over edges starting at a vertex
771 * positioned at the first edge.
772 */
773 EdgeIterator beginEdges(const VertexDescriptor& source);
774
775 /**
776 * @brief Get the mutable edge iterator over edges starting at a vertex.
777 * @return An edge iterator over edges starting at a vertex
778 * positioned after the last edge.
779 */
780 EdgeIterator endEdges(const VertexDescriptor& source);
781
782 /**
783 * @brief Get the mutable edge iterator over edges starting at a vertex.
784 * @return An edge iterator over edges starting at a vertex
785 * positioned at the first edge.
786 */
787 ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
788
789 /**
790 * @brief Get the mutable edge iterator over edges starting at a vertex.
791 * @return An edge iterator over edges starting at a vertex
792 * positioned after the last edge.
793 */
794 ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
795
796
797 template<class C>
798 class VertexIteratorT
799 : public std::conditional<std::is_same<typename std::remove_const<C>::type,
800 C>::value,
801 typename Graph::VertexIterator,
802 typename Graph::ConstVertexIterator>::type
803 {
804 friend class VertexIteratorT<const typename std::remove_const<C>::type>;
805 friend class VertexIteratorT<typename std::remove_const<C>::type>;
806 public:
807 /**
808 * @brief The father class.
809 */
810 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
811 C>::value,
812 typename Graph::VertexIterator,
813 typename Graph::ConstVertexIterator>::type
814 Father;
815
816 /**
817 * @brief The class of the edge iterator.
818 */
819 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
820 C>::value,
821 typename Graph::EdgeIterator,
822 typename Graph::ConstEdgeIterator>::type
823 EdgeIterator;
824
825 /**
826 * @brief Constructor.
827 * @param iter The iterator of the underlying graph.
828 * @param graph The property graph over whose vertices we iterate.
829 */
830 explicit VertexIteratorT(const Father& iter,
831 C* graph);
832
833
834 /**
835 * @brief Constructor for the end iterator.
836 *
837 * Only operator!= or operator== can be called safely on an iterator
838 * constructed this way.
839 * @param iter The iterator of the underlying graph.
840 */
841 explicit VertexIteratorT(const Father& iter);
842
843 /**
844 * @brief Copy Constructor.
845 * @param other The iterator to copy.
846 */
847 template<class C1>
848 VertexIteratorT(const VertexIteratorT<C1>& other);
849
850 /**
851 * @brief Get the properties of the current Vertex.
852 */
853 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
854 VertexProperties&,
855 const VertexProperties&>::type
856 properties() const;
857
858 /**
859 * @brief Get an iterator over the edges starting from the current vertex.
860 * @return An iterator over the edges starting from the current vertex
861 * positioned at the first edge.
862 */
863 EdgeIterator begin() const;
864
865 /**
866 * @brief Get an iterator over the edges starting from the current vertex.
867 * @return An iterator over the edges starting from the current vertex
868 * positioned after the last edge.
869 */
870 EdgeIterator end() const;
871
872 private:
873 /**
874 * @brief The graph over whose vertices we iterate.
875 */
876 C* graph_;
877 };
878
879 /**
880 * @brief The type of the mutable Vertex iterator.
881 */
882 typedef VertexIteratorT<VertexPropertiesGraph<Graph,
883 VertexProperties,VM> > VertexIterator;
884
885 /**
886 * @brief The type of the constant Vertex iterator.
887 */
888 typedef VertexIteratorT<const VertexPropertiesGraph<Graph,
889 VertexProperties,VM> > ConstVertexIterator;
890
891 /**
892 * @brief Get an iterator over the vertices.
893 * @return A vertex Iterator positioned at the first vertex.
894 */
895 VertexIterator begin();
896
897 /**
898 * @brief Get an iterator over the vertices.
899 * @return A vertex Iterator positioned behind the last vertex.
900 */
901 VertexIterator end();
902
903 /**
904 * @brief Get an iterator over the vertices.
905 * @return A vertex Iterator positioned at the first vertex.
906 */
907 ConstVertexIterator begin() const;
908
909 /**
910 * @brief Get an iterator over the vertices.
911 * @return A vertex Iterator positioned behind the last vertex.
912 */
913 ConstVertexIterator end() const;
914
915 /**
916 * @brief Get the properties associated with a vertex.
917 * @param vertex The descriptor identifying the vertex.
918 * @return The properties of the vertex.
919 */
920 VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
921
922 /**
923 * @brief Get the properties associated with a vertex.
924 * @param vertex The descriptor identifying the vertex.
925 * @return The properties of the vertex.
926 */
927 const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
928
929 /**
930 * @brief Get the graph the properties are attached to.
931 * @return The underlying graph.
932 */
933 const Graph& graph() const;
934
935 /**
936 * @brief Get the number of vertices in the graph.
937 */
938 std::size_t noVertices() const;
939
940 /**
941 * @brief Get the number of edges in the graph.
942 */
943 std::size_t noEdges() const;
944
945 /**
946 * @brief Get the maximal vertex descriptor.
947 *
948 * @return The minimum value v such that for
949 * all vertices w in the graph w&lt;v holds.
950 */
951 VertexDescriptor maxVertex() const;
952
953 /**
954 * @brief Constructor.
955 * @param graph The graph we attach properties to.
956 * @param vmap The vertex map.
957 */
958 VertexPropertiesGraph(Graph& graph, const VertexMap vmap=VertexMap());
959
960 private:
961 VertexPropertiesGraph(const VertexPropertiesGraph&)
962 {}
963
964 /** @brief The graph the properties are attached to. */
965 Graph& graph_;
966 /** @brief The vertex map. */
967 VertexMap vmap_;
968 /** @brief The vertex properties. */
969 std::vector<VertexProperties> vertexProperties_;
970
971 };
972
973 /**
974 * @brief Attaches properties to the edges and vertices of a graph.
975 */
976 template<class G, class VP, class EP, class VM=IdentityMap, class EM=IdentityMap>
977 class PropertiesGraph
978 {
979 public:
980 /**
981 * @brief The graph we attach properties to.
982 */
983 typedef G Graph;
984
985 /**
986 * @brief The vertex descriptor.
987 */
988 typedef typename Graph::VertexDescriptor VertexDescriptor;
989
990 /**
991 * @brief The edge descritor.
992 */
993 typedef typename Graph::EdgeDescriptor EdgeDescriptor;
994
995 /**
996 * @brief The type of the properties of the vertices.
997 */
998 typedef VP VertexProperties;
999
1000 /**
1001 * @brief The type of the map for converting the VertexDescriptor
1002 * to std::size_t
1003 *
1004 * Has to provide the following method:
1005 * std::size_t operator[](const VertexDescriptor& vertex)
1006 *
1007 * The following condition has to be met:
1008 * Let v1 and v2 be two vertex descriptors with v1 < v2 and map be the
1009 * index map. Then map[v1]<map[v2] has to hold.
1010 */
1011 typedef VM VertexMap;
1012
1013 /**
1014 * @brief The type of the properties of the edges;
1015 */
1016 typedef EP EdgeProperties;
1017
1018
1019 /**
1020 * @brief The type of the map for converting the EdgeDescriptor
1021 * to std::size_t.
1022 *
1023 * Has to provide the following method:
1024 * std::size_t operator[](const EdgeDescriptor& vertex)
1025 *
1026 * The following condition has to be met:
1027 * Let e1 and e2 be two edge descriptors, e1 < e2, and map be the
1028 * index map. Then map[v1]<map[v2] has to hold.
1029 */
1030 typedef EM EdgeMap;
1031
1032 template<class C>
1033 class EdgeIteratorT
1034 : public std::conditional<std::is_same<typename std::remove_const<C>::type,
1035 C>::value,
1036 typename Graph::EdgeIterator,
1037 typename Graph::ConstEdgeIterator>::type
1038 {
1039
1040 friend class EdgeIteratorT<const typename std::remove_const<C>::type>;
1041 friend class EdgeIteratorT<typename std::remove_const<C>::type>;
1042 public:
1043 /**
1044 * @brief The father class.
1045 */
1046 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
1047 C>::value,
1048 typename Graph::EdgeIterator,
1049 typename Graph::ConstEdgeIterator>::type
1050 Father;
1051
1052 /**
1053 * @brief Constructor.
1054 * @param iter The iterator of the underlying graph.
1055 * @param graph The graph over whose edges we iterate on.
1056 */
1057 explicit EdgeIteratorT(const Father& iter,
1058 C* graph);
1059
1060 /**
1061 * @brief Constructor for the end iterator.
1062 *
1063 * Only operator== or operator!= should be called on
1064 * an iterator constructed this way.
1065 * @param iter The iterator of the underlying graph.
1066 */
1067 explicit EdgeIteratorT(const Father& iter);
1068
1069 /**
1070 * @brief Copy constructor.
1071 * @param other the iterator to copy.
1072 */
1073 template<class C1>
1074 EdgeIteratorT(const EdgeIteratorT<C1>& other);
1075
1076 /**
1077 * @brief Get the properties of the current edge.
1078 */
1079 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
1080 EdgeProperties&,
1081 const EdgeProperties&>::type
1082 properties() const;
1083
1084 private:
1085 /**
1086 * @brief The graph over whose edges we iterate.
1087 */
1088 C* graph_;
1089 };
1090
1091 /**
1092 * @brief The type of the mutable edge iterator.
1093 */
1094 typedef EdgeIteratorT<PropertiesGraph<Graph,
1095 VertexProperties,
1096 EdgeProperties,VM,EM> > EdgeIterator;
1097
1098 /**
1099 * @brief The type of the constant edge iterator.
1100 */
1101 typedef EdgeIteratorT<const PropertiesGraph<Graph,
1102 VertexProperties,
1103 EdgeProperties,VM,EM> > ConstEdgeIterator;
1104
1105 /**
1106 * @brief Get the mutable edge iterator over edges starting at a vertex.
1107 * @return An edge iterator over edges starting at a vertex
1108 * positioned at the first edge.
1109 */
1110 EdgeIterator beginEdges(const VertexDescriptor& source);
1111
1112 /**
1113 * @brief Get the mutable edge iterator over edges starting at a vertex.
1114 * @return An edge iterator over edges starting at a vertex
1115 * positioned after the last edge.
1116 */
1117 EdgeIterator endEdges(const VertexDescriptor& source);
1118
1119 /**
1120 * @brief Get the mutable edge iterator over edges starting at a vertex.
1121 * @return An edge iterator over edges starting at a vertex
1122 * positioned at the first edge.
1123 */
1124 ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
1125
1126 /**
1127 * @brief Get the mutable edge iterator over edges starting at a vertex.
1128 * @return An edge iterator over edges starting at a vertex
1129 * positioned after the last edge.
1130 */
1131 ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
1132
1133
1134 template<class C>
1135 class VertexIteratorT
1136 : public std::conditional<std::is_same<typename std::remove_const<C>::type,
1137 C>::value,
1138 typename Graph::VertexIterator,
1139 typename Graph::ConstVertexIterator>::type
1140 {
1141 friend class VertexIteratorT<const typename std::remove_const<C>::type>;
1142 friend class VertexIteratorT<typename std::remove_const<C>::type>;
1143 public:
1144 /**
1145 * @brief The father class.
1146 */
1147 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
1148 C>::value,
1149 typename Graph::VertexIterator,
1150 typename Graph::ConstVertexIterator>::type
1151 Father;
1152
1153 /**
1154 * @brief Constructor.
1155 * @param iter The iterator of the underlying graph.
1156 * @param graph The property graph over whose vertices we iterate.
1157 */
1158 explicit VertexIteratorT(const Father& iter,
1159 C* graph);
1160
1161
1162 /**
1163 * @brief Constructor for the end iterator.
1164 *
1165 * Only operator!= or operator== can be called safely on an iterator
1166 * constructed this way.
1167 * @param iter The iterator of the underlying graph.
1168 */
1169 explicit VertexIteratorT(const Father& iter);
1170
1171 /**
1172 * @brief Copy Constructor.
1173 * @param other The iterator to copy.
1174 */
1175 template<class C1>
1176 VertexIteratorT(const VertexIteratorT<C1>& other);
1177
1178 /**
1179 * @brief Get the properties of the current Vertex.
1180 */
1181 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
1182 VertexProperties&,
1183 const VertexProperties&>::type
1184 properties() const;
1185
1186 /**
1187 * @brief Get an iterator over the edges starting from the current vertex.
1188 * @return An iterator over the edges starting from the current vertex
1189 * positioned at the first edge.
1190 */
1191 EdgeIteratorT<C> begin() const;
1192
1193 /**
1194 * @brief Get an iterator over the edges starting from the current vertex.
1195 * @return An iterator over the edges starting from the current vertex
1196 * positioned after the last edge.
1197 */
1198 EdgeIteratorT<C> end() const;
1199
1200 private:
1201 /**
1202 * @brief The graph over whose vertices we iterate.
1203 */
1204 C* graph_;
1205 };
1206
1207 /**
1208 * @brief The type of the mutable Vertex iterator.
1209 */
1210 typedef VertexIteratorT<PropertiesGraph<Graph,
1211 VertexProperties,
1212 EdgeProperties,VM,EM> > VertexIterator;
1213
1214 /**
1215 * @brief The type of the constant Vertex iterator.
1216 */
1217 typedef VertexIteratorT<const PropertiesGraph<Graph,
1218 VertexProperties,
1219 EdgeProperties,VM,EM> > ConstVertexIterator;
1220
1221 /**
1222 * @brief Get an iterator over the vertices.
1223 * @return A vertex Iterator positioned at the first vertex.
1224 */
1225 VertexIterator begin();
1226
1227 /**
1228 * @brief Get an iterator over the vertices.
1229 * @return A vertex Iterator positioned behind the last vertex.
1230 */
1231 VertexIterator end();
1232
1233 /**
1234 * @brief Get an iterator over the vertices.
1235 * @return A vertex Iterator positioned at the first vertex.
1236 */
1237 ConstVertexIterator begin() const;
1238
1239 /**
1240 * @brief Get an iterator over the vertices.
1241 * @return A vertex Iterator positioned behind the last vertex.
1242 */
1243 ConstVertexIterator end() const;
1244
1245 /**
1246 * @brief Get the properties associated with a vertex.
1247 * @param vertex The descriptor identifying the vertex.
1248 * @return The properties of the vertex.
1249 */
1250 VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
1251
1252 /**
1253 * @brief Get the properties associated with a vertex.
1254 * @param vertex The descriptor identifying the vertex.
1255 * @return The properties of the vertex.
1256 */
1257 const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
1258
1259 /**
1260 * @brief Find the descriptor of an edge.
1261 * @param source The source vertex of the edge we search for.
1262 * @param target The target vertex of the edge we search for.
1263 * @return The edge we found or numeric_limits<EdgeIterator>::max() if it does not exist.
1264 */
1265 EdgeDescriptor findEdge(const VertexDescriptor& source,
1266 const VertexDescriptor& target)
1267 {
1268 return graph_.findEdge(source,target);
1269 }
1270
1271 /**
1272 * @brief Get the properties associated with a edge.
1273 * @param edge The descriptor identifying the edge.
1274 * @return The properties of the edge.
1275 */
1276 EdgeProperties& getEdgeProperties(const EdgeDescriptor& edge);
1277
1278
1279 /**
1280 * @brief Get the properties associated with a edge.
1281 * @param edge The descriptor identifying the edge.
1282 * @return The properties of the edge.
1283 */
1284 const EdgeProperties& getEdgeProperties(const EdgeDescriptor& edge) const;
1285
1286 /**
1287 * @brief Get the properties associated with a edge.
1288 * @param source The descriptor identifying the source vertex of the edge.
1289 * @param target The descriptor identifying the target vertex of the edge.
1290 * @return The properties of the edge.
1291 */
1292 EdgeProperties& getEdgeProperties(const VertexDescriptor& source,
1293 const VertexDescriptor& target);
1294
1295 /**
1296 * @brief Get the properties associated with a edge.
1297 * @param source The descriptor identifying the source vertex of the edge.
1298 * @param target The descriptor identifying the target vertex of the edge.
1299 * @return The properties of the edge.
1300 */
1301 const EdgeProperties& getEdgeProperties(const VertexDescriptor& source,
1302 const VertexDescriptor& target) const;
1303
1304 /**
1305 * @brief Get the graph the properties are attached to.
1306 * @return The underlying graph.
1307 */
1308 const Graph& graph() const;
1309
1310 /**
1311 * @brief Get the number of vertices in the graph.
1312 */
1313 std::size_t noVertices() const;
1314
1315 /**
1316 * @brief Get the number of edges in the graph.
1317 */
1318 std::size_t noEdges() const;
1319
1320 /**
1321 * @brief Get the maximal vertex descriptor.
1322 *
1323 * @return The minimum value v such that for
1324 * all vertices w in the graph w&lt;v holds.
1325 */
1326 VertexDescriptor maxVertex() const;
1327
1328 /**
1329 * @brief Constructor.
1330 * @param graph The graph we attach properties to.
1331 * @param vmap The map of the vertices onto indices.
1332 * @param emap The map of the edges onto indices.
1333 */
1334 PropertiesGraph(Graph& graph, const VertexMap& vmap=VertexMap(),
1335 const EdgeMap& emap=EdgeMap());
1336
1337 private:
1338 PropertiesGraph(const PropertiesGraph&)
1339 {}
1340
1341 /** @brief The graph the properties are attached to. */
1342 Graph& graph_;
1343 /** @brief The vertex properties. */
1344 /** @brief The mapping of the vertices to indices. */
1345 VertexMap vmap_;
1346 std::vector<VertexProperties> vertexProperties_;
1347 /** @brief The mapping of the edges to indices. */
1348 EdgeMap emap_;
1349 /** @brief The edge properties. */
1350 std::vector<EdgeProperties> edgeProperties_;
1351
1352 };
1353
1354
1355 /**
1356 * @brief Wrapper to access the internal edge properties of a graph
1357 * via operator[]()
1358 */
1359 template<typename G>
1360 class GraphVertexPropertiesSelector
1361 {
1362 public:
1363 /**
1364 * @brief The type of the graph with internal properties.
1365 */
1366 typedef G Graph;
1367 /**
1368 * @brief The type of the vertex properties.
1369 */
1370 typedef typename G::VertexProperties VertexProperties;
1371 /**
1372 * @brief The vertex descriptor.
1373 */
1374 typedef typename G::VertexDescriptor Vertex;
1375
1376 /**
1377 * @brief Constructor.
1378 * @param g The graph whose properties we access.
1379 */
1380 GraphVertexPropertiesSelector(G& g)
1381 : graph_(g)
1382 {}
1383 /**
1384 * @brief Default constructor.
1385 */
1386 GraphVertexPropertiesSelector()
1387 : graph_(0)
1388 {}
1389
1390
1391 /**
1392 * @brief Get the properties associated to a vertex.
1393 * @param vertex The vertex whose Properties we want.
1394 */
1395 VertexProperties& operator[](const Vertex& vertex) const
1396 {
1397 return graph_->getVertexProperties(vertex);
1398 }
1399 private:
1400 Graph* graph_;
1401 };
1402
1403 /**
1404 * @brief Wrapper to access the internal vertex properties of a graph
1405 * via operator[]()
1406 */
1407 template<typename G>
1408 class GraphEdgePropertiesSelector
1409 {
1410 public:
1411 /**
1412 * @brief The type of the graph with internal properties.
1413 */
1414 typedef G Graph;
1415 /**
1416 * @brief The type of the vertex properties.
1417 */
1418 typedef typename G::EdgeProperties EdgeProperties;
1419 /**
1420 * @brief The edge descriptor.
1421 */
1422 typedef typename G::EdgeDescriptor Edge;
1423
1424 /**
1425 * @brief Constructor.
1426 * @param g The graph whose properties we access.
1427 */
1428 GraphEdgePropertiesSelector(G& g)
1429 : graph_(g)
1430 {}
1431 /**
1432 * @brief Default constructor.
1433 */
1434 GraphEdgePropertiesSelector()
1435 : graph_(0)
1436 {}
1437
1438 /**
1439 * @brief Get the properties associated to a vertex.
1440 * @param edge The edge whose Properties we want.
1441 */
1442 EdgeProperties& operator[](const Edge& edge) const
1443 {
1444 return graph_->getEdgeProperties(edge);
1445 }
1446 private:
1447 Graph* graph_;
1448 };
1449
1450
1451 /**
1452 * @brief Visit all neighbour vertices of a vertex in a graph.
1453 *
1454 * @param graph The graph whose vertices to visit.
1455 * @param vertex The vertex whose neighbours we want to
1456 * visit.
1457 * @param visitor The visitor evaluated for each EdgeIterator
1458 * (by its method operator()(const ConstEdgeIterator& edge)
1459 * @return The number of neighbours of the vertex.
1460 */
1461 template<class G, class V>
1462 int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex,
1463 V& visitor);
1464
1465 #ifndef DOXYGEN
1466
1467 template<class M>
1468 MatrixGraph<M>::MatrixGraph(M& matrix)
1469 : matrix_(matrix)
1470 {
1471 if(matrix_.N()!=matrix_.M())
1472 DUNE_THROW(ISTLError, "Matrix has to have as many columns as rows!");
1473
1474 start_ = new EdgeDescriptor[matrix_.N()+1];
1475
1476 typedef typename M::ConstIterator Iterator;
1477 start_[matrix_.begin().index()] = 0;
1478
1479 for(Iterator row=matrix_.begin(); row != matrix_.end(); ++row)
1480 start_[row.index()+1] = start_[row.index()] + row->size();
1481 }
1482
1483 template<class M>
1484 MatrixGraph<M>::~MatrixGraph()
1485 {
1486 delete[] start_;
1487 }
1488
1489 template<class M>
1490 inline std::size_t MatrixGraph<M>::noEdges() const
1491 {
1492 return start_[matrix_.N()];
1493 }
1494
1495 template<class M>
1496 inline std::size_t MatrixGraph<M>::noVertices() const
1497 {
1498 return matrix_.N();
1499 }
1500
1501 template<class M>
1502 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::maxVertex() const
1503 {
1504 return matrix_.N()-1;
1505 }
1506
1507 template<class M>
1508 typename MatrixGraph<M>::EdgeDescriptor
1509 MatrixGraph<M>::findEdge(const VertexDescriptor& source,
1510 const VertexDescriptor& target) const
1511 {
1512 typename M::ConstColIterator found =matrix_[source].find(target);
1513 if(found == matrix_[source].end())
1514 return std::numeric_limits<EdgeDescriptor>::max();
1515 std::size_t offset = found.offset();
1516 if(target>source)
1517 offset--;
1518
1519 assert(offset<noEdges());
1520
1521 return start_[source]+offset;
1522 }
1523
1524
1525 template<class M>
1526 inline M& MatrixGraph<M>::matrix()
1527 {
1528 return matrix_;
1529 }
1530
1531 template<class M>
1532 inline const M& MatrixGraph<M>::matrix() const
1533 {
1534 return matrix_;
1535 }
1536
1537 template<class M>
1538 template<class C>
1539 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block,
1540 const ColIterator& end, const EdgeDescriptor& edge)
1541 : source_(source), block_(block), blockEnd_(end), edge_(edge)
1542 {
1543 if(block_!=blockEnd_ && block_.index() == source_) {
1544 // This is the edge from the diagonal to the diagonal. Skip it.
1545 ++block_;
1546 }
1547 }
1548
1549 template<class M>
1550 template<class C>
1551 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const ColIterator& block)
1552 : block_(block)
1553 {}
1554
1555 template<class M>
1556 template<class C>
1557 template<class C1>
1558 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const EdgeIteratorT<C1>& other)
1559 : source_(other.source_), block_(other.block_), blockEnd_(other.blockEnd_), edge_(other.edge_)
1560 {}
1561
1562
1563 template<class M>
1564 template<class C>
1565 inline typename MatrixGraph<M>::template EdgeIteratorT<C>::WeightType&
1566 MatrixGraph<M>::EdgeIteratorT<C>::weight() const
1567 {
1568 return *block_;
1569 }
1570
1571 template<class M>
1572 template<class C>
1573 inline typename MatrixGraph<M>::template EdgeIteratorT<C>& MatrixGraph<M>::EdgeIteratorT<C>::operator++()
1574 {
1575 ++block_;
1576 ++edge_;
1577
1578 if(block_!=blockEnd_ && block_.index() == source_) {
1579 // This is the edge from the diagonal to the diagonal. Skip it.
1580 ++block_;
1581 }
1582
1583 return *this;
1584 }
1585
1586 template<class M>
1587 template<class C>
1588 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(const typename MatrixGraph<M>::template EdgeIteratorT<typename std::remove_const<C>::type>& other) const
1589 {
1590 return block_!=other.block_;
1591 }
1592
1593 template<class M>
1594 template<class C>
1595 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(const typename MatrixGraph<M>::template EdgeIteratorT<const typename std::remove_const<C>::type>& other) const
1596 {
1597 return block_!=other.block_;
1598 }
1599
1600 template<class M>
1601 template<class C>
1602 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator==(const typename MatrixGraph<M>::template EdgeIteratorT<typename std::remove_const<C>::type>& other) const
1603 {
1604 return block_==other.block_;
1605 }
1606
1607 template<class M>
1608 template<class C>
1609 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator==(const typename MatrixGraph<M>::template EdgeIteratorT<const typename std::remove_const<C>::type>& other) const
1610 {
1611 return block_==other.block_;
1612 }
1613
1614 template<class M>
1615 template<class C>
1616 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::target() const
1617 {
1618 return block_.index();
1619 }
1620
1621 template<class M>
1622 template<class C>
1623 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::source() const
1624 {
1625 return source_;
1626 }
1627
1628 template<class M>
1629 template<class C>
1630 inline const typename MatrixGraph<M>::EdgeDescriptor& MatrixGraph<M>::EdgeIteratorT<C>::operator*() const
1631 {
1632 return edge_;
1633 }
1634
1635 template<class M>
1636 template<class C>
1637 inline const typename MatrixGraph<M>::EdgeDescriptor* MatrixGraph<M>::EdgeIteratorT<C>::operator->() const
1638 {
1639 return &edge_;
1640 }
1641
1642 template<class M>
1643 template<class C>
1644 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(C* graph,
1645 const VertexDescriptor& current)
1646 : graph_(graph), current_(current)
1647 {}
1648
1649
1650 template<class M>
1651 template<class C>
1652 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(const VertexDescriptor& current)
1653 : current_(current)
1654 {}
1655
1656 template<class M>
1657 template<class C>
1658 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(const VertexIteratorT<MutableContainer>& other)
1659 : graph_(other.graph_), current_(other.current_)
1660 {}
1661
1662 template<class M>
1663 template<class C>
1664 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(const VertexIteratorT<MutableContainer>& other) const
1665 {
1666 return current_ != other.current_;
1667 }
1668
1669 template<class M>
1670 template<class C>
1671 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(const VertexIteratorT<ConstContainer>& other) const
1672 {
1673 return current_ != other.current_;
1674 }
1675
1676
1677 template<class M>
1678 template<class C>
1679 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(const VertexIteratorT<MutableContainer>& other) const
1680 {
1681 return current_ == other.current_;
1682 }
1683
1684 template<class M>
1685 template<class C>
1686 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(const VertexIteratorT<ConstContainer>& other) const
1687 {
1688 return current_ == other.current_;
1689 }
1690
1691 template<class M>
1692 template<class C>
1693 inline typename MatrixGraph<M>::template VertexIteratorT<C>& MatrixGraph<M>::VertexIteratorT<C>::operator++()
1694 {
1695 ++current_;
1696 return *this;
1697 }
1698
1699 template<class M>
1700 template<class C>
1701 inline typename MatrixGraph<M>::template VertexIteratorT<C>::WeightType&
1702 MatrixGraph<M>::VertexIteratorT<C>::weight() const
1703 {
1704 return graph_->matrix()[current_][current_];
1705 }
1706
1707 template<class M>
1708 template<class C>
1709 inline const typename MatrixGraph<M>::VertexDescriptor&
1710 MatrixGraph<M>::VertexIteratorT<C>::operator*() const
1711 {
1712 return current_;
1713 }
1714
1715 template<class M>
1716 template<class C>
1717 inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1718 MatrixGraph<M>::VertexIteratorT<C>::begin() const
1719 {
1720 return graph_->beginEdges(current_);
1721 }
1722
1723 template<class M>
1724 template<class C>
1725 inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1726 MatrixGraph<M>::VertexIteratorT<C>::end() const
1727 {
1728 return graph_->endEdges(current_);
1729 }
1730
1731 template<class M>
1732 inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1733 MatrixGraph<M>::begin()
1734 {
1735 return VertexIterator(this,0);
1736 }
1737
1738 template<class M>
1739 inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1740 MatrixGraph<M>::end()
1741 {
1742 return VertexIterator(matrix_.N());
1743 }
1744
1745
1746 template<class M>
1747 inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1748 MatrixGraph<M>::begin() const
1749 {
1750 return ConstVertexIterator(this, 0);
1751 }
1752
1753 template<class M>
1754 inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1755 MatrixGraph<M>::end() const
1756 {
1757 return ConstVertexIterator(matrix_.N());
1758 }
1759
1760 template<class M>
1761 inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1762 MatrixGraph<M>::beginEdges(const VertexDescriptor& source)
1763 {
1764 return EdgeIterator(source, matrix_.operator[](source).begin(),
1765 matrix_.operator[](source).end(), start_[source]);
1766 }
1767
1768 template<class M>
1769 inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1770 MatrixGraph<M>::endEdges(const VertexDescriptor& source)
1771 {
1772 return EdgeIterator(matrix_.operator[](source).end());
1773 }
1774
1775
1776 template<class M>
1777 inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
1778 MatrixGraph<M>::beginEdges(const VertexDescriptor& source) const
1779 {
1780 return ConstEdgeIterator(source, matrix_.operator[](source).begin(),
1781 matrix_.operator[](source).end(), start_[source]);
1782 }
1783
1784 template<class M>
1785 inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
1786 MatrixGraph<M>::endEdges(const VertexDescriptor& source) const
1787 {
1788 return ConstEdgeIterator(matrix_.operator[](source).end());
1789 }
1790
1791
1792 template<class G, class T>
1793 SubGraph<G,T>::EdgeIterator::EdgeIterator(const VertexDescriptor& source,
1794 const EdgeDescriptor& edge)
1795 : source_(source), edge_(edge)
1796 {}
1797
1798
1799 template<class G, class T>
1800 SubGraph<G,T>::EdgeIterator::EdgeIterator(const EdgeDescriptor& edge)
1801 : edge_(edge)
1802 {}
1803
1804 template<class G, class T>
1805 typename SubGraph<G,T>::EdgeIndexMap SubGraph<G,T>::getEdgeIndexMap()
1806 {
1807 return EdgeIndexMap(edges_);
1808 }
1809
1810 template<class G, class T>
1811 inline bool SubGraph<G,T>::EdgeIterator::equals(const EdgeIterator & other) const
1812 {
1813 return other.edge_==edge_;
1814 }
1815
1816 template<class G, class T>
1817 inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::increment()
1818 {
1819 ++edge_;
1820 return *this;
1821 }
1822
1823 template<class G, class T>
1824 inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::decrement()
1825 {
1826 --edge_;
1827 return *this;
1828 }
1829
1830 template<class G, class T>
1831 inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::advance(std::ptrdiff_t n)
1832 {
1833 edge_+=n;
1834 return *this;
1835 }
1836 template<class G, class T>
1837 inline const typename G::VertexDescriptor& SubGraph<G,T>::EdgeIterator::source() const
1838 {
1839 return source_;
1840 }
1841
1842 template<class G, class T>
1843 inline const typename G::VertexDescriptor& SubGraph<G,T>::EdgeIterator::target() const
1844 {
1845 return *edge_;
1846 }
1847
1848
1849 template<class G, class T>
1850 inline const typename SubGraph<G,T>::EdgeDescriptor& SubGraph<G,T>::EdgeIterator::dereference() const
1851 {
1852 return edge_;
1853 }
1854
1855 template<class G, class T>
1856 inline std::ptrdiff_t SubGraph<G,T>::EdgeIterator::distanceTo(const EdgeIterator & other) const
1857 {
1858 return other.edge_-edge_;
1859 }
1860
1861 template<class G, class T>
1862 SubGraph<G,T>::VertexIterator::VertexIterator(const SubGraph<G,T>* graph,
1863 const VertexDescriptor& current,
1864 const VertexDescriptor& end)
1865 : graph_(graph), current_(current), end_(end)
1866 {
1867 // Skip excluded vertices
1868 typedef typename T::const_iterator Iterator;
1869
1870 for(Iterator vertex = graph_->excluded_.begin();
1871 current_ != end_ && *vertex;
1872 ++vertex)
1873 ++current_;
1874 assert(current_ == end_ || !graph_->excluded_[current_]);
1875 }
1876
1877 template<class G, class T>
1878 SubGraph<G,T>::VertexIterator::VertexIterator(const VertexDescriptor& current)
1879 : current_(current)
1880 {}
1881
1882 template<class G, class T>
1883 inline typename SubGraph<G,T>::VertexIterator& SubGraph<G,T>::VertexIterator::increment()
1884 {
1885 ++current_;
1886 //Skip excluded vertices
1887 while(current_ != end_ && graph_->excluded_[current_])
1888 ++current_;
1889
1890 assert(current_ == end_ || !graph_->excluded_[current_]);
1891 return *this;
1892 }
1893
1894 template<class G, class T>
1895 inline bool SubGraph<G,T>::VertexIterator::equals(const VertexIterator & other) const
1896 {
1897 return current_==other.current_;
1898 }
1899
1900 template<class G, class T>
1901 inline const typename G::VertexDescriptor& SubGraph<G,T>::VertexIterator::dereference() const
1902 {
1903 return current_;
1904 }
1905
1906 template<class G, class T>
1907 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::VertexIterator::begin() const
1908 {
1909 return graph_->beginEdges(current_);
1910 }
1911
1912 template<class G, class T>
1913 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::VertexIterator::end() const
1914 {
1915 return graph_->endEdges(current_);
1916 }
1917
1918 template<class G, class T>
1919 inline typename SubGraph<G,T>::VertexIterator SubGraph<G,T>::begin() const
1920 {
1921 return VertexIterator(this, 0, endVertex_);
1922 }
1923
1924
1925 template<class G, class T>
1926 inline typename SubGraph<G,T>::VertexIterator SubGraph<G,T>::end() const
1927 {
1928 return VertexIterator(endVertex_);
1929 }
1930
1931
1932 template<class G, class T>
1933 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::beginEdges(const VertexDescriptor& source) const
1934 {
1935 return EdgeIterator(source, edges_+start_[source]);
1936 }
1937
1938 template<class G, class T>
1939 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::endEdges(const VertexDescriptor& source) const
1940 {
1941 return EdgeIterator(edges_+end_[source]);
1942 }
1943
1944 template<class G, class T>
1945 std::size_t SubGraph<G,T>::noVertices() const
1946 {
1947 return noVertices_;
1948 }
1949
1950 template<class G, class T>
1951 inline typename SubGraph<G,T>::VertexDescriptor SubGraph<G,T>::maxVertex() const
1952 {
1953 return maxVertex_;
1954 }
1955
1956 template<class G, class T>
1957 inline std::size_t SubGraph<G,T>::noEdges() const
1958 {
1959 return noEdges_;
1960 }
1961
1962 template<class G, class T>
1963 inline typename SubGraph<G,T>::EdgeDescriptor SubGraph<G,T>::findEdge(const VertexDescriptor& source,
1964 const VertexDescriptor& target) const
1965 {
1966 const EdgeDescriptor edge = std::lower_bound(edges_+start_[source], edges_+end_[source], target);
1967 if(edge==edges_+end_[source] || *edge!=target)
1968 return std::numeric_limits<EdgeDescriptor>::max();
1969
1970 return edge;
1971 }
1972
1973 template<class G, class T>
1974 SubGraph<G,T>::~SubGraph()
1975 {
1976 delete[] edges_;
1977 delete[] end_;
1978 delete[] start_;
1979 }
1980
1981 template<class G, class T>
1982 SubGraph<G,T>::SubGraph(const G& graph, const T& excluded)
1983 : excluded_(excluded), noVertices_(0), endVertex_(0), maxVertex_(graph.maxVertex())
1984 {
1985 start_ = new std::ptrdiff_t[graph.noVertices()];
1986 end_ = new std::ptrdiff_t[graph.noVertices()];
1987 edges_ = new VertexDescriptor[graph.noEdges()];
1988
1989 VertexDescriptor* edge=edges_;
1990
1991 // Cater for the case that there are no vertices.
1992 // Otherwise endVertex_ will get 1 below.
1993 if ( graph.noVertices() == 0)
1994 return;
1995
1996 typedef typename Graph::ConstVertexIterator Iterator;
1997 Iterator endVertex=graph.end();
1998
1999 for(Iterator vertex = graph.begin(); vertex != endVertex; ++vertex)
2000 if(excluded_[*vertex])
2001 start_[*vertex]=end_[*vertex]=-1;
2002 else{
2003 ++noVertices_;
2004 endVertex_ = std::max(*vertex, endVertex_);
2005
2006 start_[*vertex] = edge-edges_;
2007
2008 auto endEdge = vertex.end();
2009
2010 for(auto iter=vertex.begin(); iter!= endEdge; ++iter)
2011 if(!excluded[iter.target()]) {
2012 *edge = iter.target();
2013 ++edge;
2014 }
2015
2016 end_[*vertex] = edge - edges_;
2017
2018 // Sort the edges
2019 std::sort(edges_+start_[*vertex], edge);
2020 }
2021 noEdges_ = edge-edges_;
2022 ++endVertex_;
2023 }
2024
2025 template<class G, class V, class VM>
2026 inline std::size_t VertexPropertiesGraph<G,V,VM>::noEdges() const
2027 {
2028 return graph_.noEdges();
2029 }
2030
2031 template<class G, class V, class VM>
2032 inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2033 VertexPropertiesGraph<G,V,VM>::beginEdges(const VertexDescriptor& source)
2034 {
2035 return graph_.beginEdges(source);
2036 }
2037
2038 template<class G, class V, class VM>
2039 inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2040 VertexPropertiesGraph<G,V,VM>::endEdges(const VertexDescriptor& source)
2041 {
2042 return graph_.endEdges(source);
2043 }
2044
2045 template<class G, class V, class VM>
2046 typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2047 inline VertexPropertiesGraph<G,V,VM>::beginEdges(const VertexDescriptor& source) const
2048 {
2049 return graph_.beginEdges(source);
2050 }
2051
2052 template<class G, class V, class VM>
2053 typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2054 VertexPropertiesGraph<G,V,VM>::endEdges(const VertexDescriptor& source) const
2055 {
2056 return graph_.endEdges(source);
2057 }
2058
2059 template<class G, class V, class VM>
2060 template<class C>
2061 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2062 ::VertexIteratorT(const Father& iter,
2063 C* graph)
2064 : Father(iter), graph_(graph)
2065 {}
2066
2067 template<class G, class V, class VM>
2068 template<class C>
2069 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2070 ::VertexIteratorT(const Father& iter)
2071 : Father(iter)
2072 {}
2073
2074 template<class G, class V, class VM>
2075 template<class C>
2076 template<class C1>
2077 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2078 ::VertexIteratorT(const VertexIteratorT<C1>& other)
2079 : Father(other), graph_(other.graph_)
2080 {}
2081
2082 template<class G, class V, class VM>
2083 template<class C>
2084 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
2085 V&, const V&>::type
2086 inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::properties() const
2087 {
2088 return graph_->getVertexProperties(Father::operator*());
2089 }
2090
2091 template<class G, class V, class VM>
2092 template<class C>
2093 typename std::conditional<std::is_same<typename std::remove_const<C>::type,
2094 C>::value,
2095 typename G::EdgeIterator,
2096 typename G::ConstEdgeIterator>::type
2097 inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::begin() const
2098 {
2099 return graph_->beginEdges(Father::operator*());
2100 }
2101
2102 template<class G, class V, class VM>
2103 template<class C>
2104 typename std::conditional<std::is_same<typename std::remove_const<C>::type,
2105 C>::value,
2106 typename G::EdgeIterator,
2107 typename G::ConstEdgeIterator>::type
2108 inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::end() const
2109 {
2110 return graph_->endEdges(Father::operator*());
2111 }
2112
2113 template<class G, class V, class VM>
2114 inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::begin()
2115 {
2116 return VertexIterator(graph_.begin(), this);
2117 }
2118
2119 template<class G, class V, class VM>
2120 inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::end()
2121 {
2122 return VertexIterator(graph_.end());
2123 }
2124
2125
2126 template<class G, class V, class VM>
2127 inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::begin() const
2128 {
2129 return ConstVertexIterator(graph_.begin(), this);
2130 }
2131
2132 template<class G, class V, class VM>
2133 inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::end() const
2134 {
2135 return ConstVertexIterator(graph_.end());
2136 }
2137
2138 template<class G, class V, class VM>
2139 inline V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(const VertexDescriptor& vertex)
2140 {
2141 return vertexProperties_[vmap_[vertex]];
2142 }
2143
2144 template<class G, class V, class VM>
2145 inline const V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(const VertexDescriptor& vertex) const
2146 {
2147 return vertexProperties_[vmap_[vertex]];
2148 }
2149
2150 template<class G, class V, class VM>
2151 inline const G& VertexPropertiesGraph<G,V,VM>::graph() const
2152 {
2153 return graph_;
2154 }
2155
2156 template<class G, class V, class VM>
2157 inline std::size_t VertexPropertiesGraph<G,V,VM>::noVertices() const
2158 {
2159 return graph_.noVertices();
2160 }
2161
2162
2163 template<class G, class V, class VM>
2164 inline typename VertexPropertiesGraph<G,V,VM>::VertexDescriptor VertexPropertiesGraph<G,V,VM>::maxVertex() const
2165 {
2166 return graph_.maxVertex();
2167 }
2168
2169 template<class G, class V, class VM>
2170 VertexPropertiesGraph<G,V,VM>::VertexPropertiesGraph(Graph& graph, const VM vmap)
2171 : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V())
2172 {}
2173
2174 template<class G, class V, class E, class VM, class EM>
2175 template<class C>
2176 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const Father& iter,
2177 C* graph)
2178 : Father(iter), graph_(graph)
2179 {}
2180
2181 template<class G, class V, class E, class VM, class EM>
2182 template<class C>
2183 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const Father& iter)
2184 : Father(iter)
2185 {}
2186
2187 template<class G, class V, class E, class VM, class EM>
2188 template<class C>
2189 template<class C1>
2190 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const EdgeIteratorT<C1>& other)
2191 : Father(other), graph_(other.graph_)
2192 {}
2193
2194
2195 template<class G, class V, class E, class VM, class EM>
2196 inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noEdges() const
2197 {
2198 return graph_.noEdges();
2199 }
2200
2201 template<class G, class V, class E, class VM, class EM>
2202 template<class C>
2203 inline typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,E&,const E&>::type
2204 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::properties() const
2205 {
2206 return graph_->getEdgeProperties(Father::operator*());
2207 }
2208
2209 template<class G, class V, class E, class VM, class EM>
2210 inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2211 PropertiesGraph<G,V,E,VM,EM>::beginEdges(const VertexDescriptor& source)
2212 {
2213 return EdgeIterator(graph_.beginEdges(source), this);
2214 }
2215
2216 template<class G, class V, class E, class VM, class EM>
2217 inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2218 PropertiesGraph<G,V,E,VM,EM>::endEdges(const VertexDescriptor& source)
2219 {
2220 return EdgeIterator(graph_.endEdges(source));
2221 }
2222
2223 template<class G, class V, class E, class VM, class EM>
2224 typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2225 inline PropertiesGraph<G,V,E,VM,EM>::beginEdges(const VertexDescriptor& source) const
2226 {
2227 return ConstEdgeIterator(graph_.beginEdges(source), this);
2228 }
2229
2230 template<class G, class V, class E, class VM, class EM>
2231 typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2232 PropertiesGraph<G,V,E,VM,EM>::endEdges(const VertexDescriptor& source) const
2233 {
2234 return ConstEdgeIterator(graph_.endEdges(source));
2235 }
2236
2237 template<class G, class V, class E, class VM, class EM>
2238 template<class C>
2239 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2240 ::VertexIteratorT(const Father& iter,
2241 C* graph)
2242 : Father(iter), graph_(graph)
2243 {}
2244
2245 template<class G, class V, class E, class VM, class EM>
2246 template<class C>
2247 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2248 ::VertexIteratorT(const Father& iter)
2249 : Father(iter)
2250 {}
2251
2252 template<class G, class V, class E, class VM, class EM>
2253 template<class C>
2254 template<class C1>
2255 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2256 ::VertexIteratorT(const VertexIteratorT<C1>& other)
2257 : Father(other), graph_(other.graph_)
2258 {}
2259
2260 template<class G, class V, class E, class VM, class EM>
2261 template<class C>
2262 inline typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
2263 V&, const V&>::type
2264 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::properties() const
2265 {
2266 return graph_->getVertexProperties(Father::operator*());
2267 }
2268
2269 template<class G, class V, class E, class VM, class EM>
2270 template<class C>
2271 inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2272 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::begin() const
2273 {
2274 return graph_->beginEdges(Father::operator*());
2275 }
2276
2277 template<class G, class V, class E, class VM, class EM>
2278 template<class C>
2279 inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2280 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::end() const
2281 {
2282 return graph_->endEdges(Father::operator*());
2283 }
2284
2285 template<class G, class V, class E, class VM, class EM>
2286 inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::begin()
2287 {
2288 return VertexIterator(graph_.begin(), this);
2289 }
2290
2291 template<class G, class V, class E, class VM, class EM>
2292 inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::end()
2293 {
2294 return VertexIterator(graph_.end());
2295 }
2296
2297
2298 template<class G, class V, class E, class VM, class EM>
2299 inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::begin() const
2300 {
2301 return ConstVertexIterator(graph_.begin(), this);
2302 }
2303
2304 template<class G, class V, class E, class VM, class EM>
2305 inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::end() const
2306 {
2307 return ConstVertexIterator(graph_.end());
2308 }
2309
2310 template<class G, class V, class E, class VM, class EM>
2311 inline V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(const VertexDescriptor& vertex)
2312 {
2313 return vertexProperties_[vmap_[vertex]];
2314 }
2315
2316 template<class G, class V, class E, class VM, class EM>
2317 inline const V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(const VertexDescriptor& vertex) const
2318 {
2319 return vertexProperties_[vmap_[vertex]];
2320 }
2321
2322 template<class G, class V, class E, class VM, class EM>
2323 inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const EdgeDescriptor& edge)
2324 {
2325 return edgeProperties_[emap_[edge]];
2326 }
2327
2328 template<class G, class V, class E, class VM, class EM>
2329 inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const EdgeDescriptor& edge) const
2330 {
2331 return edgeProperties_[emap_[edge]];
2332 }
2333
2334 template<class G, class V, class E, class VM, class EM>
2335 inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const VertexDescriptor& source,
2336 const VertexDescriptor& target)
2337 {
2338 return getEdgeProperties(graph_.findEdge(source,target));
2339 }
2340
2341 template<class G, class V, class E, class VM, class EM>
2342 inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const VertexDescriptor& source,
2343 const VertexDescriptor& target) const
2344 {
2345 return getEdgeProperties(graph_.findEdge(source,target));
2346 }
2347
2348 template<class G, class V, class E, class VM, class EM>
2349 inline const G& PropertiesGraph<G,V,E,VM,EM>::graph() const
2350 {
2351 return graph_;
2352 }
2353
2354 template<class G, class V, class E, class VM, class EM>
2355 inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noVertices() const
2356 {
2357 return graph_.noVertices();
2358 }
2359
2360
2361 template<class G, class V, class E, class VM, class EM>
2362 inline typename PropertiesGraph<G,V,E,VM,EM>::VertexDescriptor PropertiesGraph<G,V,E,VM,EM>::maxVertex() const
2363 {
2364 return graph_.maxVertex();
2365 }
2366
2367 template<class G, class V, class E, class VM, class EM>
2368 PropertiesGraph<G,V,E,VM,EM>::PropertiesGraph(Graph& graph, const VM& vmap, const EM& emap)
2369 : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V()),
2370 emap_(emap), edgeProperties_(graph_.noEdges(), E())
2371 {}
2372
2373 template<class G, class V>
2374 inline int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex,
2375 V& visitor)
2376 {
2377 typedef typename G::ConstEdgeIterator iterator;
2378 const iterator end = graph.endEdges(vertex);
2379 int noNeighbours=0;
2380 for(iterator edge = graph.beginEdges(vertex); edge != end; ++edge, ++noNeighbours)
2381 visitor(edge);
2382 return noNeighbours;
2383 }
2384
2385 #endif // DOXYGEN
2386
2387 /** @} */
2388 }
2389 }
2390 #endif