Dune Core Modules (2.6.0)

graph.hh
Go to the documentation of this file.
1// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2// vi: set et ts=4 sw=2 sts=2:
3#ifndef DUNE_AMG_GRAPH_HH
4#define DUNE_AMG_GRAPH_HH
5
6#include <cstddef>
7#include <algorithm>
8#include <vector>
9#include <cassert>
10#include <limits>
13#include <dune/istl/istlexception.hh>
14#include <dune/common/propertymap.hh>
15
16namespace Dune
17{
18 namespace Amg
19 {
47 template<class M>
49 {
50 public:
54 typedef M Matrix;
55
59 typedef typename std::remove_const<M>::type MutableMatrix;
60
64 typedef typename M::block_type Weight;
65
71 typedef typename M::size_type VertexDescriptor;
72
78 typedef std::ptrdiff_t EdgeDescriptor;
79
80 enum {
81 /*
82 * @brief Whether Matrix is mutable.
83 */
84 mutableMatrix = std::is_same<M, typename std::remove_const<M>::type>::value
85 };
86
87
91 template<class C>
93 {
94
95 public:
99 typedef typename std::remove_const<C>::type MutableContainer;
103 typedef const typename std::remove_const<C>::type ConstContainer;
104
105 friend class EdgeIteratorT<MutableContainer>;
106 friend class EdgeIteratorT<ConstContainer>;
107
108 enum {
110 isMutable = std::is_same<C, MutableContainer>::value
111 };
112
116 typedef typename std::conditional<isMutable && C::mutableMatrix,typename Matrix::row_type::Iterator,
117 typename Matrix::row_type::ConstIterator>::type
119
123 typedef typename std::conditional<isMutable && C::mutableMatrix,typename M::block_type,
124 const typename M::block_type>::type
126
135 const ColIterator& end, const EdgeDescriptor& edge);
136
144
149 template<class C1>
151
152 typedef typename std::conditional<std::is_same<C, typename std::remove_const<C>::type>::value && C::mutableMatrix,
153 typename M::block_type, const typename M::block_type>::type
154 WeightType;
155
159 WeightType& weight() const;
160
163
165 bool operator!=(const EdgeIteratorT<typename std::remove_const<C>::type>& other) const;
166
168 bool operator!=(const EdgeIteratorT<const typename std::remove_const<C>::type>& other) const;
169
171 bool operator==(const EdgeIteratorT<typename std::remove_const<C>::type>& other) const;
172
174 bool operator==(const EdgeIteratorT<const typename std::remove_const<C>::type>& other) const;
175
178
181
183 const EdgeDescriptor& operator*() const;
184
187
188 private:
190 VertexDescriptor source_;
192 ColIterator block_;
193 /***
194 * @brief The column iterator positioned at the end of the row
195 * of vertex source_
196 */
197 ColIterator blockEnd_;
199 EdgeDescriptor edge_;
200 };
201
205 template<class C>
207 {
208 public:
212 typedef typename std::remove_const<C>::type MutableContainer;
216 typedef const typename std::remove_const<C>::type ConstContainer;
217
218 friend class VertexIteratorT<MutableContainer>;
219 friend class VertexIteratorT<ConstContainer>;
220
221 enum {
223 isMutable = std::is_same<C, MutableContainer>::value
224 };
225
231 explicit VertexIteratorT(C* graph, const VertexDescriptor& current);
232
240 explicit VertexIteratorT(const VertexDescriptor& current);
241
243
249
252
255
258
261
262 typedef typename std::conditional<std::is_same<C, typename std::remove_const<C>::type>::value && C::mutableMatrix,
263 typename M::block_type, const typename M::block_type>::type
264 WeightType;
266 WeightType& weight() const;
267
273
280
287
288 private:
289 C* graph_;
290 VertexDescriptor current_;
291 };
292
297
302
307
312
318
323
329
335
341
347
355
363
364
372
380
386
391 const Matrix& matrix() const;
392
396 std::size_t noVertices() const;
397
405
409 std::size_t noEdges() const;
410
418 const VertexDescriptor& target) const;
419
420 private:
422 Matrix& matrix_;
424 EdgeDescriptor* start_;
426 MatrixGraph(const MatrixGraph&);
427
428 };
429
439 template<class G, class T>
441 {
442 public:
446 typedef G Graph;
447
452 typedef T Excluded;
453
457 typedef typename Graph::VertexDescriptor VertexDescriptor;
458
459 typedef VertexDescriptor* EdgeDescriptor;
460
468 {
469 public:
471
472 EdgeIndexMap(const EdgeDescriptor& firstEdge)
473 : firstEdge_(firstEdge)
474 {}
475
478 : firstEdge_(emap.firstEdge_)
479 {}
480
481 std::size_t operator[](const EdgeDescriptor& edge) const
482 {
483 return edge-firstEdge_;
484 }
485 private:
487 EdgeDescriptor firstEdge_;
489 EdgeIndexMap()
490 {}
491 };
492
498
502 class EdgeIterator : public RandomAccessIteratorFacade<EdgeIterator,const EdgeDescriptor>
503 {
504 public:
510 explicit EdgeIterator(const VertexDescriptor& source, const EdgeDescriptor& edge);
511
519 explicit EdgeIterator(const EdgeDescriptor& edge);
520
522 bool equals(const EdgeIterator& other) const;
523
526
529
530 EdgeIterator& advance(std::ptrdiff_t n);
531
533 const EdgeDescriptor& dereference() const;
534
536 const VertexDescriptor& target() const;
537
539 const VertexDescriptor& source() const;
540
541 std::ptrdiff_t distanceTo(const EdgeIterator& other) const;
542
543 private:
545 VertexDescriptor source_;
550 EdgeDescriptor edge_;
551 };
552
557 : public ForwardIteratorFacade<VertexIterator,const VertexDescriptor>
558 {
559 public:
566 explicit VertexIterator(const SubGraph<G,T>* graph, const VertexDescriptor& current,
567 const VertexDescriptor& end);
568
569
576 explicit VertexIterator(const VertexDescriptor& current);
577
580
582 bool equals(const VertexIterator& other) const;
583
589
596
603
604 private:
606 const SubGraph<Graph,T>* graph_;
608 VertexDescriptor current_;
610 VertexDescriptor end_;
611 };
612
617
622
628
634
642
650
654 std::size_t noVertices() const;
655
663
667 std::size_t noEdges() const;
674 EdgeDescriptor findEdge(const VertexDescriptor& source,
675 const VertexDescriptor& target) const;
683 SubGraph(const Graph& graph, const T& excluded);
684
689
690 private:
692 const T& excluded_;
694 std::size_t noVertices_;
696 VertexDescriptor endVertex_;
698 int noEdges_;
703 VertexDescriptor maxVertex_;
705 VertexDescriptor* edges_;
707 std::ptrdiff_t* start_;
709 std::ptrdiff_t* end_;
711 SubGraph(const SubGraph&)
712 {}
713 };
714
715
719 template<class G, class VP, class VM=IdentityMap>
721 {
722 public:
726 typedef G Graph;
727
731 typedef typename Graph::VertexDescriptor VertexDescriptor;
732
736 typedef typename Graph::EdgeDescriptor EdgeDescriptor;
737
742
754 typedef VM VertexMap;
755
759 typedef typename Graph::EdgeIterator EdgeIterator;
760
764 typedef typename Graph::ConstEdgeIterator ConstEdgeIterator;
765
772
779
786
793
794
795 template<class C>
796 class VertexIteratorT
797 : public std::conditional<std::is_same<typename std::remove_const<C>::type,
798 C>::value,
799 typename Graph::VertexIterator,
800 typename Graph::ConstVertexIterator>::type
801 {
802 friend class VertexIteratorT<const typename std::remove_const<C>::type>;
803 friend class VertexIteratorT<typename std::remove_const<C>::type>;
804 public:
808 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
809 C>::value,
810 typename Graph::VertexIterator,
811 typename Graph::ConstVertexIterator>::type
812 Father;
813
817 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
818 C>::value,
819 typename Graph::EdgeIterator,
820 typename Graph::ConstEdgeIterator>::type
822
828 explicit VertexIteratorT(const Father& iter,
829 C* graph);
830
831
839 explicit VertexIteratorT(const Father& iter);
840
845 template<class C1>
846 VertexIteratorT(const VertexIteratorT<C1>& other);
847
851 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
852 VertexProperties&,
853 const VertexProperties&>::type
854 properties() const;
855
861 EdgeIterator begin() const;
862
868 EdgeIterator end() const;
869
870 private:
874 C* graph_;
875 };
876
880 typedef VertexIteratorT<VertexPropertiesGraph<Graph,
881 VertexProperties,VM> > VertexIterator;
882
886 typedef VertexIteratorT<const VertexPropertiesGraph<Graph,
887 VertexProperties,VM> > ConstVertexIterator;
888
894
900
906
912
918 VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
919
925 const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
926
931 const Graph& graph() const;
932
936 std::size_t noVertices() const;
937
941 std::size_t noEdges() const;
942
950
956 VertexPropertiesGraph(Graph& graph, const VertexMap vmap=VertexMap());
957
958 private:
959 VertexPropertiesGraph(const VertexPropertiesGraph&)
960 {}
961
963 Graph& graph_;
965 VertexMap vmap_;
967 std::vector<VertexProperties> vertexProperties_;
968
969 };
970
974 template<class G, class VP, class EP, class VM=IdentityMap, class EM=IdentityMap>
976 {
977 public:
981 typedef G Graph;
982
986 typedef typename Graph::VertexDescriptor VertexDescriptor;
987
991 typedef typename Graph::EdgeDescriptor EdgeDescriptor;
992
997
1009 typedef VM VertexMap;
1010
1014 typedef EP EdgeProperties;
1015
1016
1028 typedef EM EdgeMap;
1029
1030 template<class C>
1031 class EdgeIteratorT
1032 : public std::conditional<std::is_same<typename std::remove_const<C>::type,
1033 C>::value,
1034 typename Graph::EdgeIterator,
1035 typename Graph::ConstEdgeIterator>::type
1036 {
1037
1038 friend class EdgeIteratorT<const typename std::remove_const<C>::type>;
1039 friend class EdgeIteratorT<typename std::remove_const<C>::type>;
1040 public:
1044 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
1045 C>::value,
1046 typename Graph::EdgeIterator,
1047 typename Graph::ConstEdgeIterator>::type
1048 Father;
1049
1055 explicit EdgeIteratorT(const Father& iter,
1056 C* graph);
1057
1065 explicit EdgeIteratorT(const Father& iter);
1066
1071 template<class C1>
1072 EdgeIteratorT(const EdgeIteratorT<C1>& other);
1073
1077 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
1078 EdgeProperties&,
1079 const EdgeProperties&>::type
1080 properties() const;
1081
1082 private:
1086 C* graph_;
1087 };
1088
1092 typedef EdgeIteratorT<PropertiesGraph<Graph,
1093 VertexProperties,
1094 EdgeProperties,VM,EM> > EdgeIterator;
1095
1099 typedef EdgeIteratorT<const PropertiesGraph<Graph,
1100 VertexProperties,
1101 EdgeProperties,VM,EM> > ConstEdgeIterator;
1102
1108 EdgeIterator beginEdges(const VertexDescriptor& source);
1109
1115 EdgeIterator endEdges(const VertexDescriptor& source);
1116
1122 ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
1123
1129 ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
1130
1131
1132 template<class C>
1133 class VertexIteratorT
1134 : public std::conditional<std::is_same<typename std::remove_const<C>::type,
1135 C>::value,
1136 typename Graph::VertexIterator,
1137 typename Graph::ConstVertexIterator>::type
1138 {
1139 friend class VertexIteratorT<const typename std::remove_const<C>::type>;
1140 friend class VertexIteratorT<typename std::remove_const<C>::type>;
1141 public:
1145 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
1146 C>::value,
1147 typename Graph::VertexIterator,
1148 typename Graph::ConstVertexIterator>::type
1149 Father;
1150
1156 explicit VertexIteratorT(const Father& iter,
1157 C* graph);
1158
1159
1167 explicit VertexIteratorT(const Father& iter);
1168
1173 template<class C1>
1174 VertexIteratorT(const VertexIteratorT<C1>& other);
1175
1179 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
1180 VertexProperties&,
1181 const VertexProperties&>::type
1182 properties() const;
1183
1189 EdgeIteratorT<C> begin() const;
1190
1196 EdgeIteratorT<C> end() const;
1197
1198 private:
1202 C* graph_;
1203 };
1204
1208 typedef VertexIteratorT<PropertiesGraph<Graph,
1209 VertexProperties,
1210 EdgeProperties,VM,EM> > VertexIterator;
1211
1215 typedef VertexIteratorT<const PropertiesGraph<Graph,
1216 VertexProperties,
1217 EdgeProperties,VM,EM> > ConstVertexIterator;
1218
1224
1230
1236
1242
1248 VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
1249
1255 const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
1256
1263 EdgeDescriptor findEdge(const VertexDescriptor& source,
1264 const VertexDescriptor& target)
1265 {
1266 return graph_.findEdge(source,target);
1267 }
1268
1275
1276
1283
1291 const VertexDescriptor& target);
1292
1300 const VertexDescriptor& target) const;
1301
1306 const Graph& graph() const;
1307
1311 std::size_t noVertices() const;
1312
1316 std::size_t noEdges() const;
1317
1325
1333 const EdgeMap& emap=EdgeMap());
1334
1335 private:
1337 {}
1338
1340 Graph& graph_;
1343 VertexMap vmap_;
1344 std::vector<VertexProperties> vertexProperties_;
1346 EdgeMap emap_;
1348 std::vector<EdgeProperties> edgeProperties_;
1349
1350 };
1351
1352
1357 template<typename G>
1359 {
1360 public:
1364 typedef G Graph;
1368 typedef typename G::VertexProperties VertexProperties;
1372 typedef typename G::VertexDescriptor Vertex;
1373
1379 : graph_(g)
1380 {}
1385 : graph_(0)
1386 {}
1387
1388
1394 {
1395 return graph_->getVertexProperties(vertex);
1396 }
1397 private:
1398 Graph* graph_;
1399 };
1400
1405 template<typename G>
1407 {
1408 public:
1412 typedef G Graph;
1416 typedef typename G::EdgeProperties EdgeProperties;
1420 typedef typename G::EdgeDescriptor Edge;
1421
1427 : graph_(g)
1428 {}
1433 : graph_(0)
1434 {}
1435
1440 EdgeProperties& operator[](const Edge& edge) const
1441 {
1442 return graph_->getEdgeProperties(edge);
1443 }
1444 private:
1445 Graph* graph_;
1446 };
1447
1448
1459 template<class G, class V>
1460 int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex,
1461 V& visitor);
1462
1463#ifndef DOXYGEN
1464
1465 template<class M>
1467 : matrix_(matrix)
1468 {
1469 if(matrix_.N()!=matrix_.M())
1470 DUNE_THROW(ISTLError, "Matrix has to have as many columns as rows!");
1471
1472 start_ = new EdgeDescriptor[matrix_.N()+1];
1473
1474 typedef typename M::ConstIterator Iterator;
1475 start_[matrix_.begin().index()] = 0;
1476
1477 for(Iterator row=matrix_.begin(); row != matrix_.end(); ++row)
1478 start_[row.index()+1] = start_[row.index()] + row->size();
1479 }
1480
1481 template<class M>
1482 MatrixGraph<M>::~MatrixGraph()
1483 {
1484 delete[] start_;
1485 }
1486
1487 template<class M>
1488 inline std::size_t MatrixGraph<M>::noEdges() const
1489 {
1490 return start_[matrix_.N()];
1491 }
1492
1493 template<class M>
1494 inline std::size_t MatrixGraph<M>::noVertices() const
1495 {
1496 return matrix_.N();
1497 }
1498
1499 template<class M>
1500 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::maxVertex() const
1501 {
1502 return matrix_.N()-1;
1503 }
1504
1505 template<class M>
1506 typename MatrixGraph<M>::EdgeDescriptor
1507 MatrixGraph<M>::findEdge(const VertexDescriptor& source,
1508 const VertexDescriptor& target) const
1509 {
1510 typename M::ConstColIterator found =matrix_[source].find(target);
1511 if(found == matrix_[source].end())
1512 return std::numeric_limits<EdgeDescriptor>::max();
1513 std::size_t offset = found.offset();
1514 if(target>source)
1515 offset--;
1516
1517 assert(offset<noEdges());
1518
1519 return start_[source]+offset;
1520 }
1521
1522
1523 template<class M>
1524 inline M& MatrixGraph<M>::matrix()
1525 {
1526 return matrix_;
1527 }
1528
1529 template<class M>
1530 inline const M& MatrixGraph<M>::matrix() const
1531 {
1532 return matrix_;
1533 }
1534
1535 template<class M>
1536 template<class C>
1537 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block,
1538 const ColIterator& end, const EdgeDescriptor& edge)
1539 : source_(source), block_(block), blockEnd_(end), edge_(edge)
1540 {
1541 if(block_!=blockEnd_ && block_.index() == source_) {
1542 // This is the edge from the diagonal to the diagonal. Skip it.
1543 ++block_;
1544 }
1545 }
1546
1547 template<class M>
1548 template<class C>
1549 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const ColIterator& block)
1550 : block_(block)
1551 {}
1552
1553 template<class M>
1554 template<class C>
1555 template<class C1>
1556 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const EdgeIteratorT<C1>& other)
1557 : source_(other.source_), block_(other.block_), blockEnd_(other.blockEnd_), edge_(other.edge_)
1558 {}
1559
1560
1561 template<class M>
1562 template<class C>
1563 inline typename MatrixGraph<M>::template EdgeIteratorT<C>::WeightType&
1564 MatrixGraph<M>::EdgeIteratorT<C>::weight() const
1565 {
1566 return *block_;
1567 }
1568
1569 template<class M>
1570 template<class C>
1571 inline typename MatrixGraph<M>::template EdgeIteratorT<C>& MatrixGraph<M>::EdgeIteratorT<C>::operator++()
1572 {
1573 ++block_;
1574 ++edge_;
1575
1576 if(block_!=blockEnd_ && block_.index() == source_) {
1577 // This is the edge from the diagonal to the diagonal. Skip it.
1578 ++block_;
1579 }
1580
1581 return *this;
1582 }
1583
1584 template<class M>
1585 template<class C>
1586 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(const typename MatrixGraph<M>::template EdgeIteratorT<typename std::remove_const<C>::type>& other) const
1587 {
1588 return block_!=other.block_;
1589 }
1590
1591 template<class M>
1592 template<class C>
1593 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(const typename MatrixGraph<M>::template EdgeIteratorT<const typename std::remove_const<C>::type>& other) const
1594 {
1595 return block_!=other.block_;
1596 }
1597
1598 template<class M>
1599 template<class C>
1600 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator==(const typename MatrixGraph<M>::template EdgeIteratorT<typename std::remove_const<C>::type>& other) const
1601 {
1602 return block_==other.block_;
1603 }
1604
1605 template<class M>
1606 template<class C>
1607 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator==(const typename MatrixGraph<M>::template EdgeIteratorT<const typename std::remove_const<C>::type>& other) const
1608 {
1609 return block_==other.block_;
1610 }
1611
1612 template<class M>
1613 template<class C>
1614 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::target() const
1615 {
1616 return block_.index();
1617 }
1618
1619 template<class M>
1620 template<class C>
1621 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::source() const
1622 {
1623 return source_;
1624 }
1625
1626 template<class M>
1627 template<class C>
1628 inline const typename MatrixGraph<M>::EdgeDescriptor& MatrixGraph<M>::EdgeIteratorT<C>::operator*() const
1629 {
1630 return edge_;
1631 }
1632
1633 template<class M>
1634 template<class C>
1635 inline const typename MatrixGraph<M>::EdgeDescriptor* MatrixGraph<M>::EdgeIteratorT<C>::operator->() const
1636 {
1637 return &edge_;
1638 }
1639
1640 template<class M>
1641 template<class C>
1642 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(C* graph,
1643 const VertexDescriptor& current)
1644 : graph_(graph), current_(current)
1645 {}
1646
1647
1648 template<class M>
1649 template<class C>
1650 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(const VertexDescriptor& current)
1651 : current_(current)
1652 {}
1653
1654 template<class M>
1655 template<class C>
1656 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(const VertexIteratorT<MutableContainer>& other)
1657 : graph_(other.graph_), current_(other.current_)
1658 {}
1659
1660 template<class M>
1661 template<class C>
1662 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(const VertexIteratorT<MutableContainer>& other) const
1663 {
1664 return current_ != other.current_;
1665 }
1666
1667 template<class M>
1668 template<class C>
1669 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(const VertexIteratorT<ConstContainer>& other) const
1670 {
1671 return current_ != other.current_;
1672 }
1673
1674
1675 template<class M>
1676 template<class C>
1677 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(const VertexIteratorT<MutableContainer>& other) const
1678 {
1679 return current_ == other.current_;
1680 }
1681
1682 template<class M>
1683 template<class C>
1684 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(const VertexIteratorT<ConstContainer>& other) const
1685 {
1686 return current_ == other.current_;
1687 }
1688
1689 template<class M>
1690 template<class C>
1691 inline typename MatrixGraph<M>::template VertexIteratorT<C>& MatrixGraph<M>::VertexIteratorT<C>::operator++()
1692 {
1693 ++current_;
1694 return *this;
1695 }
1696
1697 template<class M>
1698 template<class C>
1699 inline typename MatrixGraph<M>::template VertexIteratorT<C>::WeightType&
1700 MatrixGraph<M>::VertexIteratorT<C>::weight() const
1701 {
1702 return graph_->matrix()[current_][current_];
1703 }
1704
1705 template<class M>
1706 template<class C>
1707 inline const typename MatrixGraph<M>::VertexDescriptor&
1708 MatrixGraph<M>::VertexIteratorT<C>::operator*() const
1709 {
1710 return current_;
1711 }
1712
1713 template<class M>
1714 template<class C>
1715 inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1716 MatrixGraph<M>::VertexIteratorT<C>::begin() const
1717 {
1718 return graph_->beginEdges(current_);
1719 }
1720
1721 template<class M>
1722 template<class C>
1723 inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1724 MatrixGraph<M>::VertexIteratorT<C>::end() const
1725 {
1726 return graph_->endEdges(current_);
1727 }
1728
1729 template<class M>
1730 inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1731 MatrixGraph<M>::begin()
1732 {
1733 return VertexIterator(this,0);
1734 }
1735
1736 template<class M>
1737 inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1738 MatrixGraph<M>::end()
1739 {
1740 return VertexIterator(matrix_.N());
1741 }
1742
1743
1744 template<class M>
1745 inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1746 MatrixGraph<M>::begin() const
1747 {
1748 return ConstVertexIterator(this, 0);
1749 }
1750
1751 template<class M>
1752 inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1753 MatrixGraph<M>::end() const
1754 {
1755 return ConstVertexIterator(matrix_.N());
1756 }
1757
1758 template<class M>
1759 inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1760 MatrixGraph<M>::beginEdges(const VertexDescriptor& source)
1761 {
1762 return EdgeIterator(source, matrix_.operator[](source).begin(),
1763 matrix_.operator[](source).end(), start_[source]);
1764 }
1765
1766 template<class M>
1767 inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1768 MatrixGraph<M>::endEdges(const VertexDescriptor& source)
1769 {
1770 return EdgeIterator(matrix_.operator[](source).end());
1771 }
1772
1773
1774 template<class M>
1775 inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
1776 MatrixGraph<M>::beginEdges(const VertexDescriptor& source) const
1777 {
1778 return ConstEdgeIterator(source, matrix_.operator[](source).begin(),
1779 matrix_.operator[](source).end(), start_[source]);
1780 }
1781
1782 template<class M>
1783 inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
1784 MatrixGraph<M>::endEdges(const VertexDescriptor& source) const
1785 {
1786 return ConstEdgeIterator(matrix_.operator[](source).end());
1787 }
1788
1789
1790 template<class G, class T>
1791 SubGraph<G,T>::EdgeIterator::EdgeIterator(const VertexDescriptor& source,
1792 const EdgeDescriptor& edge)
1793 : source_(source), edge_(edge)
1794 {}
1795
1796
1797 template<class G, class T>
1798 SubGraph<G,T>::EdgeIterator::EdgeIterator(const EdgeDescriptor& edge)
1799 : edge_(edge)
1800 {}
1801
1802 template<class G, class T>
1803 typename SubGraph<G,T>::EdgeIndexMap SubGraph<G,T>::getEdgeIndexMap()
1804 {
1805 return EdgeIndexMap(edges_);
1806 }
1807
1808 template<class G, class T>
1809 inline bool SubGraph<G,T>::EdgeIterator::equals(const EdgeIterator & other) const
1810 {
1811 return other.edge_==edge_;
1812 }
1813
1814 template<class G, class T>
1815 inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::increment()
1816 {
1817 ++edge_;
1818 return *this;
1819 }
1820
1821 template<class G, class T>
1822 inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::decrement()
1823 {
1824 --edge_;
1825 return *this;
1826 }
1827
1828 template<class G, class T>
1829 inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::advance(std::ptrdiff_t n)
1830 {
1831 edge_+=n;
1832 return *this;
1833 }
1834 template<class G, class T>
1835 inline const typename G::VertexDescriptor& SubGraph<G,T>::EdgeIterator::source() const
1836 {
1837 return source_;
1838 }
1839
1840 template<class G, class T>
1841 inline const typename G::VertexDescriptor& SubGraph<G,T>::EdgeIterator::target() const
1842 {
1843 return *edge_;
1844 }
1845
1846
1847 template<class G, class T>
1848 inline const typename SubGraph<G,T>::EdgeDescriptor& SubGraph<G,T>::EdgeIterator::dereference() const
1849 {
1850 return edge_;
1851 }
1852
1853 template<class G, class T>
1854 inline std::ptrdiff_t SubGraph<G,T>::EdgeIterator::distanceTo(const EdgeIterator & other) const
1855 {
1856 return other.edge_-edge_;
1857 }
1858
1859 template<class G, class T>
1860 SubGraph<G,T>::VertexIterator::VertexIterator(const SubGraph<G,T>* graph,
1861 const VertexDescriptor& current,
1862 const VertexDescriptor& end)
1863 : graph_(graph), current_(current), end_(end)
1864 {
1865 // Skip excluded vertices
1866 typedef typename T::const_iterator Iterator;
1867
1868 for(Iterator vertex = graph_->excluded_.begin();
1869 current_ != end_ && *vertex;
1870 ++vertex)
1871 ++current_;
1872 assert(current_ == end_ || !graph_->excluded_[current_]);
1873 }
1874
1875 template<class G, class T>
1876 SubGraph<G,T>::VertexIterator::VertexIterator(const VertexDescriptor& current)
1877 : current_(current)
1878 {}
1879
1880 template<class G, class T>
1881 inline typename SubGraph<G,T>::VertexIterator& SubGraph<G,T>::VertexIterator::increment()
1882 {
1883 ++current_;
1884 //Skip excluded vertices
1885 while(current_ != end_ && graph_->excluded_[current_])
1886 ++current_;
1887
1888 assert(current_ == end_ || !graph_->excluded_[current_]);
1889 return *this;
1890 }
1891
1892 template<class G, class T>
1893 inline bool SubGraph<G,T>::VertexIterator::equals(const VertexIterator & other) const
1894 {
1895 return current_==other.current_;
1896 }
1897
1898 template<class G, class T>
1899 inline const typename G::VertexDescriptor& SubGraph<G,T>::VertexIterator::dereference() const
1900 {
1901 return current_;
1902 }
1903
1904 template<class G, class T>
1905 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::VertexIterator::begin() const
1906 {
1907 return graph_->beginEdges(current_);
1908 }
1909
1910 template<class G, class T>
1911 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::VertexIterator::end() const
1912 {
1913 return graph_->endEdges(current_);
1914 }
1915
1916 template<class G, class T>
1917 inline typename SubGraph<G,T>::VertexIterator SubGraph<G,T>::begin() const
1918 {
1919 return VertexIterator(this, 0, endVertex_);
1920 }
1921
1922
1923 template<class G, class T>
1924 inline typename SubGraph<G,T>::VertexIterator SubGraph<G,T>::end() const
1925 {
1926 return VertexIterator(endVertex_);
1927 }
1928
1929
1930 template<class G, class T>
1931 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::beginEdges(const VertexDescriptor& source) const
1932 {
1933 return EdgeIterator(source, edges_+start_[source]);
1934 }
1935
1936 template<class G, class T>
1937 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::endEdges(const VertexDescriptor& source) const
1938 {
1939 return EdgeIterator(edges_+end_[source]);
1940 }
1941
1942 template<class G, class T>
1943 std::size_t SubGraph<G,T>::noVertices() const
1944 {
1945 return noVertices_;
1946 }
1947
1948 template<class G, class T>
1949 inline typename SubGraph<G,T>::VertexDescriptor SubGraph<G,T>::maxVertex() const
1950 {
1951 return maxVertex_;
1952 }
1953
1954 template<class G, class T>
1955 inline std::size_t SubGraph<G,T>::noEdges() const
1956 {
1957 return noEdges_;
1958 }
1959
1960 template<class G, class T>
1961 inline typename SubGraph<G,T>::EdgeDescriptor SubGraph<G,T>::findEdge(const VertexDescriptor& source,
1962 const VertexDescriptor& target) const
1963 {
1964 const EdgeDescriptor edge = std::lower_bound(edges_+start_[source], edges_+end_[source], target);
1965 if(edge==edges_+end_[source] || *edge!=target)
1966 return std::numeric_limits<EdgeDescriptor>::max();
1967
1968 return edge;
1969 }
1970
1971 template<class G, class T>
1972 SubGraph<G,T>::~SubGraph()
1973 {
1974 delete[] edges_;
1975 delete[] end_;
1976 delete[] start_;
1977 }
1978
1979 template<class G, class T>
1980 SubGraph<G,T>::SubGraph(const G& graph, const T& excluded)
1981 : excluded_(excluded), noVertices_(0), endVertex_(0), maxVertex_(graph.maxVertex())
1982 {
1983 start_ = new std::ptrdiff_t[graph.noVertices()];
1984 end_ = new std::ptrdiff_t[graph.noVertices()];
1985 edges_ = new VertexDescriptor[graph.noEdges()];
1986
1987 VertexDescriptor* edge=edges_;
1988
1989 // Cater for the case that there are no vertices.
1990 // Otherwise endVertex_ will get 1 below.
1991 if ( graph.noVertices() == 0)
1992 return;
1993
1994 typedef typename Graph::ConstVertexIterator Iterator;
1995 Iterator endVertex=graph.end();
1996
1997 for(Iterator vertex = graph.begin(); vertex != endVertex; ++vertex)
1998 if(excluded_[*vertex])
1999 start_[*vertex]=end_[*vertex]=-1;
2000 else{
2001 ++noVertices_;
2002 endVertex_ = std::max(*vertex, endVertex_);
2003
2004 start_[*vertex] = edge-edges_;
2005
2006 typedef typename Graph::ConstEdgeIterator Iterator;
2007 Iterator endEdge = vertex.end();
2008
2009 for(Iterator iter=vertex.begin(); iter!= endEdge; ++iter)
2010 if(!excluded[iter.target()]) {
2011 *edge = iter.target();
2012 ++edge;
2013 }
2014
2015 end_[*vertex] = edge - edges_;
2016
2017 // Sort the edges
2018 std::sort(edges_+start_[*vertex], edge);
2019 }
2020 noEdges_ = edge-edges_;
2021 ++endVertex_;
2022 }
2023
2024 template<class G, class V, class VM>
2025 inline std::size_t VertexPropertiesGraph<G,V,VM>::noEdges() const
2026 {
2027 return graph_.noEdges();
2028 }
2029
2030 template<class G, class V, class VM>
2031 inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2032 VertexPropertiesGraph<G,V,VM>::beginEdges(const VertexDescriptor& source)
2033 {
2034 return graph_.beginEdges(source);
2035 }
2036
2037 template<class G, class V, class VM>
2038 inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2039 VertexPropertiesGraph<G,V,VM>::endEdges(const VertexDescriptor& source)
2040 {
2041 return graph_.endEdges(source);
2042 }
2043
2044 template<class G, class V, class VM>
2045 typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2046 inline VertexPropertiesGraph<G,V,VM>::beginEdges(const VertexDescriptor& source) const
2047 {
2048 return graph_.beginEdges(source);
2049 }
2050
2051 template<class G, class V, class VM>
2052 typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2053 VertexPropertiesGraph<G,V,VM>::endEdges(const VertexDescriptor& source) const
2054 {
2055 return graph_.endEdges(source);
2056 }
2057
2058 template<class G, class V, class VM>
2059 template<class C>
2060 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2061 ::VertexIteratorT(const Father& iter,
2062 C* graph)
2063 : Father(iter), graph_(graph)
2064 {}
2065
2066 template<class G, class V, class VM>
2067 template<class C>
2068 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2069 ::VertexIteratorT(const Father& iter)
2070 : Father(iter)
2071 {}
2072
2073 template<class G, class V, class VM>
2074 template<class C>
2075 template<class C1>
2076 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2077 ::VertexIteratorT(const VertexIteratorT<C1>& other)
2078 : Father(other), graph_(other.graph_)
2079 {}
2080
2081 template<class G, class V, class VM>
2082 template<class C>
2083 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
2084 V&, const V&>::type
2085 inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::properties() const
2086 {
2087 return graph_->getVertexProperties(Father::operator*());
2088 }
2089
2090 template<class G, class V, class VM>
2091 template<class C>
2092 typename std::conditional<std::is_same<typename std::remove_const<C>::type,
2093 C>::value,
2094 typename G::EdgeIterator,
2095 typename G::ConstEdgeIterator>::type
2096 inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::begin() const
2097 {
2098 return graph_->beginEdges(Father::operator*());
2099 }
2100
2101 template<class G, class V, class VM>
2102 template<class C>
2103 typename std::conditional<std::is_same<typename std::remove_const<C>::type,
2104 C>::value,
2105 typename G::EdgeIterator,
2106 typename G::ConstEdgeIterator>::type
2107 inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::end() const
2108 {
2109 return graph_->endEdges(Father::operator*());
2110 }
2111
2112 template<class G, class V, class VM>
2113 inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::begin()
2114 {
2115 return VertexIterator(graph_.begin(), this);
2116 }
2117
2118 template<class G, class V, class VM>
2119 inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::end()
2120 {
2121 return VertexIterator(graph_.end());
2122 }
2123
2124
2125 template<class G, class V, class VM>
2126 inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::begin() const
2127 {
2128 return ConstVertexIterator(graph_.begin(), this);
2129 }
2130
2131 template<class G, class V, class VM>
2132 inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::end() const
2133 {
2134 return ConstVertexIterator(graph_.end());
2135 }
2136
2137 template<class G, class V, class VM>
2138 inline V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(const VertexDescriptor& vertex)
2139 {
2140 return vertexProperties_[vmap_[vertex]];
2141 }
2142
2143 template<class G, class V, class VM>
2144 inline const V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(const VertexDescriptor& vertex) const
2145 {
2146 return vertexProperties_[vmap_[vertex]];
2147 }
2148
2149 template<class G, class V, class VM>
2150 inline const G& VertexPropertiesGraph<G,V,VM>::graph() const
2151 {
2152 return graph_;
2153 }
2154
2155 template<class G, class V, class VM>
2156 inline std::size_t VertexPropertiesGraph<G,V,VM>::noVertices() const
2157 {
2158 return graph_.noVertices();
2159 }
2160
2161
2162 template<class G, class V, class VM>
2163 inline typename VertexPropertiesGraph<G,V,VM>::VertexDescriptor VertexPropertiesGraph<G,V,VM>::maxVertex() const
2164 {
2165 return graph_.maxVertex();
2166 }
2167
2168 template<class G, class V, class VM>
2169 VertexPropertiesGraph<G,V,VM>::VertexPropertiesGraph(Graph& graph, const VM vmap)
2170 : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V())
2171 {}
2172
2173 template<class G, class V, class E, class VM, class EM>
2174 template<class C>
2175 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const Father& iter,
2176 C* graph)
2177 : Father(iter), graph_(graph)
2178 {}
2179
2180 template<class G, class V, class E, class VM, class EM>
2181 template<class C>
2182 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const Father& iter)
2183 : Father(iter)
2184 {}
2185
2186 template<class G, class V, class E, class VM, class EM>
2187 template<class C>
2188 template<class C1>
2189 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const EdgeIteratorT<C1>& other)
2190 : Father(other), graph_(other.graph_)
2191 {}
2192
2193
2194 template<class G, class V, class E, class VM, class EM>
2195 inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noEdges() const
2196 {
2197 return graph_.noEdges();
2198 }
2199
2200 template<class G, class V, class E, class VM, class EM>
2201 template<class C>
2202 inline typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,E&,const E&>::type
2203 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::properties() const
2204 {
2205 return graph_->getEdgeProperties(Father::operator*());
2206 }
2207
2208 template<class G, class V, class E, class VM, class EM>
2209 inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2210 PropertiesGraph<G,V,E,VM,EM>::beginEdges(const VertexDescriptor& source)
2211 {
2212 return EdgeIterator(graph_.beginEdges(source), this);
2213 }
2214
2215 template<class G, class V, class E, class VM, class EM>
2216 inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2217 PropertiesGraph<G,V,E,VM,EM>::endEdges(const VertexDescriptor& source)
2218 {
2219 return EdgeIterator(graph_.endEdges(source));
2220 }
2221
2222 template<class G, class V, class E, class VM, class EM>
2223 typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2224 inline PropertiesGraph<G,V,E,VM,EM>::beginEdges(const VertexDescriptor& source) const
2225 {
2226 return ConstEdgeIterator(graph_.beginEdges(source), this);
2227 }
2228
2229 template<class G, class V, class E, class VM, class EM>
2230 typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2231 PropertiesGraph<G,V,E,VM,EM>::endEdges(const VertexDescriptor& source) const
2232 {
2233 return ConstEdgeIterator(graph_.endEdges(source));
2234 }
2235
2236 template<class G, class V, class E, class VM, class EM>
2237 template<class C>
2238 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2239 ::VertexIteratorT(const Father& iter,
2240 C* graph)
2241 : Father(iter), graph_(graph)
2242 {}
2243
2244 template<class G, class V, class E, class VM, class EM>
2245 template<class C>
2246 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2247 ::VertexIteratorT(const Father& iter)
2248 : Father(iter)
2249 {}
2250
2251 template<class G, class V, class E, class VM, class EM>
2252 template<class C>
2253 template<class C1>
2254 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2255 ::VertexIteratorT(const VertexIteratorT<C1>& other)
2256 : Father(other), graph_(other.graph_)
2257 {}
2258
2259 template<class G, class V, class E, class VM, class EM>
2260 template<class C>
2261 inline typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
2262 V&, const V&>::type
2263 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::properties() const
2264 {
2265 return graph_->getVertexProperties(Father::operator*());
2266 }
2267
2268 template<class G, class V, class E, class VM, class EM>
2269 template<class C>
2270 inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2271 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::begin() const
2272 {
2273 return graph_->beginEdges(Father::operator*());
2274 }
2275
2276 template<class G, class V, class E, class VM, class EM>
2277 template<class C>
2278 inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2279 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::end() const
2280 {
2281 return graph_->endEdges(Father::operator*());
2282 }
2283
2284 template<class G, class V, class E, class VM, class EM>
2285 inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::begin()
2286 {
2287 return VertexIterator(graph_.begin(), this);
2288 }
2289
2290 template<class G, class V, class E, class VM, class EM>
2291 inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::end()
2292 {
2293 return VertexIterator(graph_.end());
2294 }
2295
2296
2297 template<class G, class V, class E, class VM, class EM>
2298 inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::begin() const
2299 {
2300 return ConstVertexIterator(graph_.begin(), this);
2301 }
2302
2303 template<class G, class V, class E, class VM, class EM>
2304 inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::end() const
2305 {
2306 return ConstVertexIterator(graph_.end());
2307 }
2308
2309 template<class G, class V, class E, class VM, class EM>
2310 inline V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(const VertexDescriptor& vertex)
2311 {
2312 return vertexProperties_[vmap_[vertex]];
2313 }
2314
2315 template<class G, class V, class E, class VM, class EM>
2316 inline const V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(const VertexDescriptor& vertex) const
2317 {
2318 return vertexProperties_[vmap_[vertex]];
2319 }
2320
2321 template<class G, class V, class E, class VM, class EM>
2322 inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const EdgeDescriptor& edge)
2323 {
2324 return edgeProperties_[emap_[edge]];
2325 }
2326
2327 template<class G, class V, class E, class VM, class EM>
2328 inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const EdgeDescriptor& edge) const
2329 {
2330 return edgeProperties_[emap_[edge]];
2331 }
2332
2333 template<class G, class V, class E, class VM, class EM>
2334 inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const VertexDescriptor& source,
2335 const VertexDescriptor& target)
2336 {
2337 return getEdgeProperties(graph_.findEdge(source,target));
2338 }
2339
2340 template<class G, class V, class E, class VM, class EM>
2341 inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const VertexDescriptor& source,
2342 const VertexDescriptor& target) const
2343 {
2344 return getEdgeProperties(graph_.findEdge(source,target));
2345 }
2346
2347 template<class G, class V, class E, class VM, class EM>
2348 inline const G& PropertiesGraph<G,V,E,VM,EM>::graph() const
2349 {
2350 return graph_;
2351 }
2352
2353 template<class G, class V, class E, class VM, class EM>
2354 inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noVertices() const
2355 {
2356 return graph_.noVertices();
2357 }
2358
2359
2360 template<class G, class V, class E, class VM, class EM>
2361 inline typename PropertiesGraph<G,V,E,VM,EM>::VertexDescriptor PropertiesGraph<G,V,E,VM,EM>::maxVertex() const
2362 {
2363 return graph_.maxVertex();
2364 }
2365
2366 template<class G, class V, class E, class VM, class EM>
2367 PropertiesGraph<G,V,E,VM,EM>::PropertiesGraph(Graph& graph, const VM& vmap, const EM& emap)
2368 : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V()),
2369 emap_(emap), edgeProperties_(graph_.noEdges(), E())
2370 {}
2371
2372 template<class G, class V>
2373 inline int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex,
2374 V& visitor)
2375 {
2376 typedef typename G::ConstEdgeIterator iterator;
2377 const iterator end = graph.endEdges(vertex);
2378 int noNeighbours=0;
2379 for(iterator edge = graph.beginEdges(vertex); edge != end; ++edge, ++noNeighbours)
2380 visitor(edge);
2381 return noNeighbours;
2382 }
2383
2384#endif // DOXYGEN
2385
2387 }
2388}
2389#endif
Wrapper to access the internal vertex properties of a graph via operator[]()
Definition: graph.hh:1407
EdgeProperties & operator[](const Edge &edge) const
Get the properties associated to a vertex.
Definition: graph.hh:1440
G::EdgeProperties EdgeProperties
The type of the vertex properties.
Definition: graph.hh:1416
G::EdgeDescriptor Edge
The edge descriptor.
Definition: graph.hh:1420
GraphEdgePropertiesSelector()
Default constructor.
Definition: graph.hh:1432
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1412
GraphEdgePropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1426
Wrapper to access the internal edge properties of a graph via operator[]()
Definition: graph.hh:1359
GraphVertexPropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1378
VertexProperties & operator[](const Vertex &vertex) const
Get the properties associated to a vertex.
Definition: graph.hh:1393
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1364
G::VertexProperties VertexProperties
The type of the vertex properties.
Definition: graph.hh:1368
GraphVertexPropertiesSelector()
Default constructor.
Definition: graph.hh:1384
G::VertexDescriptor Vertex
The vertex descriptor.
Definition: graph.hh:1372
Iterator over all edges starting from a vertex.
Definition: graph.hh:93
EdgeIteratorT(const VertexDescriptor &source, const ColIterator &block, const ColIterator &end, const EdgeDescriptor &edge)
Constructor.
VertexDescriptor target() const
The index of the target vertex of the current edge.
EdgeIteratorT< C > & operator++()
preincrement operator.
bool operator!=(const EdgeIteratorT< const typename std::remove_const< C >::type > &other) const
Inequality operator.
@ isMutable
whether C is mutable.
Definition: graph.hh:110
bool operator==(const EdgeIteratorT< const typename std::remove_const< C >::type > &other) const
Equality operator.
EdgeIteratorT(const EdgeIteratorT< C1 > &other)
Copy Constructor.
bool operator!=(const EdgeIteratorT< typename std::remove_const< C >::type > &other) const
Inequality operator.
WeightType & weight() const
Access the edge weight.
VertexDescriptor source() const
The index of the source vertex of the current edge.
std::conditional< isMutable &&C::mutableMatrix, typenameMatrix::row_type::Iterator, typenameMatrix::row_type::ConstIterator >::type ColIterator
The column iterator of the matrix we use.
Definition: graph.hh:118
const std::remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:103
bool operator==(const EdgeIteratorT< typename std::remove_const< C >::type > &other) const
Equality operator.
EdgeIteratorT(const ColIterator &block)
Constructor for the end iterator.
std::conditional< isMutable &&C::mutableMatrix, typenameM::block_type, consttypenameM::block_type >::type Weight
The matrix block type we use as weights.
Definition: graph.hh:125
const EdgeDescriptor & operator*() const
Get the edge descriptor.
const EdgeDescriptor * operator->() const
Get the edge descriptor.
std::remove_const< C >::type MutableContainer
The mutable type of the container type.
Definition: graph.hh:99
The vertex iterator type of the graph.
Definition: graph.hh:207
EdgeIteratorT< C > begin() const
Get an iterator over all edges starting at the current vertex.
const VertexDescriptor & operator*() const
Get the descriptor of the current vertex.
WeightType & weight() const
Access the weight of the vertex.
VertexIteratorT(C *graph, const VertexDescriptor &current)
Constructor.
std::remove_const< C >::type MutableContainer
The mutable type of the container type.
Definition: graph.hh:212
bool operator!=(const VertexIteratorT< MutableContainer > &other) const
Inequality operator.
bool operator==(const VertexIteratorT< MutableContainer > &other) const
Equality operator.
const std::remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:216
@ isMutable
whether C is mutable.
Definition: graph.hh:223
VertexIteratorT< C > & operator++()
Move to the next vertex.
EdgeIteratorT< C > end() const
Get an iterator over all edges starting at the current vertex.
bool operator==(const VertexIteratorT< ConstContainer > &other) const
Equality operator.
bool operator!=(const VertexIteratorT< ConstContainer > &other) const
Inequality operator.
VertexIteratorT(const VertexDescriptor &current)
Constructor for the end iterator.
The (undirected) graph of a matrix.
Definition: graph.hh:49
MatrixGraph(Matrix &matrix)
Constructor.
VertexIterator end()
Get an iterator over the vertices.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
M Matrix
The type of the matrix we are a graph for.
Definition: graph.hh:54
ConstVertexIterator begin() const
Get an iterator over the vertices.
VertexIteratorT< const MatrixGraph< Matrix > > ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:306
~MatrixGraph()
Destructor.
std::ptrdiff_t EdgeDescriptor
The edge descriptor.
Definition: graph.hh:78
ConstEdgeIterator endEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
M::size_type VertexDescriptor
The vertex descriptor.
Definition: graph.hh:71
const Matrix & matrix() const
Get the underlying matrix.
ConstEdgeIterator beginEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
ConstVertexIterator end() const
Get an iterator over the vertices.
EdgeIteratorT< const MatrixGraph< Matrix > > ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:296
EdgeIterator beginEdges(const VertexDescriptor &source)
Get an iterator over the edges starting at a vertex.
std::size_t noVertices() const
Get the number of vertices in the graph.
EdgeDescriptor findEdge(const VertexDescriptor &source, const VertexDescriptor &target) const
Find the descriptor of an edge.
M::block_type Weight
The type of the weights.
Definition: graph.hh:64
std::remove_const< M >::type MutableMatrix
The mutable type of the matrix we are a graph for.
Definition: graph.hh:59
EdgeIteratorT< MatrixGraph< Matrix > > EdgeIterator
The mutable edge iterator type.
Definition: graph.hh:301
VertexIteratorT< MatrixGraph< Matrix > > VertexIterator
The mutable vertex iterator type.
Definition: graph.hh:311
EdgeIterator endEdges(const VertexDescriptor &source)
Get an iterator over the edges starting at a vertex.
std::size_t noEdges() const
Get the number of edges in the graph.
Matrix & matrix()
Get the underlying matrix.
VertexIterator begin()
Get an iterator over the vertices.
Attaches properties to the edges and vertices of a graph.
Definition: graph.hh:976
EdgeIteratorT< PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > EdgeIterator
The type of the mutable edge iterator.
Definition: graph.hh:1094
std::size_t noVertices() const
Get the number of vertices in the graph.
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:991
const EdgeProperties & getEdgeProperties(const VertexDescriptor &source, const VertexDescriptor &target) const
Get the properties associated with a edge.
const EdgeProperties & getEdgeProperties(const EdgeDescriptor &edge) const
Get the properties associated with a edge.
const Graph & graph() const
Get the graph the properties are attached to.
EdgeIteratorT< const PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > ConstEdgeIterator
The type of the constant edge iterator.
Definition: graph.hh:1101
VertexIteratorT< PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > VertexIterator
The type of the mutable Vertex iterator.
Definition: graph.hh:1210
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
G Graph
The graph we attach properties to.
Definition: graph.hh:981
EM EdgeMap
The type of the map for converting the EdgeDescriptor to std::size_t.
Definition: graph.hh:1028
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:1009
VertexIteratorT< const PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > ConstVertexIterator
The type of the constant Vertex iterator.
Definition: graph.hh:1217
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:996
std::size_t noEdges() const
Get the number of edges in the graph.
EP EdgeProperties
The type of the properties of the edges;.
Definition: graph.hh:1014
EdgeProperties & getEdgeProperties(const VertexDescriptor &source, const VertexDescriptor &target)
Get the properties associated with a edge.
EdgeProperties & getEdgeProperties(const EdgeDescriptor &edge)
Get the properties associated with a edge.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:986
PropertiesGraph(Graph &graph, const VertexMap &vmap=VertexMap(), const EdgeMap &emap=EdgeMap())
Constructor.
An index map for mapping the edges to indices.
Definition: graph.hh:468
EdgeIndexMap(const EdgeIndexMap &emap)
Protect copy construction.
Definition: graph.hh:477
The edge iterator of the graph.
Definition: graph.hh:503
const EdgeDescriptor & dereference() const
The descriptor of the current edge.
EdgeIterator(const EdgeDescriptor &edge)
Constructor for the end iterator.
bool equals(const EdgeIterator &other) const
Equality operator.
EdgeIterator & increment()
Preincrement operator.
const VertexDescriptor & target() const
The index of the target vertex of the current edge.
const VertexDescriptor & source() const
The index of the source vertex of the current edge.
EdgeIterator & decrement()
Preincrement operator.
EdgeIterator(const VertexDescriptor &source, const EdgeDescriptor &edge)
Constructor.
The vertex iterator of the graph.
Definition: graph.hh:558
VertexIterator(const VertexDescriptor &current)
Constructor for end iterator.
VertexIterator & increment()
Preincrement operator.
EdgeIterator begin() const
Get an iterator over all edges starting at the current vertex.
bool equals(const VertexIterator &other) const
Equality iterator.
VertexIterator(const SubGraph< G, T > *graph, const VertexDescriptor &current, const VertexDescriptor &end)
Constructor.
EdgeIterator end() const
Get an iterator over all edges starting at the current vertex.
const VertexDescriptor & dereference() const
Get the descriptor of the current vertex.
A subgraph of a graph.
Definition: graph.hh:441
EdgeDescriptor findEdge(const VertexDescriptor &source, const VertexDescriptor &target) const
Find the descriptor of an edge.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
EdgeIndexMap getEdgeIndexMap()
Get an edge index map for the graph.
std::size_t noEdges() const
Get the number of edges in the graph.
ConstEdgeIterator endEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
ConstVertexIterator end() const
Get an iterator over the vertices.
ConstEdgeIterator beginEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
std::size_t noVertices() const
Get the number of vertices in the graph.
T Excluded
Random access container providing information about which vertices are excluded.
Definition: graph.hh:452
~SubGraph()
Destructor.
EdgeIterator ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:616
G Graph
The type of the graph we are a sub graph for.
Definition: graph.hh:446
VertexIterator ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:621
SubGraph(const Graph &graph, const T &excluded)
Constructor.
ConstVertexIterator begin() const
Get an iterator over the vertices.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:457
Attaches properties to the vertices of a graph.
Definition: graph.hh:721
VertexIterator end()
Get an iterator over the vertices.
const Graph & graph() const
Get the graph the properties are attached to.
Graph::ConstEdgeIterator ConstEdgeIterator
The type of the constant edge iterator.
Definition: graph.hh:764
VertexProperties & getVertexProperties(const VertexDescriptor &vertex)
Get the properties associated with a vertex.
std::size_t noEdges() const
Get the number of edges in the graph.
VertexIteratorT< const VertexPropertiesGraph< Graph, VertexProperties, VM > > ConstVertexIterator
The type of the constant Vertex iterator.
Definition: graph.hh:887
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:736
ConstEdgeIterator endEdges(const VertexDescriptor &source) const
Get the mutable edge iterator over edges starting at a vertex.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:731
G Graph
The graph we attach properties to.
Definition: graph.hh:726
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:754
EdgeIterator endEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
EdgeIterator beginEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:741
std::size_t noVertices() const
Get the number of vertices in the graph.
ConstEdgeIterator beginEdges(const VertexDescriptor &source) const
Get the mutable edge iterator over edges starting at a vertex.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
VertexIteratorT< VertexPropertiesGraph< Graph, VertexProperties, VM > > VertexIterator
The type of the mutable Vertex iterator.
Definition: graph.hh:881
VertexIterator begin()
Get an iterator over the vertices.
Graph::EdgeIterator EdgeIterator
The type of the mutable edge iterator.
Definition: graph.hh:759
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:144
derive error class from the base class in common
Definition: istlexception.hh:16
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:433
#define DUNE_THROW(E, m)
Definition: exceptions.hh:216
constexpr GeometryType vertex
GeometryType representing a vertex.
Definition: type.hh:727
constexpr auto equals(T1 &&t1, T2 &&t2)
Equality comparison.
Definition: hybridutilities.hh:435
int visitNeighbours(const G &graph, const typename G::VertexDescriptor &vertex, V &visitor)
Visit all neighbour vertices of a vertex in a graph.
EnableIfInterOperable< T1, T2, bool >::type operator==(const ForwardIteratorFacade< T1, V1, R1, D > &lhs, const ForwardIteratorFacade< T2, V2, R2, D > &rhs)
Checks for equality.
Definition: iteratorfacades.hh:233
EnableIfInterOperable< T1, T2, bool >::type operator!=(const ForwardIteratorFacade< T1, V1, R1, D > &lhs, const ForwardIteratorFacade< T2, V2, R2, D > &rhs)
Checks for inequality.
Definition: iteratorfacades.hh:255
This file implements iterator facade classes for writing stl conformant iterators.
Dune namespace.
Definition: alignedallocator.hh:10
STL namespace.
Tag for the category of readable property maps.
Definition: propertymap.hh:36
Traits for type conversions and type information.
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 24, 23:30, 2024)