DUNE-FEM (unstable)

graph.hh
Go to the documentation of this file.
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>
15#include <dune/istl/istlexception.hh>
16#include <dune/common/propertymap.hh>
17
18namespace Dune
19{
20 namespace Amg
21 {
49 template<class M>
51 {
52 public:
56 typedef M Matrix;
57
61 typedef typename std::remove_const<M>::type MutableMatrix;
62
66 typedef typename M::block_type Weight;
67
73 typedef typename M::size_type VertexDescriptor;
74
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
93 template<class C>
95 {
96
97 public:
101 typedef typename std::remove_const<C>::type MutableContainer;
105 typedef const typename std::remove_const<C>::type ConstContainer;
106
107 friend class EdgeIteratorT<MutableContainer>;
108 friend class EdgeIteratorT<ConstContainer>;
109
110 enum {
112 isMutable = std::is_same<C, MutableContainer>::value
113 };
114
118 typedef typename std::conditional<isMutable && C::mutableMatrix,typename Matrix::row_type::Iterator,
119 typename Matrix::row_type::ConstIterator>::type
121
125 typedef typename std::conditional<isMutable && C::mutableMatrix,typename M::block_type,
126 const typename M::block_type>::type
128
137 const ColIterator& end, const EdgeDescriptor& edge);
138
146
151 template<class C1>
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
161 WeightType& weight() const;
162
165
167 bool operator!=(const EdgeIteratorT<typename std::remove_const<C>::type>& other) const;
168
170 bool operator!=(const EdgeIteratorT<const typename std::remove_const<C>::type>& other) const;
171
173 bool operator==(const EdgeIteratorT<typename std::remove_const<C>::type>& other) const;
174
176 bool operator==(const EdgeIteratorT<const typename std::remove_const<C>::type>& other) const;
177
180
183
185 const EdgeDescriptor& operator*() const;
186
189
190 private:
192 VertexDescriptor source_;
194 ColIterator block_;
195 /***
196 * @brief The column iterator positioned at the end of the row
197 * of vertex source_
198 */
199 ColIterator blockEnd_;
201 EdgeDescriptor edge_;
202 };
203
207 template<class C>
209 {
210 public:
214 typedef typename std::remove_const<C>::type MutableContainer;
218 typedef const typename std::remove_const<C>::type ConstContainer;
219
220 friend class VertexIteratorT<MutableContainer>;
221 friend class VertexIteratorT<ConstContainer>;
222
223 enum {
225 isMutable = std::is_same<C, MutableContainer>::value
226 };
227
233 explicit VertexIteratorT(C* graph, const VertexDescriptor& current);
234
242 explicit VertexIteratorT(const VertexDescriptor& current);
243
245
251
254
257
260
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;
268 WeightType& weight() const;
269
275
282
289
290 private:
291 C* graph_;
292 VertexDescriptor current_;
293 };
294
299
304
309
314
320
325
331
337
343
349
357
365
366
374
382
388
393 const Matrix& matrix() const;
394
398 std::size_t noVertices() const;
399
407
411 std::size_t noEdges() const;
412
420 const VertexDescriptor& target) const;
421
422 private:
424 Matrix& matrix_;
426 EdgeDescriptor* start_;
428 MatrixGraph(const MatrixGraph&);
429
430 };
431
441 template<class G, class T>
443 {
444 public:
448 typedef G Graph;
449
454 typedef T Excluded;
455
459 typedef typename Graph::VertexDescriptor VertexDescriptor;
460
461 typedef VertexDescriptor* EdgeDescriptor;
462
470 {
471 public:
473
474 EdgeIndexMap(const EdgeDescriptor& firstEdge)
475 : firstEdge_(firstEdge)
476 {}
477
480 : firstEdge_(emap.firstEdge_)
481 {}
482
483 std::size_t operator[](const EdgeDescriptor& edge) const
484 {
485 return edge-firstEdge_;
486 }
487 private:
489 EdgeDescriptor firstEdge_;
491 EdgeIndexMap()
492 {}
493 };
494
500
504 class EdgeIterator : public RandomAccessIteratorFacade<EdgeIterator,const EdgeDescriptor>
505 {
506 public:
512 explicit EdgeIterator(const VertexDescriptor& source, const EdgeDescriptor& edge);
513
521 explicit EdgeIterator(const EdgeDescriptor& edge);
522
524 bool equals(const EdgeIterator& other) const;
525
528
531
532 EdgeIterator& advance(std::ptrdiff_t n);
533
535 const EdgeDescriptor& dereference() const;
536
538 const VertexDescriptor& target() const;
539
541 const VertexDescriptor& source() const;
542
543 std::ptrdiff_t distanceTo(const EdgeIterator& other) const;
544
545 private:
547 VertexDescriptor source_;
552 EdgeDescriptor edge_;
553 };
554
559 : public ForwardIteratorFacade<VertexIterator,const VertexDescriptor>
560 {
561 public:
568 explicit VertexIterator(const SubGraph<G,T>* graph, const VertexDescriptor& current,
569 const VertexDescriptor& end);
570
571
578 explicit VertexIterator(const VertexDescriptor& current);
579
582
584 bool equals(const VertexIterator& other) const;
585
591
598
605
606 private:
608 const SubGraph<Graph,T>* graph_;
610 VertexDescriptor current_;
612 VertexDescriptor end_;
613 };
614
619
624
630
636
644
652
656 std::size_t noVertices() const;
657
665
669 std::size_t noEdges() const;
676 EdgeDescriptor findEdge(const VertexDescriptor& source,
677 const VertexDescriptor& target) const;
685 SubGraph(const Graph& graph, const T& excluded);
686
691
692 private:
694 const T& excluded_;
696 std::size_t noVertices_;
698 VertexDescriptor endVertex_;
700 int noEdges_;
705 VertexDescriptor maxVertex_;
707 VertexDescriptor* edges_;
709 std::ptrdiff_t* start_;
711 std::ptrdiff_t* end_;
713 SubGraph(const SubGraph&)
714 {}
715 };
716
717
721 template<class G, class VP, class VM=IdentityMap>
723 {
724 public:
728 typedef G Graph;
729
733 typedef typename Graph::VertexDescriptor VertexDescriptor;
734
738 typedef typename Graph::EdgeDescriptor EdgeDescriptor;
739
744
756 typedef VM VertexMap;
757
761 typedef typename Graph::EdgeIterator EdgeIterator;
762
766 typedef typename Graph::ConstEdgeIterator ConstEdgeIterator;
767
774
781
788
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:
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
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
824
830 explicit VertexIteratorT(const Father& iter,
831 C* graph);
832
833
841 explicit VertexIteratorT(const Father& iter);
842
847 template<class C1>
848 VertexIteratorT(const VertexIteratorT<C1>& other);
849
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
863 EdgeIterator begin() const;
864
870 EdgeIterator end() const;
871
872 private:
876 C* graph_;
877 };
878
882 typedef VertexIteratorT<VertexPropertiesGraph<Graph,
883 VertexProperties,VM> > VertexIterator;
884
888 typedef VertexIteratorT<const VertexPropertiesGraph<Graph,
889 VertexProperties,VM> > ConstVertexIterator;
890
896
902
908
914
920 VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
921
927 const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
928
933 const Graph& graph() const;
934
938 std::size_t noVertices() const;
939
943 std::size_t noEdges() const;
944
952
958 VertexPropertiesGraph(Graph& graph, const VertexMap vmap=VertexMap());
959
960 private:
961 VertexPropertiesGraph(const VertexPropertiesGraph&)
962 {}
963
965 Graph& graph_;
967 VertexMap vmap_;
969 std::vector<VertexProperties> vertexProperties_;
970
971 };
972
976 template<class G, class VP, class EP, class VM=IdentityMap, class EM=IdentityMap>
978 {
979 public:
983 typedef G Graph;
984
988 typedef typename Graph::VertexDescriptor VertexDescriptor;
989
993 typedef typename Graph::EdgeDescriptor EdgeDescriptor;
994
999
1011 typedef VM VertexMap;
1012
1016 typedef EP EdgeProperties;
1017
1018
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:
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
1057 explicit EdgeIteratorT(const Father& iter,
1058 C* graph);
1059
1067 explicit EdgeIteratorT(const Father& iter);
1068
1073 template<class C1>
1074 EdgeIteratorT(const EdgeIteratorT<C1>& other);
1075
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:
1088 C* graph_;
1089 };
1090
1094 typedef EdgeIteratorT<PropertiesGraph<Graph,
1095 VertexProperties,
1096 EdgeProperties,VM,EM> > EdgeIterator;
1097
1101 typedef EdgeIteratorT<const PropertiesGraph<Graph,
1102 VertexProperties,
1103 EdgeProperties,VM,EM> > ConstEdgeIterator;
1104
1110 EdgeIterator beginEdges(const VertexDescriptor& source);
1111
1117 EdgeIterator endEdges(const VertexDescriptor& source);
1118
1124 ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
1125
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:
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
1158 explicit VertexIteratorT(const Father& iter,
1159 C* graph);
1160
1161
1169 explicit VertexIteratorT(const Father& iter);
1170
1175 template<class C1>
1176 VertexIteratorT(const VertexIteratorT<C1>& other);
1177
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
1191 EdgeIteratorT<C> begin() const;
1192
1198 EdgeIteratorT<C> end() const;
1199
1200 private:
1204 C* graph_;
1205 };
1206
1210 typedef VertexIteratorT<PropertiesGraph<Graph,
1211 VertexProperties,
1212 EdgeProperties,VM,EM> > VertexIterator;
1213
1217 typedef VertexIteratorT<const PropertiesGraph<Graph,
1218 VertexProperties,
1219 EdgeProperties,VM,EM> > ConstVertexIterator;
1220
1226
1232
1238
1244
1250 VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
1251
1257 const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
1258
1265 EdgeDescriptor findEdge(const VertexDescriptor& source,
1266 const VertexDescriptor& target)
1267 {
1268 return graph_.findEdge(source,target);
1269 }
1270
1277
1278
1285
1293 const VertexDescriptor& target);
1294
1302 const VertexDescriptor& target) const;
1303
1308 const Graph& graph() const;
1309
1313 std::size_t noVertices() const;
1314
1318 std::size_t noEdges() const;
1319
1327
1335 const EdgeMap& emap=EdgeMap());
1336
1337 private:
1339 {}
1340
1342 Graph& graph_;
1345 VertexMap vmap_;
1346 std::vector<VertexProperties> vertexProperties_;
1348 EdgeMap emap_;
1350 std::vector<EdgeProperties> edgeProperties_;
1351
1352 };
1353
1354
1359 template<typename G>
1361 {
1362 public:
1366 typedef G Graph;
1370 typedef typename G::VertexProperties VertexProperties;
1374 typedef typename G::VertexDescriptor Vertex;
1375
1381 : graph_(g)
1382 {}
1387 : graph_(0)
1388 {}
1389
1390
1396 {
1397 return graph_->getVertexProperties(vertex);
1398 }
1399 private:
1400 Graph* graph_;
1401 };
1402
1407 template<typename G>
1409 {
1410 public:
1414 typedef G Graph;
1418 typedef typename G::EdgeProperties EdgeProperties;
1422 typedef typename G::EdgeDescriptor Edge;
1423
1429 : graph_(g)
1430 {}
1435 : graph_(0)
1436 {}
1437
1442 EdgeProperties& operator[](const Edge& edge) const
1443 {
1444 return graph_->getEdgeProperties(edge);
1445 }
1446 private:
1447 Graph* graph_;
1448 };
1449
1450
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>
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())
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)
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
2388 }
2389}
2390#endif
Wrapper to access the internal vertex properties of a graph via operator[]()
Definition: graph.hh:1409
EdgeProperties & operator[](const Edge &edge) const
Get the properties associated to a vertex.
Definition: graph.hh:1442
G::EdgeProperties EdgeProperties
The type of the vertex properties.
Definition: graph.hh:1418
G::EdgeDescriptor Edge
The edge descriptor.
Definition: graph.hh:1422
GraphEdgePropertiesSelector()
Default constructor.
Definition: graph.hh:1434
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1414
GraphEdgePropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1428
Wrapper to access the internal edge properties of a graph via operator[]()
Definition: graph.hh:1361
GraphVertexPropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1380
VertexProperties & operator[](const Vertex &vertex) const
Get the properties associated to a vertex.
Definition: graph.hh:1395
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1366
G::VertexProperties VertexProperties
The type of the vertex properties.
Definition: graph.hh:1370
GraphVertexPropertiesSelector()
Default constructor.
Definition: graph.hh:1386
G::VertexDescriptor Vertex
The vertex descriptor.
Definition: graph.hh:1374
Iterator over all edges starting from a vertex.
Definition: graph.hh:95
EdgeIteratorT(const VertexDescriptor &source, const ColIterator &block, const ColIterator &end, const EdgeDescriptor &edge)
Constructor.
@ isMutable
whether C is mutable.
Definition: graph.hh:112
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.
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:120
const std::remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:105
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:127
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:101
The vertex iterator type of the graph.
Definition: graph.hh:209
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:214
@ isMutable
whether C is mutable.
Definition: graph.hh:225
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:218
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:51
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:56
ConstVertexIterator begin() const
Get an iterator over the vertices.
VertexIteratorT< const MatrixGraph< Matrix > > ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:308
~MatrixGraph()
Destructor.
std::ptrdiff_t EdgeDescriptor
The edge descriptor.
Definition: graph.hh:80
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:73
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:298
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:66
std::remove_const< M >::type MutableMatrix
The mutable type of the matrix we are a graph for.
Definition: graph.hh:61
EdgeIteratorT< MatrixGraph< Matrix > > EdgeIterator
The mutable edge iterator type.
Definition: graph.hh:303
VertexIteratorT< MatrixGraph< Matrix > > VertexIterator
The mutable vertex iterator type.
Definition: graph.hh:313
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:978
EdgeIteratorT< PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > EdgeIterator
The type of the mutable edge iterator.
Definition: graph.hh:1096
std::size_t noVertices() const
Get the number of vertices in the graph.
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:993
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:1103
VertexIteratorT< PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > VertexIterator
The type of the mutable Vertex iterator.
Definition: graph.hh:1212
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
G Graph
The graph we attach properties to.
Definition: graph.hh:983
EM EdgeMap
The type of the map for converting the EdgeDescriptor to std::size_t.
Definition: graph.hh:1030
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:1011
VertexIteratorT< const PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > ConstVertexIterator
The type of the constant Vertex iterator.
Definition: graph.hh:1219
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:998
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:1016
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:988
PropertiesGraph(Graph &graph, const VertexMap &vmap=VertexMap(), const EdgeMap &emap=EdgeMap())
Constructor.
An index map for mapping the edges to indices.
Definition: graph.hh:470
EdgeIndexMap(const EdgeIndexMap &emap)
Protect copy construction.
Definition: graph.hh:479
The edge iterator of the graph.
Definition: graph.hh:505
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:560
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:443
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:454
~SubGraph()
Destructor.
EdgeIterator ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:618
G Graph
The type of the graph we are a sub graph for.
Definition: graph.hh:448
VertexIterator ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:623
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:459
Attaches properties to the vertices of a graph.
Definition: graph.hh:723
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:766
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:889
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:738
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:733
G Graph
The graph we attach properties to.
Definition: graph.hh:728
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:756
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:743
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:883
VertexIterator begin()
Get an iterator over the vertices.
Graph::EdgeIterator EdgeIterator
The type of the mutable edge iterator.
Definition: graph.hh:761
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:142
derive error class from the base class in common
Definition: istlexception.hh:19
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:435
#define DUNE_THROW(E, m)
Definition: exceptions.hh:218
constexpr GeometryType vertex
GeometryType representing a vertex.
Definition: type.hh:492
constexpr auto equals(T1 &&t1, T2 &&t2)
Equality comparison.
Definition: hybridutilities.hh:587
constexpr auto max
Function object that returns the greater of the given values.
Definition: hybridutilities.hh:484
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:238
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:260
This file implements iterator facade classes for writing stl conformant iterators.
Dune namespace.
Definition: alignedallocator.hh:13
STL namespace.
Tag for the category of readable property maps.
Definition: propertymap.hh:38
Traits for type conversions and type information.
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 21, 23:30, 2024)