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