dune-istl  2.2.1
graph.hh
Go to the documentation of this file.
1 // $Id: graph.hh 1870 2013-02-26 11:20:08Z mblatt $
2 #ifndef DUNE_AMG_GRAPH_HH
3 #define DUNE_AMG_GRAPH_HH
4 
5 #include<cstddef>
6 #include<algorithm>
7 #include<vector>
8 #include<cassert>
9 #include<limits>
10 #include<dune/common/typetraits.hh>
11 #include<dune/common/iteratorfacades.hh>
13 #include<dune/common/propertymap.hh>
14 
15 namespace Dune
16 {
17  namespace Amg
18  {
46  template<class M>
48  {
49  public:
53  typedef M Matrix;
54 
58  typedef typename M::block_type Weight;
59 
65  typedef typename M::size_type VertexDescriptor;
66 
72  typedef std::ptrdiff_t EdgeDescriptor;
73 
74  enum{
75  /*
76  * @brief Whether Matrix is mutable.
77  */
79  };
80 
81 
85  template<class C>
87  {
88 
89  public:
97  typedef const typename remove_const<C>::type ConstContainer;
98 
101 
102  enum{
104  isMutable = is_same<C, MutableContainer>::value
105  };
106 
110  typedef typename SelectType<isMutable && C::mutableMatrix,typename Matrix::row_type::Iterator,
111  typename Matrix::row_type::ConstIterator>::Type
113 
117  typedef typename SelectType<isMutable && C::mutableMatrix,typename M::block_type,
118  const typename M::block_type>::Type
120 
128  EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block,
129  const ColIterator& end, const EdgeDescriptor& edge);
130 
137  EdgeIteratorT(const ColIterator& block);
138 
143  template<class C1>
144  EdgeIteratorT(const EdgeIteratorT<C1>& other);
145 
147  typename M::block_type, const typename M::block_type>::Type
149 
153  WeightType& weight() const;
154 
157 
159  bool operator!=(const EdgeIteratorT<typename remove_const<C>::type>& other) const;
160 
162  bool operator!=(const EdgeIteratorT<const typename remove_const<C>::type>& other) const;
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  VertexDescriptor target() const;
172 
174  VertexDescriptor source() const;
175 
177  const EdgeDescriptor& operator*() const;
178 
180  const EdgeDescriptor* operator->() const;
181 
182  private:
184  VertexDescriptor source_;
186  ColIterator block_;
187  /***
188  * @brief The column iterator positioned at the end of the row
189  * of vertex source_
190  */
191  ColIterator blockEnd_;
193  EdgeDescriptor edge_;
194  };
195 
199  template<class C>
201  {
202  public:
210  typedef const typename remove_const<C>::type ConstContainer;
211 
214 
215  enum{
217  isMutable = is_same<C, MutableContainer>::value
218  };
219 
225  explicit VertexIteratorT(C* graph, const VertexDescriptor& current);
226 
234  explicit VertexIteratorT(const VertexDescriptor& current);
235 
237 
243 
245  bool operator!=(const VertexIteratorT<ConstContainer>& other) const;
246 
248  bool operator==(const VertexIteratorT<ConstContainer>& other) const;
249 
251  bool operator!=(const VertexIteratorT<MutableContainer>& other) const;
252 
254  bool operator==(const VertexIteratorT<MutableContainer>& other) const;
255 
257  typename M::block_type, const typename M::block_type>::Type
260  WeightType& weight() const;
261 
266  const VertexDescriptor& operator*() const;
267 
273  EdgeIteratorT<C> begin() const;
274 
280  EdgeIteratorT<C> end() const;
281 
282  private:
283  C* graph_;
284  VertexDescriptor current_;
285  };
286 
290  typedef EdgeIteratorT<const MatrixGraph<Matrix> > ConstEdgeIterator;
291 
295  typedef EdgeIteratorT<MatrixGraph<Matrix> > EdgeIterator;
296 
300  typedef VertexIteratorT<const MatrixGraph<Matrix> > ConstVertexIterator;
301 
305  typedef VertexIteratorT<MatrixGraph<Matrix> > VertexIterator;
306 
312 
316  ~MatrixGraph();
317 
323 
329 
334  ConstVertexIterator begin() const;
335 
340  ConstVertexIterator end() const;
341 
349 
356  EdgeIterator endEdges(const VertexDescriptor& source);
357 
358 
365  ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
366 
373  ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
374 
379  Matrix& matrix();
380 
385  const Matrix& matrix() const;
386 
390  std::size_t noVertices() const;
391 
398  VertexDescriptor maxVertex() const;
399 
403  std::size_t noEdges() const;
404 
412  const VertexDescriptor& target) const;
413 
414  private:
416  Matrix& matrix_;
418  EdgeDescriptor* start_;
420  MatrixGraph(const MatrixGraph&);
421 
422  };
423 
433  template<class G, class T>
434  class SubGraph
435  {
436  public:
440  typedef G Graph;
441 
446  typedef T Excluded;
447 
451  typedef typename Graph::VertexDescriptor VertexDescriptor;
452 
454 
462  {
463  public:
464  typedef ReadablePropertyMapTag Category;
465 
466  EdgeIndexMap(const EdgeDescriptor& firstEdge)
467  : firstEdge_(firstEdge)
468  {}
469 
472  : firstEdge_(emap.firstEdge_)
473  {}
474 
475  std::size_t operator[](const EdgeDescriptor& edge) const
476  {
477  return edge-firstEdge_;
478  }
479  private:
481  EdgeDescriptor firstEdge_;
483  EdgeIndexMap()
484  {}
485  };
486 
491  EdgeIndexMap getEdgeIndexMap();
492 
496  class EdgeIterator : public RandomAccessIteratorFacade<EdgeIterator,const EdgeDescriptor>
497  {
498  public:
504  explicit EdgeIterator(const VertexDescriptor& source, const EdgeDescriptor& edge);
505 
513  explicit EdgeIterator(const EdgeDescriptor& edge);
514 
516  bool equals(const EdgeIterator& other) const;
517 
520 
523 
524  EdgeIterator& advance(std::ptrdiff_t n);
525 
527  const EdgeDescriptor& dereference() const;
528 
530  const VertexDescriptor& target() const;
531 
533  const VertexDescriptor& source() const;
534 
535  std::ptrdiff_t distanceTo(const EdgeIterator& other) const;
536 
537  private:
539  VertexDescriptor source_;
544  EdgeDescriptor edge_;
545  };
546 
551  : public ForwardIteratorFacade<VertexIterator,const VertexDescriptor>
552  {
553  public:
560  explicit VertexIterator(const SubGraph<G,T>* graph, const VertexDescriptor& current,
561  const VertexDescriptor& end);
562 
563 
570  explicit VertexIterator(const VertexDescriptor& current);
571 
574 
576  bool equals(const VertexIterator& other) const;
577 
582  const VertexDescriptor& dereference() const;
583 
589  EdgeIterator begin() const;
590 
596  EdgeIterator end() const;
597 
598  private:
600  const SubGraph<Graph,T>* graph_;
602  VertexDescriptor current_;
604  VertexDescriptor end_;
605  };
606 
610  typedef EdgeIterator ConstEdgeIterator;
611 
615  typedef VertexIterator ConstVertexIterator;
616 
621  ConstVertexIterator begin() const;
622 
627  ConstVertexIterator end() const;
628 
635  ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
636 
643  ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
644 
648  std::size_t noVertices() const;
649 
656  VertexDescriptor maxVertex() const;
657 
661  std::size_t noEdges() const;
668  const EdgeDescriptor findEdge(const VertexDescriptor& source,
669  const VertexDescriptor& target) const;
677  SubGraph(const Graph& graph, const T& excluded);
678 
682  ~SubGraph();
683 
684  private:
686  const T& excluded_;
688  std::size_t noVertices_;
690  VertexDescriptor endVertex_;
692  int noEdges_;
697  VertexDescriptor maxVertex_;
699  VertexDescriptor* edges_;
701  std::ptrdiff_t* start_;
703  std::ptrdiff_t* end_;
705  SubGraph(const SubGraph&)
706  {}
707  };
708 
709 
713  template<class G, class VP, class VM=IdentityMap>
715  {
716  public:
720  typedef G Graph;
721 
725  typedef typename Graph::VertexDescriptor VertexDescriptor;
726 
730  typedef typename Graph::EdgeDescriptor EdgeDescriptor;
731 
735  typedef VP VertexProperties;
736 
748  typedef VM VertexMap;
749 
753  typedef typename Graph::EdgeIterator EdgeIterator;
754 
758  typedef typename Graph::ConstEdgeIterator ConstEdgeIterator;
759 
766 
772  EdgeIterator endEdges(const VertexDescriptor& source);
773 
779  ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
780 
786  ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
787 
788 
789  template<class C>
791  : public SelectType<is_same<typename remove_const<C>::type,
792  C>::value,
793  typename Graph::VertexIterator,
794  typename Graph::ConstVertexIterator>::Type
795  {
796  friend class VertexIteratorT<const typename remove_const<C>::type>;
797  friend class VertexIteratorT<typename remove_const<C>::type>;
798  public:
802  typedef typename SelectType<is_same<typename remove_const<C>::type,
803  C>::value,
804  typename Graph::VertexIterator,
805  typename Graph::ConstVertexIterator>::Type
807 
811  typedef typename SelectType<is_same<typename remove_const<C>::type,
812  C>::value,
813  typename Graph::EdgeIterator,
814  typename Graph::ConstEdgeIterator>::Type
816 
822  explicit VertexIteratorT(const Father& iter,
823  C* graph);
824 
825 
833  explicit VertexIteratorT(const Father& iter);
834 
839  template<class C1>
840  VertexIteratorT(const VertexIteratorT<C1>& other);
841 
845  typename SelectType<is_same<C,typename remove_const<C>::type>::value,
846  VertexProperties&,
847  const VertexProperties&>::Type
848  properties() const;
849 
855  EdgeIterator begin() const;
856 
862  EdgeIterator end() const;
863 
864  private:
868  C* graph_;
869  };
870 
874  typedef VertexIteratorT<VertexPropertiesGraph<Graph,
875  VertexProperties,VM> > VertexIterator;
876 
880  typedef VertexIteratorT<const VertexPropertiesGraph<Graph,
881  VertexProperties,VM> > ConstVertexIterator;
882 
888 
894 
899  ConstVertexIterator begin() const;
900 
905  ConstVertexIterator end() const;
906 
912  VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
913 
919  const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
920 
925  const Graph& graph() const;
926 
930  std::size_t noVertices() const;
931 
935  std::size_t noEdges() const;
936 
943  VertexDescriptor maxVertex() const;
944 
950  VertexPropertiesGraph(Graph& graph, const VertexMap vmap=VertexMap());
951 
952  private:
953  VertexPropertiesGraph(const VertexPropertiesGraph&)
954  {}
955 
957  Graph& graph_;
959  VertexMap vmap_;
961  std::vector<VertexProperties> vertexProperties_;
962 
963  };
964 
968  template<class G, class VP, class EP, class VM=IdentityMap, class EM=IdentityMap>
970  {
971  public:
975  typedef G Graph;
976 
980  typedef typename Graph::VertexDescriptor VertexDescriptor;
981 
985  typedef typename Graph::EdgeDescriptor EdgeDescriptor;
986 
990  typedef VP VertexProperties;
991 
1003  typedef VM VertexMap;
1004 
1008  typedef EP EdgeProperties;
1009 
1010 
1022  typedef EM EdgeMap;
1023 
1024  template<class C>
1026  : public SelectType<is_same<typename remove_const<C>::type,
1027  C>::value,
1028  typename Graph::EdgeIterator,
1029  typename Graph::ConstEdgeIterator>::Type
1030  {
1031 
1032  friend class EdgeIteratorT<const typename remove_const<C>::type>;
1033  friend class EdgeIteratorT<typename remove_const<C>::type>;
1034  public:
1038  typedef typename SelectType<is_same<typename remove_const<C>::type,
1039  C>::value,
1040  typename Graph::EdgeIterator,
1041  typename Graph::ConstEdgeIterator>::Type
1043 
1049  explicit EdgeIteratorT(const Father& iter,
1050  C* graph);
1051 
1059  explicit EdgeIteratorT(const Father& iter);
1060 
1065  template<class C1>
1066  EdgeIteratorT(const EdgeIteratorT<C1>& other);
1067 
1071  typename SelectType<is_same<C,typename remove_const<C>::type>::value,
1072  EdgeProperties&,
1073  const EdgeProperties&>::Type
1074  properties() const;
1075 
1076  private:
1080  C* graph_;
1081  };
1082 
1086  typedef EdgeIteratorT<PropertiesGraph<Graph,
1087  VertexProperties,
1088  EdgeProperties,VM,EM> > EdgeIterator;
1089 
1093  typedef EdgeIteratorT<const PropertiesGraph<Graph,
1094  VertexProperties,
1095  EdgeProperties,VM,EM> > ConstEdgeIterator;
1096 
1102  EdgeIterator beginEdges(const VertexDescriptor& source);
1103 
1109  EdgeIterator endEdges(const VertexDescriptor& source);
1110 
1116  ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
1117 
1123  ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
1124 
1125 
1126  template<class C>
1128  : public SelectType<is_same<typename remove_const<C>::type,
1129  C>::value,
1130  typename Graph::VertexIterator,
1131  typename Graph::ConstVertexIterator>::Type
1132  {
1133  friend class VertexIteratorT<const typename remove_const<C>::type>;
1134  friend class VertexIteratorT<typename remove_const<C>::type>;
1135  public:
1139  typedef typename SelectType<is_same<typename remove_const<C>::type,
1140  C>::value,
1141  typename Graph::VertexIterator,
1142  typename Graph::ConstVertexIterator>::Type
1144 
1150  explicit VertexIteratorT(const Father& iter,
1151  C* graph);
1152 
1153 
1161  explicit VertexIteratorT(const Father& iter);
1162 
1167  template<class C1>
1168  VertexIteratorT(const VertexIteratorT<C1>& other);
1169 
1173  typename SelectType<is_same<C,typename remove_const<C>::type>::value,
1174  VertexProperties&,
1175  const VertexProperties&>::Type
1176  properties() const;
1177 
1183  EdgeIteratorT<C> begin() const;
1184 
1190  EdgeIteratorT<C> end() const;
1191 
1192  private:
1196  C* graph_;
1197  };
1198 
1202  typedef VertexIteratorT<PropertiesGraph<Graph,
1203  VertexProperties,
1204  EdgeProperties,VM,EM> > VertexIterator;
1205 
1209  typedef VertexIteratorT<const PropertiesGraph<Graph,
1210  VertexProperties,
1211  EdgeProperties,VM,EM> > ConstVertexIterator;
1212 
1218 
1223  VertexIterator end();
1224 
1229  ConstVertexIterator begin() const;
1230 
1235  ConstVertexIterator end() const;
1236 
1242  VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
1243 
1249  const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
1250 
1257  EdgeDescriptor findEdge(const VertexDescriptor& source,
1258  const VertexDescriptor& target)
1259  {
1260  return graph_.findEdge(source,target);
1261  }
1262 
1268  EdgeProperties& getEdgeProperties(const EdgeDescriptor& edge);
1269 
1270 
1276  const EdgeProperties& getEdgeProperties(const EdgeDescriptor& edge) const;
1277 
1284  EdgeProperties& getEdgeProperties(const VertexDescriptor& source,
1285  const VertexDescriptor& target);
1286 
1293  const EdgeProperties& getEdgeProperties(const VertexDescriptor& source,
1294  const VertexDescriptor& target) const;
1295 
1300  const Graph& graph() const;
1301 
1305  std::size_t noVertices() const;
1306 
1310  std::size_t noEdges() const;
1311 
1318  VertexDescriptor maxVertex() const;
1319 
1326  PropertiesGraph(Graph& graph, const VertexMap& vmap=VertexMap(),
1327  const EdgeMap& emap=EdgeMap());
1328 
1329  private:
1331  {}
1332 
1334  Graph& graph_;
1337  VertexMap vmap_;
1338  std::vector<VertexProperties> vertexProperties_;
1340  EdgeMap emap_;
1342  std::vector<EdgeProperties> edgeProperties_;
1343 
1344  };
1345 
1346 
1351  template<typename G>
1353  {
1354  public:
1358  typedef G Graph;
1362  typedef typename G::VertexProperties VertexProperties;
1366  typedef typename G::VertexDescriptor Vertex;
1367 
1373  : graph_(g)
1374  {}
1379  :graph_(0)
1380  {}
1381 
1382 
1387  VertexProperties& operator[](const Vertex& vertex) const
1388  {
1389  return graph_->getVertexProperties(vertex);
1390  }
1391  private:
1392  Graph* graph_;
1393  };
1394 
1399  template<typename G>
1401  {
1402  public:
1406  typedef G Graph;
1410  typedef typename G::EdgeProperties EdgeProperties;
1414  typedef typename G::EdgeDescriptor Edge;
1415 
1421  : graph_(g)
1422  {}
1427  :graph_(0)
1428  {}
1429 
1434  EdgeProperties& operator[](const Edge& edge) const
1435  {
1436  return graph_->getEdgeProperties(edge);
1437  }
1438  private:
1439  Graph* graph_;
1440  };
1441 
1442 
1453  template<class G, class V>
1454  int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex,
1455  V& visitor);
1456 
1457 #ifndef DOXYGEN
1458 
1459  template<class M>
1460  MatrixGraph<M>::MatrixGraph(M& matrix)
1461  : matrix_(matrix)
1462  {
1463  if(matrix_.N()!=matrix_.M())
1464  DUNE_THROW(ISTLError, "Matrix has to have as many columns as rows!");
1465 
1466  start_ = new EdgeDescriptor[matrix_.N()+1];
1467 
1468  typedef typename M::ConstIterator Iterator;
1469  Iterator row = matrix_.begin();
1470  start_[row.index()] = 0;
1471 
1472  for(Iterator row=matrix_.begin(); row != matrix_.end(); ++row)
1473  start_[row.index()+1] = start_[row.index()] + row->size();
1474  }
1475 
1476  template<class M>
1478  {
1479  delete[] start_;
1480  }
1481 
1482  template<class M>
1483  inline std::size_t MatrixGraph<M>::noEdges() const
1484  {
1485  return start_[matrix_.N()];
1486  }
1487 
1488  template<class M>
1489  inline std::size_t MatrixGraph<M>::noVertices() const
1490  {
1491  return matrix_.N();
1492  }
1493 
1494  template<class M>
1495  inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::maxVertex() const
1496  {
1497  return matrix_.N()-1;
1498  }
1499 
1500  template<class M>
1501  typename MatrixGraph<M>::EdgeDescriptor
1502  MatrixGraph<M>::findEdge(const VertexDescriptor& source,
1503  const VertexDescriptor& target) const
1504  {
1505  typename M::ConstColIterator found =matrix_[source].find(target);
1506  if(found == matrix_[source].end())
1507  return std::numeric_limits<EdgeDescriptor>::max();
1508  std::size_t offset = found.offset();
1509  if(target>source)
1510  offset--;
1511 
1512  assert(offset<noEdges());
1513 
1514  return start_[source]+offset;
1515  }
1516 
1517 
1518  template<class M>
1519  inline M& MatrixGraph<M>::matrix()
1520  {
1521  return matrix_;
1522  }
1523 
1524  template<class M>
1525  inline const M& MatrixGraph<M>::matrix() const
1526  {
1527  return matrix_;
1528  }
1529 
1530  template<class M>
1531  template<class C>
1532  MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block,
1533  const ColIterator& end, const EdgeDescriptor& edge)
1534  : source_(source), block_(block), blockEnd_(end), edge_(edge)
1535  {
1536  if(block_!=blockEnd_ && block_.index() == source_){
1537  // This is the edge from the diagonal to the diagonal. Skip it.
1538  ++block_;
1539  }
1540  }
1541 
1542  template<class M>
1543  template<class C>
1544  MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const ColIterator& block)
1545  : block_(block)
1546  {}
1547 
1548  template<class M>
1549  template<class C>
1550  template<class C1>
1551  MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const EdgeIteratorT<C1>& other)
1552  : source_(other.source_), block_(other.block_), blockEnd_(other.blockEnd_), edge_(other.edge_)
1553  {}
1554 
1555 
1556  template<class M>
1557  template<class C>
1558  inline typename MatrixGraph<M>::template EdgeIteratorT<C>::WeightType&
1559  MatrixGraph<M>::EdgeIteratorT<C>::weight() const
1560  {
1561  return *block_;
1562  }
1563 
1564  template<class M>
1565  template<class C>
1566  inline typename MatrixGraph<M>::template EdgeIteratorT<C>& MatrixGraph<M>::EdgeIteratorT<C>::operator++()
1567  {
1568  ++block_;
1569  ++edge_;
1570 
1571  if(block_!=blockEnd_ && block_.index() == source_){
1572  // This is the edge from the diagonal to the diagonal. Skip it.
1573  ++block_;
1574  }
1575 
1576  return *this;
1577  }
1578 
1579  template<class M>
1580  template<class C>
1581  inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(const typename MatrixGraph<M>::template EdgeIteratorT<typename remove_const<C>::type>& other) const
1582  {
1583  return block_!=other.block_;
1584  }
1585 
1586  template<class M>
1587  template<class C>
1588  inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(const typename MatrixGraph<M>::template EdgeIteratorT<const 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<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<const 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 typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::target() const
1610  {
1611  return block_.index();
1612  }
1613 
1614  template<class M>
1615  template<class C>
1616  inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::source() const
1617  {
1618  return source_;
1619  }
1620 
1621  template<class M>
1622  template<class C>
1623  inline const typename MatrixGraph<M>::EdgeDescriptor& MatrixGraph<M>::EdgeIteratorT<C>::operator*() const
1624  {
1625  return edge_;
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  MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(C* graph,
1638  const VertexDescriptor& current)
1639  : graph_(graph), current_(current)
1640  {}
1641 
1642 
1643  template<class M>
1644  template<class C>
1645  MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(const VertexDescriptor& current)
1646  : current_(current)
1647  {}
1648 
1649  template<class M>
1650  template<class C>
1651  MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(const VertexIteratorT<MutableContainer>& other)
1652  : graph_(other.graph_), current_(other.current_)
1653  {}
1654 
1655  template<class M>
1656  template<class C>
1657  inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(const VertexIteratorT<MutableContainer>& other) const
1658  {
1659  return current_ != other.current_;
1660  }
1661 
1662  template<class M>
1663  template<class C>
1664  inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(const VertexIteratorT<ConstContainer>& other) const
1665  {
1666  return current_ != other.current_;
1667  }
1668 
1669 
1670  template<class M>
1671  template<class C>
1672  inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(const VertexIteratorT<MutableContainer>& other) const
1673  {
1674  return current_ == other.current_;
1675  }
1676 
1677  template<class M>
1678  template<class C>
1679  inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(const VertexIteratorT<ConstContainer>& other) const
1680  {
1681  return current_ == other.current_;
1682  }
1683 
1684  template<class M>
1685  template<class C>
1686  inline typename MatrixGraph<M>::template VertexIteratorT<C>& MatrixGraph<M>::VertexIteratorT<C>::operator++()
1687  {
1688  ++current_;
1689  return *this;
1690  }
1691 
1692  template<class M>
1693  template<class C>
1694  inline typename MatrixGraph<M>::template VertexIteratorT<C>::WeightType&
1695  MatrixGraph<M>::VertexIteratorT<C>::weight() const
1696  {
1697  return graph_->matrix()[current_][current_];
1698  }
1699 
1700  template<class M>
1701  template<class C>
1702  inline const typename MatrixGraph<M>::VertexDescriptor&
1703  MatrixGraph<M>::VertexIteratorT<C>::operator*() const
1704  {
1705  return current_;
1706  }
1707 
1708  template<class M>
1709  template<class C>
1710  inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1712  {
1713  return graph_->beginEdges(current_);
1714  }
1715 
1716  template<class M>
1717  template<class C>
1718  inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1720  {
1721  return graph_->endEdges(current_);
1722  }
1723 
1724  template<class M>
1725  inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1727  {
1728  return VertexIterator(this,0);
1729  }
1730 
1731  template<class M>
1732  inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1734  {
1735  return VertexIterator(matrix_.N());
1736  }
1737 
1738 
1739  template<class M>
1740  inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1741  MatrixGraph<M>::begin() const
1742  {
1743  return ConstVertexIterator(this, 0);
1744  }
1745 
1746  template<class M>
1747  inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1748  MatrixGraph<M>::end() const
1749  {
1750  return ConstVertexIterator(matrix_.N());
1751  }
1752 
1753  template<class M>
1754  inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1755  MatrixGraph<M>::beginEdges(const VertexDescriptor& source)
1756  {
1757  return EdgeIterator(source, matrix_.operator[](source).begin(),
1758  matrix_.operator[](source).end(), start_[source]);
1759  }
1760 
1761  template<class M>
1762  inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1763  MatrixGraph<M>::endEdges(const VertexDescriptor& source)
1764  {
1765  return EdgeIterator(matrix_.operator[](source).end());
1766  }
1767 
1768 
1769  template<class M>
1770  inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
1771  MatrixGraph<M>::beginEdges(const VertexDescriptor& source) const
1772  {
1773  return ConstEdgeIterator(source, matrix_.operator[](source).begin(),
1774  matrix_.operator[](source).end(), start_[source]);
1775  }
1776 
1777  template<class M>
1778  inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
1779  MatrixGraph<M>::endEdges(const VertexDescriptor& source) const
1780  {
1781  return ConstEdgeIterator(matrix_.operator[](source).end());
1782  }
1783 
1784 
1785  template<class G, class T>
1786  SubGraph<G,T>::EdgeIterator::EdgeIterator(const VertexDescriptor& source,
1787  const EdgeDescriptor& edge)
1788  : source_(source), edge_(edge)
1789  {}
1790 
1791 
1792  template<class G, class T>
1793  SubGraph<G,T>::EdgeIterator::EdgeIterator(const EdgeDescriptor& edge)
1794  : edge_(edge)
1795  {}
1796 
1797  template<class G, class T>
1798  typename SubGraph<G,T>::EdgeIndexMap SubGraph<G,T>::getEdgeIndexMap()
1799  {
1800  return EdgeIndexMap(edges_);
1801  }
1802 
1803  template<class G, class T>
1804  inline bool SubGraph<G,T>::EdgeIterator::equals(const EdgeIterator& other) const
1805  {
1806  return other.edge_==edge_;
1807  }
1808 
1809  template<class G, class T>
1810  inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::increment()
1811  {
1812  ++edge_;
1813  return *this;
1814  }
1815 
1816  template<class G, class T>
1817  inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::decrement()
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::advance(std::ptrdiff_t n)
1825  {
1826  edge_+=n;
1827  return *this;
1828  }
1829  template<class G, class T>
1830  inline const typename G::VertexDescriptor& SubGraph<G,T>::EdgeIterator::source() const
1831  {
1832  return source_;
1833  }
1834 
1835  template<class G, class T>
1836  inline const typename G::VertexDescriptor& SubGraph<G,T>::EdgeIterator::target() const
1837  {
1838  return *edge_;
1839  }
1840 
1841 
1842  template<class G, class T>
1843  inline const typename SubGraph<G,T>::EdgeDescriptor& SubGraph<G,T>::EdgeIterator::dereference() const
1844  {
1845  return edge_;
1846  }
1847 
1848  template<class G, class T>
1849  inline std::ptrdiff_t SubGraph<G,T>::EdgeIterator::distanceTo(const EdgeIterator& other) const
1850  {
1851  return other.edge_-edge_;
1852  }
1853 
1854  template<class G, class T>
1855  SubGraph<G,T>::VertexIterator::VertexIterator(const SubGraph<G,T>* graph,
1856  const VertexDescriptor& current,
1857  const VertexDescriptor& end)
1858  : graph_(graph), current_(current), end_(end)
1859  {
1860  // Skip excluded vertices
1861  typedef typename T::const_iterator Iterator;
1862 
1863  for(Iterator vertex = graph_->excluded_.begin();
1864  current_ != end_ && *vertex;
1865  ++vertex)
1866  ++current_;
1867  assert(current_ == end_ || !graph_->excluded_[current_]);
1868  }
1869 
1870  template<class G, class T>
1871  SubGraph<G,T>::VertexIterator::VertexIterator(const VertexDescriptor& current)
1872  : current_(current)
1873  {}
1874 
1875  template<class G, class T>
1876  inline typename SubGraph<G,T>::VertexIterator& SubGraph<G,T>::VertexIterator::increment()
1877  {
1878  ++current_;
1879  //Skip excluded vertices
1880  while(current_ != end_ && graph_->excluded_[current_])
1881  ++current_;
1882 
1883  assert(current_ == end_ || !graph_->excluded_[current_]);
1884  return *this;
1885  }
1886 
1887  template<class G, class T>
1888  inline bool SubGraph<G,T>::VertexIterator::equals(const VertexIterator& other) const
1889  {
1890  return current_==other.current_;
1891  }
1892 
1893  template<class G, class T>
1894  inline const typename G::VertexDescriptor& SubGraph<G,T>::VertexIterator::dereference() const
1895  {
1896  return current_;
1897  }
1898 
1899  template<class G, class T>
1900  inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::VertexIterator::begin() const
1901  {
1902  return graph_->beginEdges(current_);
1903  }
1904 
1905  template<class G, class T>
1906  inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::VertexIterator::end() const
1907  {
1908  return graph_->endEdges(current_);
1909  }
1910 
1911  template<class G, class T>
1912  inline typename SubGraph<G,T>::VertexIterator SubGraph<G,T>::begin() const
1913  {
1914  return VertexIterator(this, 0, endVertex_);
1915  }
1916 
1917 
1918  template<class G, class T>
1919  inline typename SubGraph<G,T>::VertexIterator SubGraph<G,T>::end() const
1920  {
1921  return VertexIterator(endVertex_);
1922  }
1923 
1924 
1925  template<class G, class T>
1926  inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::beginEdges(const VertexDescriptor& source) const
1927  {
1928  return EdgeIterator(source, edges_+start_[source]);
1929  }
1930 
1931  template<class G, class T>
1932  inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::endEdges(const VertexDescriptor& source) const
1933  {
1934  return EdgeIterator(edges_+end_[source]);
1935  }
1936 
1937  template<class G, class T>
1938  std::size_t SubGraph<G,T>::noVertices() const
1939  {
1940  return noVertices_;
1941  }
1942 
1943  template<class G, class T>
1944  inline typename SubGraph<G,T>::VertexDescriptor SubGraph<G,T>::maxVertex() const
1945  {
1946  return maxVertex_;
1947  }
1948 
1949  template<class G, class T>
1950  inline std::size_t SubGraph<G,T>::noEdges() const
1951  {
1952  return noEdges_;
1953  }
1954 
1955  template<class G, class T>
1956  inline const typename SubGraph<G,T>::EdgeDescriptor SubGraph<G,T>::findEdge(const VertexDescriptor& source,
1957  const VertexDescriptor& target) const
1958  {
1959  const EdgeDescriptor edge = std::lower_bound(edges_+start_[source], edges_+end_[source], target);
1960  if(edge==edges_+end_[source] || *edge!=target)
1961  return std::numeric_limits<EdgeDescriptor>::max();
1962 
1963  return edge;
1964  }
1965 
1966  template<class G, class T>
1968  {
1969  delete[] edges_;
1970  delete[] end_;
1971  delete[] start_;
1972  }
1973 
1974  template<class G, class T>
1975  SubGraph<G,T>::SubGraph(const G& graph, const T& excluded)
1976  : excluded_(excluded), noVertices_(0), endVertex_(0), maxVertex_(graph.maxVertex())
1977  {
1978  start_ = new std::ptrdiff_t[graph.noVertices()];
1979  end_ = new std::ptrdiff_t[graph.noVertices()];
1980  edges_ = new VertexDescriptor[graph.noEdges()];
1981 
1982  VertexDescriptor* edge=edges_;
1983 
1984  typedef typename Graph::ConstVertexIterator Iterator;
1985  Iterator endVertex=graph.end();
1986 
1987  for(Iterator vertex = graph.begin(); vertex != endVertex; ++vertex)
1988  if(excluded_[*vertex])
1989  start_[*vertex]=end_[*vertex]=-1;
1990  else{
1991  ++noVertices_;
1992  endVertex_ = std::max(*vertex, endVertex_);
1993 
1994  start_[*vertex] = edge-edges_;
1995 
1996  typedef typename Graph::ConstEdgeIterator Iterator;
1997  Iterator endEdge = vertex.end();
1998 
1999  for(Iterator iter=vertex.begin(); iter!= endEdge; ++iter)
2000  if(!excluded[iter.target()]){
2001  *edge = iter.target();
2002  ++edge;
2003  }
2004 
2005  end_[*vertex] = edge - edges_;
2006 
2007  // Sort the edges
2008  std::sort(edges_+start_[*vertex], edge);
2009  }
2010  noEdges_ = edge-edges_;
2011  ++endVertex_;
2012  }
2013 
2014  template<class G, class V, class VM>
2015  inline std::size_t VertexPropertiesGraph<G,V,VM>::noEdges() const
2016  {
2017  return graph_.noEdges();
2018  }
2019 
2020  template<class G, class V, class VM>
2021  inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2022  VertexPropertiesGraph<G,V,VM>::beginEdges(const VertexDescriptor& source)
2023  {
2024  return graph_.beginEdges(source);
2025  }
2026 
2027  template<class G, class V, class VM>
2028  inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2029  VertexPropertiesGraph<G,V,VM>::endEdges(const VertexDescriptor& source)
2030  {
2031  return graph_.endEdges(source);
2032  }
2033 
2034  template<class G, class V, class VM>
2035  typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2036  inline VertexPropertiesGraph<G,V,VM>::beginEdges(const VertexDescriptor& source) const
2037  {
2038  return graph_.beginEdges(source);
2039  }
2040 
2041  template<class G, class V, class VM>
2042  typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2043  VertexPropertiesGraph<G,V,VM>::endEdges(const VertexDescriptor& source) const
2044  {
2045  return graph_.endEdges(source);
2046  }
2047 
2048  template<class G, class V, class VM>
2049  template<class C>
2050  VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2051  ::VertexIteratorT(const Father& iter,
2052  C* graph)
2053  : Father(iter), graph_(graph)
2054  {}
2055 
2056  template<class G, class V, class VM>
2057  template<class C>
2058  VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2059  ::VertexIteratorT(const Father& iter)
2060  : Father(iter)
2061  {}
2062 
2063  template<class G, class V, class VM>
2064  template<class C>
2065  template<class C1>
2066  VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2067  ::VertexIteratorT(const VertexIteratorT<C1>& other)
2068  : Father(other), graph_(other.graph_)
2069  {}
2070 
2071  template<class G, class V, class VM>
2072  template<class C>
2074  V&, const V&>::Type
2075  inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::properties() const
2076  {
2077  return graph_->getVertexProperties(Father::operator*());
2078  }
2079 
2080  template<class G, class V, class VM>
2081  template<class C>
2083  C>::value,
2084  typename G::EdgeIterator,
2085  typename G::ConstEdgeIterator>::Type
2087  {
2088  return graph_->beginEdges(Father::operator*());
2089  }
2090 
2091  template<class G, class V, class VM>
2092  template<class C>
2094  C>::value,
2095  typename G::EdgeIterator,
2096  typename G::ConstEdgeIterator>::Type
2098  {
2099  return graph_->endEdges(Father::operator*());
2100  }
2101 
2102  template<class G, class V, class VM>
2103  inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::begin()
2104  {
2105  return VertexIterator(graph_.begin(), this);
2106  }
2107 
2108  template<class G, class V, class VM>
2109  inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::end()
2110  {
2111  return VertexIterator(graph_.end());
2112  }
2113 
2114 
2115  template<class G, class V, class VM>
2116  inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::begin() const
2117  {
2118  return ConstVertexIterator(graph_.begin(), this);
2119  }
2120 
2121  template<class G, class V, class VM>
2122  inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::end() const
2123  {
2124  return ConstVertexIterator(graph_.end());
2125  }
2126 
2127  template<class G, class V, class VM>
2128  inline V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(const VertexDescriptor& vertex)
2129  {
2130  return vertexProperties_[vmap_[vertex]];
2131  }
2132 
2133  template<class G, class V, class VM>
2134  inline const V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(const VertexDescriptor& vertex) const
2135  {
2136  return vertexProperties_[vmap_[vertex]];
2137  }
2138 
2139  template<class G, class V, class VM>
2140  inline const G& VertexPropertiesGraph<G,V,VM>::graph() const
2141  {
2142  return graph_;
2143  }
2144 
2145  template<class G, class V, class VM>
2146  inline std::size_t VertexPropertiesGraph<G,V,VM>::noVertices() const
2147  {
2148  return graph_.noVertices();
2149  }
2150 
2151 
2152  template<class G, class V, class VM>
2153  inline typename VertexPropertiesGraph<G,V,VM>::VertexDescriptor VertexPropertiesGraph<G,V,VM>::maxVertex() const
2154  {
2155  return graph_.maxVertex();
2156  }
2157 
2158  template<class G, class V, class VM>
2159  VertexPropertiesGraph<G,V,VM>::VertexPropertiesGraph(Graph& graph, const VM vmap)
2160  : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V())
2161  {}
2162 
2163  template<class G, class V, class E, class VM, class EM>
2164  template<class C>
2165  PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const Father& iter,
2166  C* graph)
2167  : Father(iter), graph_(graph)
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  : Father(iter)
2174  {}
2175 
2176  template<class G, class V, class E, class VM, class EM>
2177  template<class C>
2178  template<class C1>
2179  PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const EdgeIteratorT<C1>& other)
2180  : Father(other), graph_(other.graph_)
2181  {}
2182 
2183 
2184  template<class G, class V, class E, class VM, class EM>
2185  inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noEdges() const
2186  {
2187  return graph_.noEdges();
2188  }
2189 
2190  template<class G, class V, class E, class VM, class EM>
2191  template<class C>
2192  inline typename SelectType<is_same<C,typename remove_const<C>::type>::value,E&,const E&>::Type
2193  PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::properties() const
2194  {
2195  return graph_->getEdgeProperties(Father::operator*());
2196  }
2197 
2198  template<class G, class V, class E, class VM, class EM>
2199  inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2200  PropertiesGraph<G,V,E,VM,EM>::beginEdges(const VertexDescriptor& source)
2201  {
2202  return EdgeIterator(graph_.beginEdges(source), this);
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>::endEdges(const VertexDescriptor& source)
2208  {
2209  return EdgeIterator(graph_.endEdges(source));
2210  }
2211 
2212  template<class G, class V, class E, class VM, class EM>
2213  typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2214  inline PropertiesGraph<G,V,E,VM,EM>::beginEdges(const VertexDescriptor& source) const
2215  {
2216  return ConstEdgeIterator(graph_.beginEdges(source), this);
2217  }
2218 
2219  template<class G, class V, class E, class VM, class EM>
2220  typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2221  PropertiesGraph<G,V,E,VM,EM>::endEdges(const VertexDescriptor& source) const
2222  {
2223  return ConstEdgeIterator(graph_.endEdges(source));
2224  }
2225 
2226  template<class G, class V, class E, class VM, class EM>
2227  template<class C>
2228  PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2229  ::VertexIteratorT(const Father& iter,
2230  C* graph)
2231  : Father(iter), graph_(graph)
2232  {}
2233 
2234  template<class G, class V, class E, class VM, class EM>
2235  template<class C>
2236  PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2237  ::VertexIteratorT(const Father& iter)
2238  : Father(iter)
2239  {}
2240 
2241  template<class G, class V, class E, class VM, class EM>
2242  template<class C>
2243  template<class C1>
2244  PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2245  ::VertexIteratorT(const VertexIteratorT<C1>& other)
2246  : Father(other), graph_(other.graph_)
2247  {}
2248 
2249  template<class G, class V, class E, class VM, class EM>
2250  template<class C>
2252  V&, const V&>::Type
2253  PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::properties() const
2254  {
2255  return graph_->getVertexProperties(Father::operator*());
2256  }
2257 
2258  template<class G, class V, class E, class VM, class EM>
2259  template<class C>
2260  inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2262  {
2263  return graph_->beginEdges(Father::operator*());
2264  }
2265 
2266  template<class G, class V, class E, class VM, class EM>
2267  template<class C>
2268  inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2270  {
2271  return graph_->endEdges(Father::operator*());
2272  }
2273 
2274  template<class G, class V, class E, class VM, class EM>
2275  inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::begin()
2276  {
2277  return VertexIterator(graph_.begin(), this);
2278  }
2279 
2280  template<class G, class V, class E, class VM, class EM>
2281  inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::end()
2282  {
2283  return VertexIterator(graph_.end());
2284  }
2285 
2286 
2287  template<class G, class V, class E, class VM, class EM>
2288  inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::begin() const
2289  {
2290  return ConstVertexIterator(graph_.begin(), this);
2291  }
2292 
2293  template<class G, class V, class E, class VM, class EM>
2294  inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::end() const
2295  {
2296  return ConstVertexIterator(graph_.end());
2297  }
2298 
2299  template<class G, class V, class E, class VM, class EM>
2300  inline V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(const VertexDescriptor& vertex)
2301  {
2302  return vertexProperties_[vmap_[vertex]];
2303  }
2304 
2305  template<class G, class V, class E, class VM, class EM>
2306  inline const V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(const VertexDescriptor& vertex) const
2307  {
2308  return vertexProperties_[vmap_[vertex]];
2309  }
2310 
2311  template<class G, class V, class E, class VM, class EM>
2312  inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const EdgeDescriptor& edge)
2313  {
2314  return edgeProperties_[emap_[edge]];
2315  }
2316 
2317  template<class G, class V, class E, class VM, class EM>
2318  inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const EdgeDescriptor& edge) const
2319  {
2320  return edgeProperties_[emap_[edge]];
2321  }
2322 
2323  template<class G, class V, class E, class VM, class EM>
2324  inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const VertexDescriptor& source,
2325  const VertexDescriptor& target)
2326  {
2327  return getEdgeProperties(graph_.findEdge(source,target));
2328  }
2329 
2330  template<class G, class V, class E, class VM, class EM>
2331  inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const VertexDescriptor& source,
2332  const VertexDescriptor& target) const
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 G& PropertiesGraph<G,V,E,VM,EM>::graph() const
2339  {
2340  return graph_;
2341  }
2342 
2343  template<class G, class V, class E, class VM, class EM>
2344  inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noVertices() const
2345  {
2346  return graph_.noVertices();
2347  }
2348 
2349 
2350  template<class G, class V, class E, class VM, class EM>
2351  inline typename PropertiesGraph<G,V,E,VM,EM>::VertexDescriptor PropertiesGraph<G,V,E,VM,EM>::maxVertex() const
2352  {
2353  return graph_.maxVertex();
2354  }
2355 
2356  template<class G, class V, class E, class VM, class EM>
2357  PropertiesGraph<G,V,E,VM,EM>::PropertiesGraph(Graph& graph, const VM& vmap, const EM& emap)
2358  : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V()),
2359  emap_(emap), edgeProperties_(graph_.noEdges(), E())
2360  {}
2361 
2362  template<class G, class V>
2363  inline int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex,
2364  V& visitor)
2365  {
2366  typedef typename G::ConstEdgeIterator iterator;
2367  const iterator end = graph.endEdges(vertex);
2368  int noNeighbours=0;
2369  for(iterator edge = graph.beginEdges(vertex); edge != end; ++edge, ++noNeighbours)
2370  visitor(edge);
2371  return noNeighbours;
2372  }
2373 
2374 #endif // DOXYGEN
2375 
2377  }
2378 }
2379 #endif