dune-istl  2.3.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 // $Id$
4 #ifndef DUNE_AMG_GRAPH_HH
5 #define DUNE_AMG_GRAPH_HH
6 
7 #include <cstddef>
8 #include <algorithm>
9 #include <vector>
10 #include <cassert>
11 #include <limits>
12 #include <dune/common/typetraits.hh>
13 #include <dune/common/iteratorfacades.hh>
15 #include <dune/common/propertymap.hh>
16 
17 namespace Dune
18 {
19  namespace Amg
20  {
48  template<class M>
50  {
51  public:
55  typedef M Matrix;
56 
61 
65  typedef typename M::block_type Weight;
66 
72  typedef typename M::size_type VertexDescriptor;
73 
79  typedef std::ptrdiff_t EdgeDescriptor;
80 
81  enum {
82  /*
83  * @brief Whether Matrix is mutable.
84  */
86  };
87 
88 
92  template<class C>
94  {
95 
96  public:
104  typedef const typename remove_const<C>::type ConstContainer;
105 
108 
109  enum {
111  isMutable = is_same<C, MutableContainer>::value
112  };
113 
117  typedef typename conditional<isMutable && C::mutableMatrix,typename Matrix::row_type::Iterator,
118  typename Matrix::row_type::ConstIterator>::type
120 
124  typedef typename conditional<isMutable && C::mutableMatrix,typename M::block_type,
125  const typename M::block_type>::type
127 
135  EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block,
136  const ColIterator& end, const EdgeDescriptor& edge);
137 
144  EdgeIteratorT(const ColIterator& block);
145 
150  template<class C1>
151  EdgeIteratorT(const EdgeIteratorT<C1>& other);
152 
153  typedef typename conditional<is_same<C, typename remove_const<C>::type>::value && C::mutableMatrix,
154  typename M::block_type, const typename M::block_type>::type
156 
160  WeightType& weight() const;
161 
164 
166  bool operator!=(const EdgeIteratorT<typename remove_const<C>::type>& other) const;
167 
169  bool operator!=(const EdgeIteratorT<const typename remove_const<C>::type>& other) const;
170 
172  bool operator==(const EdgeIteratorT<typename remove_const<C>::type>& other) const;
173 
175  bool operator==(const EdgeIteratorT<const typename remove_const<C>::type>& other) const;
176 
178  VertexDescriptor target() const;
179 
181  VertexDescriptor source() const;
182 
184  const EdgeDescriptor& operator*() const;
185 
187  const EdgeDescriptor* operator->() const;
188 
189  private:
191  VertexDescriptor source_;
193  ColIterator block_;
194  /***
195  * @brief The column iterator positioned at the end of the row
196  * of vertex source_
197  */
198  ColIterator blockEnd_;
200  EdgeDescriptor edge_;
201  };
202 
206  template<class C>
208  {
209  public:
217  typedef const typename remove_const<C>::type ConstContainer;
218 
221 
222  enum {
224  isMutable = is_same<C, MutableContainer>::value
225  };
226 
232  explicit VertexIteratorT(C* graph, const VertexDescriptor& current);
233 
241  explicit VertexIteratorT(const VertexDescriptor& current);
242 
244 
250 
252  bool operator!=(const VertexIteratorT<ConstContainer>& other) const;
253 
255  bool operator==(const VertexIteratorT<ConstContainer>& other) const;
256 
258  bool operator!=(const VertexIteratorT<MutableContainer>& other) const;
259 
261  bool operator==(const VertexIteratorT<MutableContainer>& other) const;
262 
263  typedef typename conditional<is_same<C, typename remove_const<C>::type>::value && C::mutableMatrix,
264  typename M::block_type, const typename M::block_type>::type
267  WeightType& weight() const;
268 
273  const VertexDescriptor& operator*() const;
274 
280  EdgeIteratorT<C> begin() const;
281 
287  EdgeIteratorT<C> end() const;
288 
289  private:
290  C* graph_;
291  VertexDescriptor current_;
292  };
293 
297  typedef EdgeIteratorT<const MatrixGraph<Matrix> > ConstEdgeIterator;
298 
302  typedef EdgeIteratorT<MatrixGraph<Matrix> > EdgeIterator;
303 
307  typedef VertexIteratorT<const MatrixGraph<Matrix> > ConstVertexIterator;
308 
312  typedef VertexIteratorT<MatrixGraph<Matrix> > VertexIterator;
313 
319 
323  ~MatrixGraph();
324 
330 
336 
341  ConstVertexIterator begin() const;
342 
347  ConstVertexIterator end() const;
348 
356 
363  EdgeIterator endEdges(const VertexDescriptor& source);
364 
365 
372  ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
373 
380  ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
381 
386  Matrix& matrix();
387 
392  const Matrix& matrix() const;
393 
397  std::size_t noVertices() const;
398 
405  VertexDescriptor maxVertex() const;
406 
410  std::size_t noEdges() const;
411 
419  const VertexDescriptor& target) const;
420 
421  private:
423  Matrix& matrix_;
425  EdgeDescriptor* start_;
427  MatrixGraph(const MatrixGraph&);
428 
429  };
430 
440  template<class G, class T>
441  class SubGraph
442  {
443  public:
447  typedef G Graph;
448 
453  typedef T Excluded;
454 
458  typedef typename Graph::VertexDescriptor VertexDescriptor;
459 
461 
469  {
470  public:
471  typedef ReadablePropertyMapTag Category;
472 
473  EdgeIndexMap(const EdgeDescriptor& firstEdge)
474  : firstEdge_(firstEdge)
475  {}
476 
479  : firstEdge_(emap.firstEdge_)
480  {}
481 
482  std::size_t operator[](const EdgeDescriptor& edge) const
483  {
484  return edge-firstEdge_;
485  }
486  private:
488  EdgeDescriptor firstEdge_;
490  EdgeIndexMap()
491  {}
492  };
493 
498  EdgeIndexMap getEdgeIndexMap();
499 
503  class EdgeIterator : public RandomAccessIteratorFacade<EdgeIterator,const EdgeDescriptor>
504  {
505  public:
511  explicit EdgeIterator(const VertexDescriptor& source, const EdgeDescriptor& edge);
512 
520  explicit EdgeIterator(const EdgeDescriptor& edge);
521 
523  bool equals(const EdgeIterator& other) const;
524 
527 
530 
531  EdgeIterator& advance(std::ptrdiff_t n);
532 
534  const EdgeDescriptor& dereference() const;
535 
537  const VertexDescriptor& target() const;
538 
540  const VertexDescriptor& source() const;
541 
542  std::ptrdiff_t distanceTo(const EdgeIterator& other) const;
543 
544  private:
546  VertexDescriptor source_;
551  EdgeDescriptor edge_;
552  };
553 
558  : public ForwardIteratorFacade<VertexIterator,const VertexDescriptor>
559  {
560  public:
567  explicit VertexIterator(const SubGraph<G,T>* graph, const VertexDescriptor& current,
568  const VertexDescriptor& end);
569 
570 
577  explicit VertexIterator(const VertexDescriptor& current);
578 
581 
583  bool equals(const VertexIterator& other) const;
584 
589  const VertexDescriptor& dereference() const;
590 
596  EdgeIterator begin() const;
597 
603  EdgeIterator end() const;
604 
605  private:
607  const SubGraph<Graph,T>* graph_;
609  VertexDescriptor current_;
611  VertexDescriptor end_;
612  };
613 
617  typedef EdgeIterator ConstEdgeIterator;
618 
622  typedef VertexIterator ConstVertexIterator;
623 
628  ConstVertexIterator begin() const;
629 
634  ConstVertexIterator end() const;
635 
642  ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
643 
650  ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
651 
655  std::size_t noVertices() const;
656 
663  VertexDescriptor maxVertex() const;
664 
668  std::size_t noEdges() const;
675  const EdgeDescriptor findEdge(const VertexDescriptor& source,
676  const VertexDescriptor& target) const;
684  SubGraph(const Graph& graph, const T& excluded);
685 
689  ~SubGraph();
690 
691  private:
693  const T& excluded_;
695  std::size_t noVertices_;
697  VertexDescriptor endVertex_;
699  int noEdges_;
704  VertexDescriptor maxVertex_;
706  VertexDescriptor* edges_;
708  std::ptrdiff_t* start_;
710  std::ptrdiff_t* end_;
712  SubGraph(const SubGraph&)
713  {}
714  };
715 
716 
720  template<class G, class VP, class VM=IdentityMap>
722  {
723  public:
727  typedef G Graph;
728 
732  typedef typename Graph::VertexDescriptor VertexDescriptor;
733 
737  typedef typename Graph::EdgeDescriptor EdgeDescriptor;
738 
742  typedef VP VertexProperties;
743 
755  typedef VM VertexMap;
756 
760  typedef typename Graph::EdgeIterator EdgeIterator;
761 
765  typedef typename Graph::ConstEdgeIterator ConstEdgeIterator;
766 
773 
779  EdgeIterator endEdges(const VertexDescriptor& source);
780 
786  ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
787 
793  ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
794 
795 
796  template<class C>
798  : public conditional<is_same<typename remove_const<C>::type,
799  C>::value,
800  typename Graph::VertexIterator,
801  typename Graph::ConstVertexIterator>::type
802  {
803  friend class VertexIteratorT<const typename remove_const<C>::type>;
804  friend class VertexIteratorT<typename remove_const<C>::type>;
805  public:
809  typedef typename conditional<is_same<typename remove_const<C>::type,
810  C>::value,
811  typename Graph::VertexIterator,
812  typename Graph::ConstVertexIterator>::type
814 
818  typedef typename conditional<is_same<typename remove_const<C>::type,
819  C>::value,
820  typename Graph::EdgeIterator,
821  typename Graph::ConstEdgeIterator>::type
823 
829  explicit VertexIteratorT(const Father& iter,
830  C* graph);
831 
832 
840  explicit VertexIteratorT(const Father& iter);
841 
846  template<class C1>
847  VertexIteratorT(const VertexIteratorT<C1>& other);
848 
852  typename conditional<is_same<C,typename remove_const<C>::type>::value,
853  VertexProperties&,
854  const VertexProperties&>::type
855  properties() const;
856 
862  EdgeIterator begin() const;
863 
869  EdgeIterator end() const;
870 
871  private:
875  C* graph_;
876  };
877 
881  typedef VertexIteratorT<VertexPropertiesGraph<Graph,
882  VertexProperties,VM> > VertexIterator;
883 
887  typedef VertexIteratorT<const VertexPropertiesGraph<Graph,
888  VertexProperties,VM> > ConstVertexIterator;
889 
895 
901 
906  ConstVertexIterator begin() const;
907 
912  ConstVertexIterator end() const;
913 
919  VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
920 
926  const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
927 
932  const Graph& graph() const;
933 
937  std::size_t noVertices() const;
938 
942  std::size_t noEdges() const;
943 
950  VertexDescriptor maxVertex() const;
951 
957  VertexPropertiesGraph(Graph& graph, const VertexMap vmap=VertexMap());
958 
959  private:
960  VertexPropertiesGraph(const VertexPropertiesGraph&)
961  {}
962 
964  Graph& graph_;
966  VertexMap vmap_;
968  std::vector<VertexProperties> vertexProperties_;
969 
970  };
971 
975  template<class G, class VP, class EP, class VM=IdentityMap, class EM=IdentityMap>
977  {
978  public:
982  typedef G Graph;
983 
987  typedef typename Graph::VertexDescriptor VertexDescriptor;
988 
992  typedef typename Graph::EdgeDescriptor EdgeDescriptor;
993 
997  typedef VP VertexProperties;
998 
1010  typedef VM VertexMap;
1011 
1015  typedef EP EdgeProperties;
1016 
1017 
1029  typedef EM EdgeMap;
1030 
1031  template<class C>
1033  : public conditional<is_same<typename remove_const<C>::type,
1034  C>::value,
1035  typename Graph::EdgeIterator,
1036  typename Graph::ConstEdgeIterator>::type
1037  {
1038 
1039  friend class EdgeIteratorT<const typename remove_const<C>::type>;
1040  friend class EdgeIteratorT<typename remove_const<C>::type>;
1041  public:
1045  typedef typename conditional<is_same<typename remove_const<C>::type,
1046  C>::value,
1047  typename Graph::EdgeIterator,
1048  typename Graph::ConstEdgeIterator>::type
1050 
1056  explicit EdgeIteratorT(const Father& iter,
1057  C* graph);
1058 
1066  explicit EdgeIteratorT(const Father& iter);
1067 
1072  template<class C1>
1073  EdgeIteratorT(const EdgeIteratorT<C1>& other);
1074 
1078  typename conditional<is_same<C,typename remove_const<C>::type>::value,
1079  EdgeProperties&,
1080  const EdgeProperties&>::type
1081  properties() const;
1082 
1083  private:
1087  C* graph_;
1088  };
1089 
1093  typedef EdgeIteratorT<PropertiesGraph<Graph,
1094  VertexProperties,
1095  EdgeProperties,VM,EM> > EdgeIterator;
1096 
1100  typedef EdgeIteratorT<const PropertiesGraph<Graph,
1101  VertexProperties,
1102  EdgeProperties,VM,EM> > ConstEdgeIterator;
1103 
1109  EdgeIterator beginEdges(const VertexDescriptor& source);
1110 
1116  EdgeIterator endEdges(const VertexDescriptor& source);
1117 
1123  ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
1124 
1130  ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
1131 
1132 
1133  template<class C>
1135  : public conditional<is_same<typename remove_const<C>::type,
1136  C>::value,
1137  typename Graph::VertexIterator,
1138  typename Graph::ConstVertexIterator>::type
1139  {
1140  friend class VertexIteratorT<const typename remove_const<C>::type>;
1141  friend class VertexIteratorT<typename remove_const<C>::type>;
1142  public:
1146  typedef typename conditional<is_same<typename remove_const<C>::type,
1147  C>::value,
1148  typename Graph::VertexIterator,
1149  typename Graph::ConstVertexIterator>::type
1151 
1157  explicit VertexIteratorT(const Father& iter,
1158  C* graph);
1159 
1160 
1168  explicit VertexIteratorT(const Father& iter);
1169 
1174  template<class C1>
1175  VertexIteratorT(const VertexIteratorT<C1>& other);
1176 
1180  typename conditional<is_same<C,typename remove_const<C>::type>::value,
1181  VertexProperties&,
1182  const VertexProperties&>::type
1183  properties() const;
1184 
1190  EdgeIteratorT<C> begin() const;
1191 
1197  EdgeIteratorT<C> end() const;
1198 
1199  private:
1203  C* graph_;
1204  };
1205 
1209  typedef VertexIteratorT<PropertiesGraph<Graph,
1210  VertexProperties,
1211  EdgeProperties,VM,EM> > VertexIterator;
1212 
1216  typedef VertexIteratorT<const PropertiesGraph<Graph,
1217  VertexProperties,
1218  EdgeProperties,VM,EM> > ConstVertexIterator;
1219 
1225 
1230  VertexIterator end();
1231 
1236  ConstVertexIterator begin() const;
1237 
1242  ConstVertexIterator end() const;
1243 
1249  VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
1250 
1256  const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
1257 
1264  EdgeDescriptor findEdge(const VertexDescriptor& source,
1265  const VertexDescriptor& target)
1266  {
1267  return graph_.findEdge(source,target);
1268  }
1269 
1275  EdgeProperties& getEdgeProperties(const EdgeDescriptor& edge);
1276 
1277 
1283  const EdgeProperties& getEdgeProperties(const EdgeDescriptor& edge) const;
1284 
1291  EdgeProperties& getEdgeProperties(const VertexDescriptor& source,
1292  const VertexDescriptor& target);
1293 
1300  const EdgeProperties& getEdgeProperties(const VertexDescriptor& source,
1301  const VertexDescriptor& target) const;
1302 
1307  const Graph& graph() const;
1308 
1312  std::size_t noVertices() const;
1313 
1317  std::size_t noEdges() const;
1318 
1325  VertexDescriptor maxVertex() const;
1326 
1333  PropertiesGraph(Graph& graph, const VertexMap& vmap=VertexMap(),
1334  const EdgeMap& emap=EdgeMap());
1335 
1336  private:
1338  {}
1339 
1341  Graph& graph_;
1344  VertexMap vmap_;
1345  std::vector<VertexProperties> vertexProperties_;
1347  EdgeMap emap_;
1349  std::vector<EdgeProperties> edgeProperties_;
1350 
1351  };
1352 
1353 
1358  template<typename G>
1360  {
1361  public:
1365  typedef G Graph;
1369  typedef typename G::VertexProperties VertexProperties;
1373  typedef typename G::VertexDescriptor Vertex;
1374 
1380  : graph_(g)
1381  {}
1386  : graph_(0)
1387  {}
1388 
1389 
1394  VertexProperties& operator[](const Vertex& vertex) const
1395  {
1396  return graph_->getVertexProperties(vertex);
1397  }
1398  private:
1399  Graph* graph_;
1400  };
1401 
1406  template<typename G>
1408  {
1409  public:
1413  typedef G Graph;
1417  typedef typename G::EdgeProperties EdgeProperties;
1421  typedef typename G::EdgeDescriptor Edge;
1422 
1428  : graph_(g)
1429  {}
1434  : graph_(0)
1435  {}
1436 
1441  EdgeProperties& operator[](const Edge& edge) const
1442  {
1443  return graph_->getEdgeProperties(edge);
1444  }
1445  private:
1446  Graph* graph_;
1447  };
1448 
1449 
1460  template<class G, class V>
1461  int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex,
1462  V& visitor);
1463 
1464 #ifndef DOXYGEN
1465 
1466  template<class M>
1467  MatrixGraph<M>::MatrixGraph(M& matrix)
1468  : matrix_(matrix)
1469  {
1470  if(matrix_.N()!=matrix_.M())
1471  DUNE_THROW(ISTLError, "Matrix has to have as many columns as rows!");
1472 
1473  start_ = new EdgeDescriptor[matrix_.N()+1];
1474 
1475  typedef typename M::ConstIterator Iterator;
1476  Iterator row = matrix_.begin();
1477  start_[row.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>
1485  {
1486  delete[] start_;
1487  }
1488 
1489  template<class M>
1490  inline std::size_t MatrixGraph<M>::noEdges() const
1491  {
1492  return start_[matrix_.N()];
1493  }
1494 
1495  template<class M>
1496  inline std::size_t MatrixGraph<M>::noVertices() const
1497  {
1498  return matrix_.N();
1499  }
1500 
1501  template<class M>
1502  inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::maxVertex() const
1503  {
1504  return matrix_.N()-1;
1505  }
1506 
1507  template<class M>
1508  typename MatrixGraph<M>::EdgeDescriptor
1509  MatrixGraph<M>::findEdge(const VertexDescriptor& source,
1510  const VertexDescriptor& target) const
1511  {
1512  typename M::ConstColIterator found =matrix_[source].find(target);
1513  if(found == matrix_[source].end())
1514  return std::numeric_limits<EdgeDescriptor>::max();
1515  std::size_t offset = found.offset();
1516  if(target>source)
1517  offset--;
1518 
1519  assert(offset<noEdges());
1520 
1521  return start_[source]+offset;
1522  }
1523 
1524 
1525  template<class M>
1526  inline M& MatrixGraph<M>::matrix()
1527  {
1528  return matrix_;
1529  }
1530 
1531  template<class M>
1532  inline const M& MatrixGraph<M>::matrix() const
1533  {
1534  return matrix_;
1535  }
1536 
1537  template<class M>
1538  template<class C>
1539  MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block,
1540  const ColIterator& end, const EdgeDescriptor& edge)
1541  : source_(source), block_(block), blockEnd_(end), edge_(edge)
1542  {
1543  if(block_!=blockEnd_ && block_.index() == source_) {
1544  // This is the edge from the diagonal to the diagonal. Skip it.
1545  ++block_;
1546  }
1547  }
1548 
1549  template<class M>
1550  template<class C>
1551  MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const ColIterator& block)
1552  : block_(block)
1553  {}
1554 
1555  template<class M>
1556  template<class C>
1557  template<class C1>
1558  MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const EdgeIteratorT<C1>& other)
1559  : source_(other.source_), block_(other.block_), blockEnd_(other.blockEnd_), edge_(other.edge_)
1560  {}
1561 
1562 
1563  template<class M>
1564  template<class C>
1565  inline typename MatrixGraph<M>::template EdgeIteratorT<C>::WeightType&
1566  MatrixGraph<M>::EdgeIteratorT<C>::weight() const
1567  {
1568  return *block_;
1569  }
1570 
1571  template<class M>
1572  template<class C>
1573  inline typename MatrixGraph<M>::template EdgeIteratorT<C>& MatrixGraph<M>::EdgeIteratorT<C>::operator++()
1574  {
1575  ++block_;
1576  ++edge_;
1577 
1578  if(block_!=blockEnd_ && block_.index() == source_) {
1579  // This is the edge from the diagonal to the diagonal. Skip it.
1580  ++block_;
1581  }
1582 
1583  return *this;
1584  }
1585 
1586  template<class M>
1587  template<class C>
1588  inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(const typename MatrixGraph<M>::template EdgeIteratorT<typename 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 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 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 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>
1719  {
1720  return graph_->beginEdges(current_);
1721  }
1722 
1723  template<class M>
1724  template<class C>
1725  inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1727  {
1728  return graph_->endEdges(current_);
1729  }
1730 
1731  template<class M>
1732  inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1734  {
1735  return VertexIterator(this,0);
1736  }
1737 
1738  template<class M>
1739  inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
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 const typename SubGraph<G,T>::EdgeDescriptor SubGraph<G,T>::findEdge(const VertexDescriptor& source,
1964  const VertexDescriptor& target) const
1965  {
1966  const EdgeDescriptor edge = std::lower_bound(edges_+start_[source], edges_+end_[source], target);
1967  if(edge==edges_+end_[source] || *edge!=target)
1968  return std::numeric_limits<EdgeDescriptor>::max();
1969 
1970  return edge;
1971  }
1972 
1973  template<class G, class T>
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  typedef typename Graph::ConstVertexIterator Iterator;
1992  Iterator endVertex=graph.end();
1993 
1994  for(Iterator vertex = graph.begin(); vertex != endVertex; ++vertex)
1995  if(excluded_[*vertex])
1996  start_[*vertex]=end_[*vertex]=-1;
1997  else{
1998  ++noVertices_;
1999  endVertex_ = std::max(*vertex, endVertex_);
2000 
2001  start_[*vertex] = edge-edges_;
2002 
2003  typedef typename Graph::ConstEdgeIterator Iterator;
2004  Iterator endEdge = vertex.end();
2005 
2006  for(Iterator iter=vertex.begin(); iter!= endEdge; ++iter)
2007  if(!excluded[iter.target()]) {
2008  *edge = iter.target();
2009  ++edge;
2010  }
2011 
2012  end_[*vertex] = edge - edges_;
2013 
2014  // Sort the edges
2015  std::sort(edges_+start_[*vertex], edge);
2016  }
2017  noEdges_ = edge-edges_;
2018  ++endVertex_;
2019  }
2020 
2021  template<class G, class V, class VM>
2022  inline std::size_t VertexPropertiesGraph<G,V,VM>::noEdges() const
2023  {
2024  return graph_.noEdges();
2025  }
2026 
2027  template<class G, class V, class VM>
2028  inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2029  VertexPropertiesGraph<G,V,VM>::beginEdges(const VertexDescriptor& source)
2030  {
2031  return graph_.beginEdges(source);
2032  }
2033 
2034  template<class G, class V, class VM>
2035  inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2036  VertexPropertiesGraph<G,V,VM>::endEdges(const VertexDescriptor& source)
2037  {
2038  return graph_.endEdges(source);
2039  }
2040 
2041  template<class G, class V, class VM>
2042  typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2043  inline VertexPropertiesGraph<G,V,VM>::beginEdges(const VertexDescriptor& source) const
2044  {
2045  return graph_.beginEdges(source);
2046  }
2047 
2048  template<class G, class V, class VM>
2049  typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2050  VertexPropertiesGraph<G,V,VM>::endEdges(const VertexDescriptor& source) const
2051  {
2052  return graph_.endEdges(source);
2053  }
2054 
2055  template<class G, class V, class VM>
2056  template<class C>
2057  VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2058  ::VertexIteratorT(const Father& iter,
2059  C* graph)
2060  : Father(iter), graph_(graph)
2061  {}
2062 
2063  template<class G, class V, class VM>
2064  template<class C>
2065  VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2066  ::VertexIteratorT(const Father& iter)
2067  : Father(iter)
2068  {}
2069 
2070  template<class G, class V, class VM>
2071  template<class C>
2072  template<class C1>
2073  VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2074  ::VertexIteratorT(const VertexIteratorT<C1>& other)
2075  : Father(other), graph_(other.graph_)
2076  {}
2077 
2078  template<class G, class V, class VM>
2079  template<class C>
2081  V&, const V&>::type
2082  inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::properties() const
2083  {
2084  return graph_->getVertexProperties(Father::operator*());
2085  }
2086 
2087  template<class G, class V, class VM>
2088  template<class C>
2090  C>::value,
2091  typename G::EdgeIterator,
2092  typename G::ConstEdgeIterator>::type
2094  {
2095  return graph_->beginEdges(Father::operator*());
2096  }
2097 
2098  template<class G, class V, class VM>
2099  template<class C>
2101  C>::value,
2102  typename G::EdgeIterator,
2103  typename G::ConstEdgeIterator>::type
2105  {
2106  return graph_->endEdges(Father::operator*());
2107  }
2108 
2109  template<class G, class V, class VM>
2110  inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::begin()
2111  {
2112  return VertexIterator(graph_.begin(), this);
2113  }
2114 
2115  template<class G, class V, class VM>
2116  inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::end()
2117  {
2118  return VertexIterator(graph_.end());
2119  }
2120 
2121 
2122  template<class G, class V, class VM>
2123  inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::begin() const
2124  {
2125  return ConstVertexIterator(graph_.begin(), this);
2126  }
2127 
2128  template<class G, class V, class VM>
2129  inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::end() const
2130  {
2131  return ConstVertexIterator(graph_.end());
2132  }
2133 
2134  template<class G, class V, class VM>
2135  inline V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(const VertexDescriptor& vertex)
2136  {
2137  return vertexProperties_[vmap_[vertex]];
2138  }
2139 
2140  template<class G, class V, class VM>
2141  inline const V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(const VertexDescriptor& vertex) const
2142  {
2143  return vertexProperties_[vmap_[vertex]];
2144  }
2145 
2146  template<class G, class V, class VM>
2147  inline const G& VertexPropertiesGraph<G,V,VM>::graph() const
2148  {
2149  return graph_;
2150  }
2151 
2152  template<class G, class V, class VM>
2153  inline std::size_t VertexPropertiesGraph<G,V,VM>::noVertices() const
2154  {
2155  return graph_.noVertices();
2156  }
2157 
2158 
2159  template<class G, class V, class VM>
2160  inline typename VertexPropertiesGraph<G,V,VM>::VertexDescriptor VertexPropertiesGraph<G,V,VM>::maxVertex() const
2161  {
2162  return graph_.maxVertex();
2163  }
2164 
2165  template<class G, class V, class VM>
2166  VertexPropertiesGraph<G,V,VM>::VertexPropertiesGraph(Graph& graph, const VM vmap)
2167  : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V())
2168  {}
2169 
2170  template<class G, class V, class E, class VM, class EM>
2171  template<class C>
2172  PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const Father& iter,
2173  C* graph)
2174  : Father(iter), graph_(graph)
2175  {}
2176 
2177  template<class G, class V, class E, class VM, class EM>
2178  template<class C>
2179  PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const Father& iter)
2180  : Father(iter)
2181  {}
2182 
2183  template<class G, class V, class E, class VM, class EM>
2184  template<class C>
2185  template<class C1>
2186  PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const EdgeIteratorT<C1>& other)
2187  : Father(other), graph_(other.graph_)
2188  {}
2189 
2190 
2191  template<class G, class V, class E, class VM, class EM>
2192  inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noEdges() const
2193  {
2194  return graph_.noEdges();
2195  }
2196 
2197  template<class G, class V, class E, class VM, class EM>
2198  template<class C>
2199  inline typename conditional<is_same<C,typename remove_const<C>::type>::value,E&,const E&>::type
2200  PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::properties() const
2201  {
2202  return graph_->getEdgeProperties(Father::operator*());
2203  }
2204 
2205  template<class G, class V, class E, class VM, class EM>
2206  inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2207  PropertiesGraph<G,V,E,VM,EM>::beginEdges(const VertexDescriptor& source)
2208  {
2209  return EdgeIterator(graph_.beginEdges(source), this);
2210  }
2211 
2212  template<class G, class V, class E, class VM, class EM>
2213  inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2214  PropertiesGraph<G,V,E,VM,EM>::endEdges(const VertexDescriptor& source)
2215  {
2216  return EdgeIterator(graph_.endEdges(source));
2217  }
2218 
2219  template<class G, class V, class E, class VM, class EM>
2220  typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2221  inline PropertiesGraph<G,V,E,VM,EM>::beginEdges(const VertexDescriptor& source) const
2222  {
2223  return ConstEdgeIterator(graph_.beginEdges(source), this);
2224  }
2225 
2226  template<class G, class V, class E, class VM, class EM>
2227  typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2228  PropertiesGraph<G,V,E,VM,EM>::endEdges(const VertexDescriptor& source) const
2229  {
2230  return ConstEdgeIterator(graph_.endEdges(source));
2231  }
2232 
2233  template<class G, class V, class E, class VM, class EM>
2234  template<class C>
2235  PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2236  ::VertexIteratorT(const Father& iter,
2237  C* graph)
2238  : Father(iter), graph_(graph)
2239  {}
2240 
2241  template<class G, class V, class E, class VM, class EM>
2242  template<class C>
2243  PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2244  ::VertexIteratorT(const Father& iter)
2245  : Father(iter)
2246  {}
2247 
2248  template<class G, class V, class E, class VM, class EM>
2249  template<class C>
2250  template<class C1>
2251  PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2252  ::VertexIteratorT(const VertexIteratorT<C1>& other)
2253  : Father(other), graph_(other.graph_)
2254  {}
2255 
2256  template<class G, class V, class E, class VM, class EM>
2257  template<class C>
2259  V&, const V&>::type
2260  PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::properties() const
2261  {
2262  return graph_->getVertexProperties(Father::operator*());
2263  }
2264 
2265  template<class G, class V, class E, class VM, class EM>
2266  template<class C>
2267  inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2269  {
2270  return graph_->beginEdges(Father::operator*());
2271  }
2272 
2273  template<class G, class V, class E, class VM, class EM>
2274  template<class C>
2275  inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2277  {
2278  return graph_->endEdges(Father::operator*());
2279  }
2280 
2281  template<class G, class V, class E, class VM, class EM>
2282  inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::begin()
2283  {
2284  return VertexIterator(graph_.begin(), this);
2285  }
2286 
2287  template<class G, class V, class E, class VM, class EM>
2288  inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::end()
2289  {
2290  return VertexIterator(graph_.end());
2291  }
2292 
2293 
2294  template<class G, class V, class E, class VM, class EM>
2295  inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::begin() const
2296  {
2297  return ConstVertexIterator(graph_.begin(), this);
2298  }
2299 
2300  template<class G, class V, class E, class VM, class EM>
2301  inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::end() const
2302  {
2303  return ConstVertexIterator(graph_.end());
2304  }
2305 
2306  template<class G, class V, class E, class VM, class EM>
2307  inline V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(const VertexDescriptor& vertex)
2308  {
2309  return vertexProperties_[vmap_[vertex]];
2310  }
2311 
2312  template<class G, class V, class E, class VM, class EM>
2313  inline const V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(const VertexDescriptor& vertex) const
2314  {
2315  return vertexProperties_[vmap_[vertex]];
2316  }
2317 
2318  template<class G, class V, class E, class VM, class EM>
2319  inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const EdgeDescriptor& edge)
2320  {
2321  return edgeProperties_[emap_[edge]];
2322  }
2323 
2324  template<class G, class V, class E, class VM, class EM>
2325  inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const EdgeDescriptor& edge) const
2326  {
2327  return edgeProperties_[emap_[edge]];
2328  }
2329 
2330  template<class G, class V, class E, class VM, class EM>
2331  inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const VertexDescriptor& source,
2332  const VertexDescriptor& target)
2333  {
2334  return getEdgeProperties(graph_.findEdge(source,target));
2335  }
2336 
2337  template<class G, class V, class E, class VM, class EM>
2338  inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const VertexDescriptor& source,
2339  const VertexDescriptor& target) const
2340  {
2341  return getEdgeProperties(graph_.findEdge(source,target));
2342  }
2343 
2344  template<class G, class V, class E, class VM, class EM>
2345  inline const G& PropertiesGraph<G,V,E,VM,EM>::graph() const
2346  {
2347  return graph_;
2348  }
2349 
2350  template<class G, class V, class E, class VM, class EM>
2351  inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noVertices() const
2352  {
2353  return graph_.noVertices();
2354  }
2355 
2356 
2357  template<class G, class V, class E, class VM, class EM>
2358  inline typename PropertiesGraph<G,V,E,VM,EM>::VertexDescriptor PropertiesGraph<G,V,E,VM,EM>::maxVertex() const
2359  {
2360  return graph_.maxVertex();
2361  }
2362 
2363  template<class G, class V, class E, class VM, class EM>
2364  PropertiesGraph<G,V,E,VM,EM>::PropertiesGraph(Graph& graph, const VM& vmap, const EM& emap)
2365  : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V()),
2366  emap_(emap), edgeProperties_(graph_.noEdges(), E())
2367  {}
2368 
2369  template<class G, class V>
2370  inline int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex,
2371  V& visitor)
2372  {
2373  typedef typename G::ConstEdgeIterator iterator;
2374  const iterator end = graph.endEdges(vertex);
2375  int noNeighbours=0;
2376  for(iterator edge = graph.beginEdges(vertex); edge != end; ++edge, ++noNeighbours)
2377  visitor(edge);
2378  return noNeighbours;
2379  }
2380 
2381 #endif // DOXYGEN
2382 
2384  }
2385 }
2386 #endif
EdgeProperties & getEdgeProperties(const EdgeDescriptor &edge)
Get the properties associated with a edge.
const EdgeDescriptor * operator->() const
Get the edge descriptor.
conditional< is_same< typename remove_const< C >::type, C >::value, typename Graph::VertexIterator, typename Graph::ConstVertexIterator >::type Father
The father class.
Definition: graph.hh:1150
The vertex iterator of the graph.
Definition: graph.hh:557
whether C is mutable.
Definition: graph.hh:224
G Graph
The type of the graph we are a sub graph for.
Definition: graph.hh:447
bool operator==(const EdgeIteratorT< typename remove_const< C >::type > &other) const
Equality operator.
int visitNeighbours(const G &graph, const typename G::VertexDescriptor &vertex, V &visitor)
Visit all neighbour vertices of a vertex in a graph.
Attaches properties to the vertices of a graph.
Definition: graph.hh:721
M::size_type VertexDescriptor
The vertex descriptor.
Definition: graph.hh:72
conditional< isMutable &&C::mutableMatrix, typename M::block_type, const typename M::block_type >::type Weight
The matrix block type we use as weights.
Definition: graph.hh:126
Iterator over all edges starting from a vertex.
Definition: graph.hh:93
const remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:217
EdgeIndexMap(const EdgeDescriptor &firstEdge)
Definition: graph.hh:473
VertexIterator begin()
Get an iterator over the vertices.
~SubGraph()
Destructor.
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:997
WeightType & weight() const
Access the edge weight.
EdgeIteratorT< C > end() const
Get an iterator over all edges starting at the current vertex.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
VertexIteratorT< MatrixGraph< Matrix > > VertexIterator
The mutable vertex iterator type.
Definition: graph.hh:312
Wrapper to access the internal vertex properties of a graph via operator[]()
Definition: graph.hh:1407
conditional< is_same< C, typename remove_const< C >::type >::value, VertexProperties &, const VertexProperties & >::type properties() const
Get the properties of the current Vertex.
EdgeIterator & decrement()
Preincrement operator.
The vertex iterator type of the graph.
Definition: graph.hh:207
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:992
Attaches properties to the edges and vertices of a graph.
Definition: graph.hh:976
PropertiesGraph(Graph &graph, const VertexMap &vmap=VertexMap(), const EdgeMap &emap=EdgeMap())
Constructor.
EdgeDescriptor findEdge(const VertexDescriptor &source, const VertexDescriptor &target) const
Find the descriptor of an edge.
std::size_t noEdges() const
Get the number of edges in the graph.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:987
whether C is mutable.
Definition: graph.hh:111
ConstEdgeIterator beginEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
G::EdgeProperties EdgeProperties
The type of the vertex properties.
Definition: graph.hh:1417
EdgeIteratorT(const VertexDescriptor &source, const ColIterator &block, const ColIterator &end, const EdgeDescriptor &edge)
Constructor.
VertexIterator & increment()
Preincrement operator.
VertexDescriptor source() const
The index of the source vertex of the current edge.
bool operator==(const VertexIteratorT< ConstContainer > &other) const
Equality operator.
remove_const< C >::type MutableContainer
The mutable type of the container type.
Definition: graph.hh:213
G Graph
The graph we attach properties to.
Definition: graph.hh:727
The (undirected) graph of a matrix.
Definition: graph.hh:49
SubGraph(const Graph &graph, const T &excluded)
Constructor.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:458
remove_const< C >::type MutableContainer
The mutable type of the container type.
Definition: graph.hh:100
std::ptrdiff_t distanceTo(const EdgeIterator &other) const
VertexProperties & getVertexProperties(const VertexDescriptor &vertex)
Get the properties associated with a vertex.
VertexDescriptor * EdgeDescriptor
Definition: graph.hh:460
std::size_t noEdges() const
Get the number of edges in the graph.
G::EdgeDescriptor Edge
The edge descriptor.
Definition: graph.hh:1421
Graph::ConstEdgeIterator ConstEdgeIterator
The type of the constant edge iterator.
Definition: graph.hh:765
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1365
EdgeIteratorT< C > begin() const
Get an iterator over all edges starting at the current vertex.
ReadablePropertyMapTag Category
Definition: graph.hh:471
GraphVertexPropertiesSelector()
Default constructor.
Definition: graph.hh:1385
bool equals(const VertexIterator &other) const
Equality iterator.
std::size_t noVertices() const
Get the number of vertices in the graph.
EM EdgeMap
The type of the map for converting the EdgeDescriptor to std::size_t.
Definition: graph.hh:1029
A subgraph of a graph.
Definition: graph.hh:441
VertexIterator end()
Get an iterator over the vertices.
EdgeIterator endEdges(const VertexDescriptor &source)
Get an iterator over the edges starting at a vertex.
std::ptrdiff_t EdgeDescriptor
The edge descriptor.
Definition: graph.hh:79
conditional< is_same< typename remove_const< C >::type, C >::value, typename Graph::EdgeIterator, typename Graph::ConstEdgeIterator >::type EdgeIterator
The class of the edge iterator.
Definition: graph.hh:822
EdgeIteratorT< C > & operator++()
preincrement operator.
GraphEdgePropertiesSelector()
Default constructor.
Definition: graph.hh:1433
EdgeIterator ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:617
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1413
const VertexDescriptor & source() const
The index of the source vertex of the current edge.
EdgeIterator beginEdges(const VertexDescriptor &source)
Get an iterator over the edges starting at a vertex.
EdgeIterator(const VertexDescriptor &source, const EdgeDescriptor &edge)
Constructor.
std::size_t noEdges() const
Get the number of edges in the graph.
VertexIterator end()
Get an iterator over the vertices.
VertexProperties & operator[](const Vertex &vertex) const
Get the properties associated to a vertex.
Definition: graph.hh:1394
The edge iterator of the graph.
Definition: graph.hh:503
VertexIterator begin()
Get an iterator over the vertices.
conditional< is_same< C, typename remove_const< C >::type >::value &&C::mutableMatrix, typename M::block_type, const typename M::block_type >::type WeightType
Definition: graph.hh:155
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:755
const VertexDescriptor & operator*() const
Get the descriptor of the current vertex.
remove_const< M >::type MutableMatrix
The mutable type of the matrix we are a graph for.
Definition: graph.hh:60
ConstVertexIterator end() const
Get an iterator over the vertices.
conditional< is_same< typename remove_const< C >::type, C >::value, typename Graph::VertexIterator, typename Graph::ConstVertexIterator >::type Father
The father class.
Definition: graph.hh:813
EdgeIterator & increment()
Preincrement operator.
EdgeIterator endEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
Class representing the properties of an ede in the matrix graph.
Definition: dependency.hh:38
const EdgeDescriptor & dereference() const
The descriptor of the current edge.
EdgeIterator end() const
Get an iterator over all edges starting at the current vertex.
G::VertexProperties VertexProperties
The type of the vertex properties.
Definition: graph.hh:1369
MatrixGraph(Matrix &matrix)
Constructor.
EdgeIterator begin() const
Get an iterator over the edges starting from the current vertex.
VertexIterator begin()
Get an iterator over the vertices.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:732
VertexDescriptor target() const
The index of the target vertex of the current edge.
const EdgeDescriptor & operator*() const
Get the edge descriptor.
G Graph
The graph we attach properties to.
Definition: graph.hh:982
MM_TYPE type
Definition: matrixmarket.hh:267
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
const 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:65
VertexIterator end()
Get an iterator over the vertices.
conditional< is_same< C, typename remove_const< C >::type >::value &&C::mutableMatrix, typename M::block_type, const typename M::block_type >::type WeightType
Definition: graph.hh:265
Row row
Definition: matrixmatrix.hh:345
const VertexDescriptor & dereference() const
Get the descriptor of the current vertex.
EP EdgeProperties
The type of the properties of the edges;.
Definition: graph.hh:1015
An index map for mapping the edges to indices.
Definition: graph.hh:468
Matrix & matrix()
Get the underlying matrix.
EdgeIterator endEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
VertexPropertiesGraph(Graph &graph, const VertexMap vmap=VertexMap())
Constructor.
conditional< isMutable &&C::mutableMatrix, typename Matrix::row_type::Iterator, typename Matrix::row_type::ConstIterator >::type ColIterator
The column iterator of the matrix we use.
Definition: graph.hh:119
const remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:104
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
G::VertexDescriptor Vertex
The vertex descriptor.
Definition: graph.hh:1373
EdgeIterator end() const
Get an iterator over the edges starting from the current vertex.
GraphEdgePropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1427
Graph::EdgeIterator EdgeIterator
The type of the mutable edge iterator.
Definition: graph.hh:760
derive error class from the base class in common
Definition: istlexception.hh:16
EdgeIterator beginEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
const VertexDescriptor & target() const
The index of the target vertex of the current edge.
VertexIterator ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:622
VertexIterator(const SubGraph< G, T > *graph, const VertexDescriptor &current, const VertexDescriptor &end)
Constructor.
M Matrix
The type of the matrix we are a graph for.
Definition: graph.hh:55
ConstEdgeIterator endEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
VertexIteratorT< const MatrixGraph< Matrix > > ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:307
GraphVertexPropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1379
EdgeIndexMap getEdgeIndexMap()
Get an edge index map for the graph.
bool equals(const EdgeIterator &other) const
Equality operator.
conditional< is_same< typename remove_const< C >::type, C >::value, typename Graph::EdgeIterator, typename Graph::ConstEdgeIterator >::type Father
The father class.
Definition: graph.hh:1049
const Graph & graph() const
Get the graph the properties are attached to.
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:1010
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:737
EdgeProperties & operator[](const Edge &edge) const
Get the properties associated to a vertex.
Definition: graph.hh:1441
EdgeIterator beginEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
const Graph & graph() const
Get the graph the properties are attached to.
std::size_t noVertices() const
Get the number of vertices in the graph.
EdgeIteratorT< MatrixGraph< Matrix > > EdgeIterator
The mutable edge iterator type.
Definition: graph.hh:302
std::size_t noEdges() const
Get the number of edges in the graph.
EdgeIndexMap(const EdgeIndexMap &emap)
Protect copy construction.
Definition: graph.hh:478
std::size_t noVertices() const
Get the number of vertices in the graph.
EdgeIteratorT< const MatrixGraph< Matrix > > ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:297
EdgeIterator & advance(std::ptrdiff_t n)
VertexProperties & getVertexProperties(const VertexDescriptor &vertex)
Get the properties associated with a vertex.
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:742
~MatrixGraph()
Destructor.
VertexIteratorT(C *graph, const VertexDescriptor &current)
Constructor.
bool operator!=(const EdgeIteratorT< typename remove_const< C >::type > &other) const
Inequality operator.
std::size_t operator[](const EdgeDescriptor &edge) const
Definition: graph.hh:482
T Excluded
Random access container providing information about which vertices are excluded.
Definition: graph.hh:453
bool operator!=(const VertexIteratorT< ConstContainer > &other) const
Inequality operator.
ConstVertexIterator begin() const
Get an iterator over the vertices.
std::size_t noVertices() const
Get the number of vertices in the graph.
EdgeIterator begin() const
Get an iterator over all edges starting at the current vertex.
Wrapper to access the internal edge properties of a graph via operator[]()
Definition: graph.hh:1359
VertexIteratorT< C > & operator++()
Move to the next vertex.
WeightType & weight() const
Access the weight of the vertex.