dune-istl  2.2.0
graph.hh
Go to the documentation of this file.
00001 // $Id: graph.hh 1227 2010-07-07 14:43:07Z mblatt $
00002 #ifndef DUNE_AMG_GRAPH_HH
00003 #define DUNE_AMG_GRAPH_HH
00004 
00005 #include<cstddef>
00006 #include<algorithm>
00007 #include<vector>
00008 #include<cassert>
00009 #include<limits>
00010 #include<dune/common/typetraits.hh>
00011 #include<dune/common/iteratorfacades.hh>
00012 #include<dune/istl/istlexception.hh>
00013 #include<dune/common/propertymap.hh>
00014 
00015 namespace Dune
00016 {
00017   namespace Amg
00018   {
00046     template<class M>
00047     class MatrixGraph
00048     {
00049     public:     
00053       typedef M Matrix;
00054       
00058       typedef typename M::block_type Weight;
00059 
00065       typedef typename M::size_type VertexDescriptor;
00066          
00072       typedef std::ptrdiff_t EdgeDescriptor;
00073 
00074       enum{
00075         /*
00076          * @brief Whether Matrix is mutable.
00077          */
00078         mutableMatrix = is_same<M, typename remove_const<M>::type>::value
00079       };
00080       
00081       
00085       template<class C>
00086       class EdgeIteratorT
00087       {
00088                         
00089       public:
00093         typedef typename remove_const<C>::type MutableContainer;
00097         typedef const typename remove_const<C>::type ConstContainer;
00098         
00099         friend class EdgeIteratorT<MutableContainer>;
00100         friend class EdgeIteratorT<ConstContainer>;
00101 
00102         enum{ 
00104           isMutable = is_same<C, MutableContainer>::value
00105             };
00106         
00110         typedef typename SelectType<isMutable && C::mutableMatrix,typename Matrix::row_type::Iterator,
00111                            typename Matrix::row_type::ConstIterator>::Type
00112         ColIterator;
00113 
00117         typedef typename SelectType<isMutable && C::mutableMatrix,typename M::block_type,
00118                                     const typename M::block_type>::Type
00119         Weight;
00120 
00128         EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block,
00129                           const ColIterator& end, const EdgeDescriptor& edge);
00130         
00137         EdgeIteratorT(const ColIterator& block);
00138 
00143         template<class C1>
00144         EdgeIteratorT(const EdgeIteratorT<C1>& other);
00145         
00146         typedef typename SelectType<is_same<C, typename remove_const<C>::type>::value && C::mutableMatrix,
00147                                typename M::block_type, const typename M::block_type>::Type
00148         WeightType;
00149         
00153         WeightType& weight() const;
00154 
00156         EdgeIteratorT<C>& operator++();
00157 
00159         bool operator!=(const EdgeIteratorT<typename remove_const<C>::type>& other) const;
00160         
00162         bool operator!=(const EdgeIteratorT<const typename remove_const<C>::type>& other) const;
00163         
00165         bool operator==(const EdgeIteratorT<typename remove_const<C>::type>& other) const;
00166         
00168         bool operator==(const EdgeIteratorT<const typename remove_const<C>::type>& other) const;
00169 
00171         VertexDescriptor target() const;
00172 
00174         VertexDescriptor source() const;
00175         
00177         const EdgeDescriptor& operator*() const;
00178         
00180         const EdgeDescriptor* operator->() const;
00181         
00182       private:
00184         VertexDescriptor source_;
00186         ColIterator block_;
00187         /***
00188          * @brief The column iterator positioned at the end of the row 
00189          * of vertex source_ 
00190          */
00191         ColIterator blockEnd_;
00193         EdgeDescriptor edge_;
00194       };
00195 
00199       template<class C>
00200       class VertexIteratorT
00201       {
00202       public:
00206         typedef typename remove_const<C>::type MutableContainer;
00210         typedef const typename remove_const<C>::type ConstContainer;
00211         
00212         friend class VertexIteratorT<MutableContainer>;
00213         friend class VertexIteratorT<ConstContainer>;
00214 
00215         enum{ 
00217           isMutable = is_same<C, MutableContainer>::value
00218             };
00219 
00225         explicit VertexIteratorT(C* graph, const VertexDescriptor& current);
00226 
00234         explicit VertexIteratorT(const VertexDescriptor& current);
00235         
00236         VertexIteratorT(const VertexIteratorT<MutableContainer>& other);
00237         
00242         VertexIteratorT<C>& operator++();
00243         
00245         bool operator!=(const VertexIteratorT<ConstContainer>& other) const;
00246         
00248         bool operator==(const VertexIteratorT<ConstContainer>& other) const;
00249         
00251         bool operator!=(const VertexIteratorT<MutableContainer>& other) const;
00252         
00254         bool operator==(const VertexIteratorT<MutableContainer>& other) const;
00255         
00256         typedef typename SelectType<is_same<C, typename remove_const<C>::type>::value && C::mutableMatrix,
00257                                typename M::block_type, const typename M::block_type>::Type
00258         WeightType;
00260         WeightType& weight() const;
00261         
00266         const VertexDescriptor& operator*() const;
00267         
00273         EdgeIteratorT<C> begin() const;
00274         
00280         EdgeIteratorT<C> end() const;
00281          
00282       private:
00283         C* graph_;
00284         VertexDescriptor current_;
00285       };
00286       
00290       typedef EdgeIteratorT<const MatrixGraph<Matrix> > ConstEdgeIterator;
00291       
00295       typedef EdgeIteratorT<MatrixGraph<Matrix> > EdgeIterator;
00296       
00300       typedef VertexIteratorT<const MatrixGraph<Matrix> > ConstVertexIterator;
00301       
00305       typedef VertexIteratorT<MatrixGraph<Matrix> > VertexIterator;
00306 
00311       MatrixGraph(Matrix& matrix);
00312       
00316       ~MatrixGraph();
00317       
00322       VertexIterator begin();
00323 
00328       VertexIterator end();
00329       
00334       ConstVertexIterator begin() const;
00335       
00340       ConstVertexIterator end() const;
00341       
00348       EdgeIterator beginEdges(const VertexDescriptor& source);
00349       
00356       EdgeIterator endEdges(const VertexDescriptor& source);
00357 
00358       
00365       ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
00366       
00373       ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
00374 
00379       Matrix& matrix();
00380       
00385       const Matrix& matrix() const;
00386       
00390       std::size_t noVertices() const;
00391 
00398       VertexDescriptor maxVertex() const;
00399       
00403       std::size_t noEdges() const;
00404 
00411       EdgeDescriptor findEdge(const VertexDescriptor& source,
00412                               const VertexDescriptor& target) const;
00413       
00414     private:
00416       Matrix& matrix_;
00418       EdgeDescriptor* start_;
00420       MatrixGraph(const MatrixGraph&);
00421       
00422     };
00423 
00433     template<class G, class T>
00434     class SubGraph
00435     {
00436     public:
00440       typedef G Graph;
00441       
00446       typedef T Excluded;
00447       
00451       typedef typename Graph::VertexDescriptor VertexDescriptor;
00452 
00453       typedef VertexDescriptor* EdgeDescriptor;
00454       
00461       class EdgeIndexMap
00462       {
00463       public:
00464         typedef ReadablePropertyMapTag Category;
00465         
00466         EdgeIndexMap(const EdgeDescriptor& firstEdge)
00467           : firstEdge_(firstEdge)
00468         {}
00469         
00471         EdgeIndexMap(const EdgeIndexMap& emap)
00472           : firstEdge_(emap.firstEdge_)
00473         {}
00474 
00475         std::size_t operator[](const EdgeDescriptor& edge) const
00476         {
00477           return edge-firstEdge_;
00478         }
00479       private:
00481         EdgeDescriptor firstEdge_;
00483         EdgeIndexMap()
00484         {}
00485       };
00486       
00491       EdgeIndexMap getEdgeIndexMap();
00492       
00496       class EdgeIterator : public RandomAccessIteratorFacade<EdgeIterator,const EdgeDescriptor>
00497       {
00498       public:   
00504         explicit EdgeIterator(const VertexDescriptor& source, const EdgeDescriptor& edge);
00505                 
00513         explicit EdgeIterator(const EdgeDescriptor& edge);
00514         
00516         bool equals(const EdgeIterator& other) const;
00517                 
00519         EdgeIterator& increment();
00520         
00522         EdgeIterator& decrement();
00523 
00524         EdgeIterator& advance(std::ptrdiff_t n);
00525 
00527         const EdgeDescriptor& dereference() const;
00528 
00530         const VertexDescriptor& target() const;
00531 
00533         const VertexDescriptor& source() const;
00534 
00535         std::ptrdiff_t distanceTo(const EdgeIterator& other) const;
00536         
00537       private:
00539         VertexDescriptor source_;
00544         EdgeDescriptor edge_;   
00545       };
00546       
00550       class VertexIterator 
00551         : public ForwardIteratorFacade<VertexIterator,const VertexDescriptor>
00552       {
00553       public:
00560         explicit VertexIterator(const SubGraph<G,T>* graph, const VertexDescriptor& current,
00561                        const VertexDescriptor& end);
00562         
00563         
00570         explicit VertexIterator(const VertexDescriptor& current);
00571 
00573         VertexIterator& increment();
00574         
00576         bool equals(const VertexIterator& other) const;
00577                 
00582         const VertexDescriptor& dereference() const;
00583 
00589         EdgeIterator begin() const;
00590         
00596         EdgeIterator end() const;
00597         
00598       private:
00600         const SubGraph<Graph,T>* graph_;
00602         VertexDescriptor current_;
00604         VertexDescriptor end_;
00605       };
00606       
00610       typedef EdgeIterator ConstEdgeIterator;
00611       
00615       typedef VertexIterator ConstVertexIterator;
00616       
00621       ConstVertexIterator begin() const;
00622       
00627       ConstVertexIterator end() const;
00628       
00635       ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
00636       
00643       ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
00644       
00648       std::size_t noVertices() const;
00649       
00656       VertexDescriptor maxVertex() const;
00657 
00661       std::size_t noEdges() const;
00668       const EdgeDescriptor findEdge(const VertexDescriptor& source,
00669                                      const VertexDescriptor& target) const;
00677       SubGraph(const Graph& graph, const T& excluded);
00678       
00682       ~SubGraph();
00683       
00684     private:
00686       const T& excluded_;
00688       std::size_t noVertices_;
00690       VertexDescriptor endVertex_;
00692       int noEdges_;
00697       VertexDescriptor maxVertex_;
00699       VertexDescriptor* edges_;
00701       std::ptrdiff_t* start_;
00703       std::ptrdiff_t* end_;
00705       SubGraph(const SubGraph&)
00706       {}
00707     };
00708 
00709 
00713     template<class G, class VP, class VM=IdentityMap>
00714     class VertexPropertiesGraph
00715     {
00716     public:
00720       typedef G Graph;
00721 
00725       typedef typename Graph::VertexDescriptor VertexDescriptor;
00726 
00730       typedef typename Graph::EdgeDescriptor EdgeDescriptor;
00731       
00735       typedef VP VertexProperties;
00736 
00748       typedef VM VertexMap;
00749       
00753       typedef typename Graph::EdgeIterator EdgeIterator;
00754       
00758       typedef typename Graph::ConstEdgeIterator ConstEdgeIterator;
00759       
00765       EdgeIterator beginEdges(const VertexDescriptor& source);
00766       
00772       EdgeIterator endEdges(const VertexDescriptor& source);
00773 
00779       ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
00780       
00786       ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
00787 
00788       
00789       template<class C>
00790       class VertexIteratorT 
00791         : public SelectType<is_same<typename remove_const<C>::type,
00792                                      C>::value,
00793                             typename Graph::VertexIterator,
00794                             typename Graph::ConstVertexIterator>::Type
00795       {
00796         friend class VertexIteratorT<const typename remove_const<C>::type>;
00797         friend class VertexIteratorT<typename remove_const<C>::type>;
00798       public:
00802         typedef typename SelectType<is_same<typename remove_const<C>::type,
00803                                      C>::value,
00804                                     typename Graph::VertexIterator,
00805                                     typename Graph::ConstVertexIterator>::Type
00806         Father;
00807 
00811         typedef typename SelectType<is_same<typename remove_const<C>::type,
00812                                      C>::value,
00813                                     typename Graph::EdgeIterator,
00814                                     typename Graph::ConstEdgeIterator>::Type
00815         EdgeIterator;
00816         
00822         explicit VertexIteratorT(const Father& iter,
00823                         C* graph);
00824         
00825         
00833         explicit VertexIteratorT(const Father& iter);
00834 
00839         template<class C1>
00840         VertexIteratorT(const VertexIteratorT<C1>& other);
00841         
00845         typename SelectType<is_same<C,typename remove_const<C>::type>::value,
00846                             VertexProperties&,
00847                             const VertexProperties&>::Type 
00848         properties() const;
00849 
00855         EdgeIterator begin() const;
00856         
00862         EdgeIterator end() const;
00863 
00864       private:
00868         C* graph_;
00869       };
00870       
00874       typedef VertexIteratorT<VertexPropertiesGraph<Graph,
00875                                               VertexProperties,VM> > VertexIterator;
00876       
00880       typedef VertexIteratorT<const VertexPropertiesGraph<Graph,
00881                                                     VertexProperties,VM> > ConstVertexIterator;
00882      
00887       VertexIterator begin();
00888 
00893       VertexIterator end();
00894       
00899       ConstVertexIterator begin() const;
00900       
00905       ConstVertexIterator end() const;
00906       
00912       VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
00913       
00919       const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
00920       
00925       const Graph& graph() const;
00926 
00930       std::size_t noVertices() const;
00931       
00935       std::size_t noEdges() const;
00936 
00943       VertexDescriptor maxVertex() const;
00944       
00950       VertexPropertiesGraph(Graph& graph, const VertexMap vmap=VertexMap());
00951       
00952     private:
00953       VertexPropertiesGraph(const VertexPropertiesGraph&)
00954       {}
00955       
00957       Graph& graph_;
00959       VertexMap vmap_;
00961       std::vector<VertexProperties> vertexProperties_;
00962       
00963     };
00964 
00968     template<class G, class VP, class EP, class VM=IdentityMap, class EM=IdentityMap>
00969     class PropertiesGraph
00970     {
00971     public:
00975       typedef G Graph;
00976 
00980       typedef typename Graph::VertexDescriptor VertexDescriptor;
00981 
00985       typedef typename Graph::EdgeDescriptor EdgeDescriptor;
00986       
00990       typedef VP VertexProperties;
00991       
01003       typedef VM VertexMap;
01004 
01008       typedef EP EdgeProperties;
01009      
01010       
01022       typedef EM EdgeMap;
01023 
01024       template<class C>
01025       class EdgeIteratorT 
01026         :  public SelectType<is_same<typename remove_const<C>::type,
01027                                       C>::value,
01028                              typename Graph::EdgeIterator,
01029                              typename Graph::ConstEdgeIterator>::Type
01030       {
01031         
01032         friend class EdgeIteratorT<const typename remove_const<C>::type>;
01033         friend class EdgeIteratorT<typename remove_const<C>::type>;
01034       public:
01038         typedef typename SelectType<is_same<typename remove_const<C>::type,
01039                                       C>::value,
01040                                     typename Graph::EdgeIterator,
01041                                     typename Graph::ConstEdgeIterator>::Type
01042         Father;
01043         
01049         explicit EdgeIteratorT(const Father& iter,
01050                         C* graph);
01051         
01059         explicit EdgeIteratorT(const Father& iter);
01060 
01065         template<class C1>
01066         EdgeIteratorT(const EdgeIteratorT<C1>& other);
01067         
01071         typename SelectType<is_same<C,typename remove_const<C>::type>::value,
01072                             EdgeProperties&,
01073                             const EdgeProperties&>::Type 
01074         properties() const;
01075         
01076       private:
01080         C* graph_;
01081       };
01082       
01086       typedef EdgeIteratorT<PropertiesGraph<Graph,
01087                                             VertexProperties,
01088                                             EdgeProperties,VM,EM> > EdgeIterator;
01089       
01093       typedef EdgeIteratorT<const PropertiesGraph<Graph,
01094                                                   VertexProperties,
01095                                                   EdgeProperties,VM,EM> > ConstEdgeIterator;
01096       
01102       EdgeIterator beginEdges(const VertexDescriptor& source);
01103       
01109       EdgeIterator endEdges(const VertexDescriptor& source);
01110 
01116       ConstEdgeIterator beginEdges(const VertexDescriptor& source) const;
01117       
01123       ConstEdgeIterator endEdges(const VertexDescriptor& source) const;
01124 
01125       
01126       template<class C>
01127       class VertexIteratorT 
01128         : public SelectType<is_same<typename remove_const<C>::type,
01129                                      C>::value,
01130                             typename Graph::VertexIterator,
01131                             typename Graph::ConstVertexIterator>::Type
01132       {
01133         friend class VertexIteratorT<const typename remove_const<C>::type>;
01134         friend class VertexIteratorT<typename remove_const<C>::type>;
01135       public:
01139         typedef typename SelectType<is_same<typename remove_const<C>::type,
01140                                      C>::value,
01141                                     typename Graph::VertexIterator,
01142                                     typename Graph::ConstVertexIterator>::Type
01143         Father;
01144 
01150         explicit VertexIteratorT(const Father& iter,
01151                         C* graph);
01152         
01153         
01161         explicit VertexIteratorT(const Father& iter);
01162 
01167         template<class C1>
01168         VertexIteratorT(const VertexIteratorT<C1>& other);
01169         
01173         typename SelectType<is_same<C,typename remove_const<C>::type>::value,
01174                             VertexProperties&,
01175                             const VertexProperties&>::Type 
01176         properties() const;
01177 
01183         EdgeIteratorT<C> begin() const;
01184         
01190         EdgeIteratorT<C> end() const;
01191 
01192       private:
01196         C* graph_;
01197       };
01198       
01202       typedef VertexIteratorT<PropertiesGraph<Graph,
01203                                               VertexProperties,
01204                                               EdgeProperties,VM,EM> > VertexIterator;
01205       
01209       typedef VertexIteratorT<const PropertiesGraph<Graph,
01210                                                     VertexProperties,
01211                                                     EdgeProperties,VM,EM> > ConstVertexIterator;
01212      
01217       VertexIterator begin();
01218 
01223       VertexIterator end();
01224       
01229       ConstVertexIterator begin() const;
01230       
01235       ConstVertexIterator end() const;
01236       
01242       VertexProperties& getVertexProperties(const VertexDescriptor& vertex);
01243       
01249       const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const;
01250 
01257       EdgeDescriptor findEdge(const VertexDescriptor& source,
01258                               const VertexDescriptor& target)
01259       {
01260         return graph_.findEdge(source,target);
01261       }
01262       
01268       EdgeProperties& getEdgeProperties(const EdgeDescriptor& edge);
01269       
01270       
01276       const EdgeProperties& getEdgeProperties(const EdgeDescriptor& edge) const;
01277       
01284       EdgeProperties& getEdgeProperties(const VertexDescriptor& source,
01285                                     const VertexDescriptor& target);
01286       
01293       const EdgeProperties& getEdgeProperties(const VertexDescriptor& source,
01294                                     const VertexDescriptor& target) const;
01295       
01300       const Graph& graph() const;
01301 
01305       std::size_t noVertices() const;
01306 
01310       std::size_t noEdges() const;
01311 
01318       VertexDescriptor maxVertex() const;
01319       
01326       PropertiesGraph(Graph& graph, const VertexMap& vmap=VertexMap(),
01327                       const EdgeMap& emap=EdgeMap());
01328       
01329     private:
01330       PropertiesGraph(const PropertiesGraph&)
01331       {}
01332       
01334       Graph& graph_;
01337       VertexMap vmap_;
01338       std::vector<VertexProperties> vertexProperties_;
01340       EdgeMap emap_;
01342       std::vector<EdgeProperties> edgeProperties_;
01343       
01344     };
01345 
01346     
01351     template<typename G>
01352     class GraphVertexPropertiesSelector
01353     {
01354     public:
01358       typedef G Graph;
01362       typedef typename G::VertexProperties VertexProperties;
01366       typedef typename G::VertexDescriptor Vertex;
01367       
01372       GraphVertexPropertiesSelector(G& g)
01373         : graph_(g)
01374       {}
01378       GraphVertexPropertiesSelector()
01379         :graph_(0)
01380       {}
01381       
01382 
01387       VertexProperties& operator[](const Vertex& vertex) const
01388       {
01389         return graph_->getVertexProperties(vertex);
01390       }
01391     private:
01392       Graph* graph_;
01393     };
01394     
01399     template<typename G>
01400     class GraphEdgePropertiesSelector
01401     {
01402     public:
01406       typedef G Graph;
01410       typedef typename G::EdgeProperties EdgeProperties;
01414       typedef typename G::EdgeDescriptor Edge;
01415       
01420       GraphEdgePropertiesSelector(G& g)
01421         : graph_(g)
01422       {}
01426       GraphEdgePropertiesSelector()
01427         :graph_(0)
01428       {}
01429 
01434       EdgeProperties& operator[](const Edge& edge) const
01435       {
01436         return graph_->getEdgeProperties(edge);
01437       }
01438     private:
01439       Graph* graph_;
01440     };
01441     
01442 
01453     template<class G, class V>
01454     int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex, 
01455                          V& visitor);
01456 
01457 #ifndef DOXYGEN
01458     
01459     template<class M>
01460     MatrixGraph<M>::MatrixGraph(M& matrix)
01461       : matrix_(matrix)
01462     {
01463       if(matrix_.N()!=matrix_.M())
01464         DUNE_THROW(ISTLError, "Matrix has to have as many columns as rows!");
01465 
01466       start_ = new EdgeDescriptor[matrix_.N()+1];
01467       
01468       typedef typename M::ConstIterator Iterator;
01469       Iterator row = matrix_.begin();
01470       start_[row.index()] = 0;
01471       
01472       for(Iterator row=matrix_.begin(); row != matrix_.end(); ++row)
01473         start_[row.index()+1] = start_[row.index()] + row->size();
01474     }
01475 
01476     template<class M>
01477     MatrixGraph<M>::~MatrixGraph()
01478     {
01479       delete[] start_;
01480     }
01481     
01482     template<class M>
01483     inline std::size_t MatrixGraph<M>::noEdges() const
01484     {
01485       return start_[matrix_.N()];
01486     }
01487     
01488     template<class M>
01489     inline std::size_t MatrixGraph<M>::noVertices() const
01490     {
01491       return matrix_.N();
01492     }
01493 
01494     template<class M>
01495     inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::maxVertex() const
01496     {
01497       return matrix_.N()-1;
01498     }
01499 
01500     template<class M>
01501     typename MatrixGraph<M>::EdgeDescriptor
01502     MatrixGraph<M>::findEdge(const VertexDescriptor& source,
01503                              const VertexDescriptor& target) const
01504     {
01505       typename M::ConstColIterator found =matrix_[source].find(target);
01506       if(found == matrix_[source].end())
01507         return std::numeric_limits<EdgeDescriptor>::max();
01508       std::size_t offset = found.offset();
01509       if(target>source)
01510         offset--;
01511       
01512       assert(offset<noEdges());
01513       
01514       return start_[source]+offset;
01515     }
01516     
01517         
01518     template<class M>
01519     inline M& MatrixGraph<M>::matrix()
01520     {
01521       return matrix_;
01522     }
01523 
01524     template<class M>
01525     inline const M& MatrixGraph<M>::matrix() const
01526     {
01527       return matrix_;
01528     }   
01529     
01530     template<class M>
01531     template<class C>
01532     MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block,
01533                           const ColIterator& end, const EdgeDescriptor& edge)
01534       : source_(source), block_(block), blockEnd_(end), edge_(edge)
01535     {
01536       if(block_!=blockEnd_ && block_.index() == source_){
01537         // This is the edge from the diagonal to the diagonal. Skip it.
01538         ++block_;
01539       }
01540     }
01541    
01542     template<class M>
01543     template<class C>
01544     MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const ColIterator& block)
01545       : block_(block)
01546     {}
01547     
01548     template<class M>
01549     template<class C>
01550     template<class C1>
01551     MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(const EdgeIteratorT<C1>& other)
01552       : source_(other.source_), block_(other.block_), blockEnd_(other.blockEnd_), edge_(other.edge_)
01553     {}
01554 
01555     
01556     template<class M>
01557     template<class C>
01558     inline typename MatrixGraph<M>::template EdgeIteratorT<C>::WeightType& 
01559     MatrixGraph<M>::EdgeIteratorT<C>::weight() const
01560     {
01561       return *block_;
01562     }
01563 
01564     template<class M>
01565     template<class C>
01566     inline MatrixGraph<M>::EdgeIteratorT<C>& MatrixGraph<M>::EdgeIteratorT<C>::operator++()
01567     {      
01568       ++block_;
01569       ++edge_;
01570       
01571       if(block_!=blockEnd_ && block_.index() == source_){
01572         // This is the edge from the diagonal to the diagonal. Skip it.
01573         ++block_;
01574       }
01575       
01576       return *this;
01577     }
01578     
01579     template<class M>
01580     template<class C>
01581     inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(const MatrixGraph<M>::EdgeIteratorT<typename remove_const<C>::type>& other) const
01582     {
01583       return block_!=other.block_;
01584     }
01585 
01586     template<class M>
01587     template<class C>
01588     inline  bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(const MatrixGraph<M>::EdgeIteratorT<const typename remove_const<C>::type>& other) const
01589     {
01590       return block_!=other.block_;
01591     }
01592     
01593     template<class M>
01594     template<class C>
01595     inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator==(const MatrixGraph<M>::EdgeIteratorT<typename remove_const<C>::type>& other) const
01596     {
01597       return block_==other.block_;
01598     }
01599 
01600     template<class M>
01601     template<class C>
01602     inline  bool MatrixGraph<M>::EdgeIteratorT<C>::operator==(const MatrixGraph<M>::EdgeIteratorT<const typename remove_const<C>::type>& other) const
01603     {
01604       return block_==other.block_;
01605     }
01606     
01607     template<class M>
01608     template<class C>
01609     inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::target() const
01610     {
01611       return block_.index();
01612     }
01613     
01614     template<class M>
01615     template<class C>
01616     inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::source() const
01617     {
01618       return source_;
01619     }
01620 
01621     template<class M>
01622     template<class C>
01623     inline const typename MatrixGraph<M>::EdgeDescriptor& MatrixGraph<M>::EdgeIteratorT<C>::operator*() const
01624     {
01625       return edge_;
01626     }
01627   
01628     template<class M>
01629     template<class C>
01630     inline const typename MatrixGraph<M>::EdgeDescriptor* MatrixGraph<M>::EdgeIteratorT<C>::operator->() const
01631     {
01632       return &edge_;
01633     }
01634 
01635     template<class M>
01636     template<class C>
01637     MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(C* graph,
01638                                                       const VertexDescriptor& current)
01639       : graph_(graph), current_(current)
01640     {}
01641     
01642     
01643     template<class M>
01644     template<class C>
01645     MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(const VertexDescriptor& current)
01646       : current_(current)
01647     {}
01648 
01649     template<class M>
01650     template<class C>
01651     MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(const VertexIteratorT<MutableContainer>& other)
01652       : graph_(other.graph_), current_(other.current_)
01653     {}
01654     
01655     template<class M>
01656     template<class C>
01657     inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(const VertexIteratorT<MutableContainer>& other) const
01658     {
01659       return current_ != other.current_;
01660     }
01661     
01662     template<class M>
01663     template<class C>
01664     inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(const VertexIteratorT<ConstContainer>& other) const
01665     {
01666       return current_ != other.current_;
01667     }
01668     
01669     
01670     template<class M>
01671     template<class C>
01672     inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(const VertexIteratorT<MutableContainer>& other) const
01673     {
01674       return current_ == other.current_;
01675     }
01676     
01677     template<class M>
01678     template<class C>
01679     inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(const VertexIteratorT<ConstContainer>& other) const
01680     {
01681       return current_ == other.current_;
01682     }
01683 
01684     template<class M>
01685     template<class C>
01686     inline MatrixGraph<M>::VertexIteratorT<C>& MatrixGraph<M>::VertexIteratorT<C>::operator++()
01687     {
01688       ++current_;
01689       return *this;
01690     }
01691     
01692     template<class M>
01693     template<class C>
01694     inline typename MatrixGraph<M>::template VertexIteratorT<C>::WeightType&
01695     MatrixGraph<M>::VertexIteratorT<C>::weight() const
01696     {
01697       return graph_->matrix()[current_][current_];
01698     }
01699 
01700     template<class M>
01701     template<class C>
01702     inline const typename MatrixGraph<M>::VertexDescriptor& 
01703     MatrixGraph<M>::VertexIteratorT<C>::operator*() const
01704     {
01705       return current_;
01706     }
01707     
01708     template<class M>
01709     template<class C>
01710     inline MatrixGraph<M>::EdgeIteratorT<C>
01711     MatrixGraph<M>::VertexIteratorT<C>::begin() const
01712     {
01713       return graph_->beginEdges(current_);
01714     }
01715     
01716     template<class M>
01717     template<class C>
01718     inline MatrixGraph<M>::EdgeIteratorT<C>
01719     MatrixGraph<M>::VertexIteratorT<C>::end() const
01720     {
01721       return graph_->endEdges(current_);
01722     }
01723     
01724     template<class M>
01725     inline MatrixGraph<M>::VertexIteratorT<MatrixGraph<M> >
01726     MatrixGraph<M>::begin()
01727     {
01728       return VertexIterator(this,0);
01729     }
01730     
01731     template<class M>
01732     inline MatrixGraph<M>::VertexIteratorT<MatrixGraph<M> >
01733     MatrixGraph<M>::end()
01734     {
01735       return VertexIterator(matrix_.N());
01736     }
01737 
01738     
01739     template<class M>
01740     inline MatrixGraph<M>::VertexIteratorT<const MatrixGraph<M> >
01741     MatrixGraph<M>::begin() const
01742     {
01743       return ConstVertexIterator(this, 0);
01744     }
01745     
01746     template<class M>
01747     inline MatrixGraph<M>::VertexIteratorT<const MatrixGraph<M> >
01748     MatrixGraph<M>::end() const
01749     {
01750       return ConstVertexIterator(matrix_.N());
01751     }
01752 
01753     template<class M>
01754     inline MatrixGraph<M>::EdgeIteratorT<MatrixGraph<M> >
01755     MatrixGraph<M>::beginEdges(const VertexDescriptor& source)
01756     {
01757       return EdgeIterator(source, matrix_.operator[](source).begin(),
01758                           matrix_.operator[](source).end(), start_[source]);
01759     }
01760      
01761     template<class M>
01762     inline MatrixGraph<M>::EdgeIteratorT<MatrixGraph<M> >
01763     MatrixGraph<M>::endEdges(const VertexDescriptor& source)
01764     {
01765       return EdgeIterator(matrix_.operator[](source).end());
01766     }
01767 
01768     
01769     template<class M>
01770     inline MatrixGraph<M>::EdgeIteratorT<const MatrixGraph<M> >
01771     MatrixGraph<M>::beginEdges(const VertexDescriptor& source) const
01772     {
01773       return ConstEdgeIterator(source, matrix_.operator[](source).begin(),
01774                                matrix_.operator[](source).end(), start_[source]);
01775     }
01776      
01777     template<class M>
01778     inline MatrixGraph<M>::EdgeIteratorT<const MatrixGraph<M> >
01779     MatrixGraph<M>::endEdges(const VertexDescriptor& source) const
01780     {
01781       return ConstEdgeIterator(matrix_.operator[](source).end());
01782     }
01783     
01784 
01785     template<class G, class T>
01786     SubGraph<G,T>::EdgeIterator::EdgeIterator(const VertexDescriptor& source,
01787                                             const EdgeDescriptor& edge)
01788       : source_(source), edge_(edge)
01789     {}
01790 
01791     
01792     template<class G, class T>
01793     SubGraph<G,T>::EdgeIterator::EdgeIterator(const EdgeDescriptor& edge)
01794       : edge_(edge)
01795     {}
01796 
01797     template<class G, class T>
01798     typename SubGraph<G,T>::EdgeIndexMap SubGraph<G,T>::getEdgeIndexMap()
01799     {
01800       return EdgeIndexMap(edges_);
01801     }
01802     
01803     template<class G, class T>
01804     inline bool SubGraph<G,T>::EdgeIterator::equals(const EdgeIterator& other) const
01805     {
01806       return other.edge_==edge_;
01807     }
01808 
01809     template<class G, class T>
01810     inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::increment()
01811     {
01812       ++edge_;
01813       return *this;
01814     }
01815     
01816     template<class G, class T>
01817     inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::decrement()
01818     {
01819       --edge_;
01820       return *this;
01821     }
01822 
01823     template<class G, class T>
01824     inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::advance(std::ptrdiff_t n)
01825     {
01826       edge_+=n;
01827       return *this;
01828     }
01829     template<class G, class T>
01830     inline const typename G::VertexDescriptor& SubGraph<G,T>::EdgeIterator::source() const
01831     {
01832       return source_;
01833     }
01834     
01835     template<class G, class T>
01836     inline const typename G::VertexDescriptor& SubGraph<G,T>::EdgeIterator::target() const
01837     {
01838       return *edge_;
01839     }
01840 
01841     
01842     template<class G, class T>
01843     inline const typename SubGraph<G,T>::EdgeDescriptor& SubGraph<G,T>::EdgeIterator::dereference() const
01844     {
01845       return edge_;
01846     }
01847 
01848     template<class G, class T>
01849     inline std::ptrdiff_t SubGraph<G,T>::EdgeIterator::distanceTo(const EdgeIterator& other) const
01850     {
01851       return other.edge_-edge_;
01852     }
01853     
01854     template<class G, class T>
01855     SubGraph<G,T>::VertexIterator::VertexIterator(const SubGraph<G,T>* graph,
01856                                                 const VertexDescriptor& current,
01857                                                 const VertexDescriptor& end)
01858       : graph_(graph), current_(current), end_(end)
01859     {
01860       // Skip excluded vertices
01861       typedef typename T::const_iterator Iterator;
01862 
01863       for(Iterator vertex = graph_->excluded_.begin(); 
01864           current_ != end_ && *vertex; 
01865           ++vertex)
01866         ++current_;
01867       assert(current_ == end_ || !graph_->excluded_[current_]);
01868     }
01869     
01870     template<class G, class T>
01871     SubGraph<G,T>::VertexIterator::VertexIterator(const VertexDescriptor& current)
01872       : current_(current)
01873     {}
01874 
01875     template<class G, class T>
01876     inline typename SubGraph<G,T>::VertexIterator& SubGraph<G,T>::VertexIterator::increment()
01877     {
01878       ++current_;
01879       //Skip excluded vertices
01880       while(current_ != end_ && graph_->excluded_[current_])
01881         ++current_;
01882       
01883       assert(current_ == end_ || !graph_->excluded_[current_]);
01884       return *this;
01885     }
01886     
01887     template<class G, class T>
01888     inline bool SubGraph<G,T>::VertexIterator::equals(const VertexIterator& other) const
01889     {
01890       return current_==other.current_;
01891     }
01892     
01893     template<class G, class T>
01894     inline const typename G::VertexDescriptor& SubGraph<G,T>::VertexIterator::dereference() const
01895     {
01896       return current_;
01897     }
01898     
01899     template<class G, class T>
01900     inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::VertexIterator::begin() const
01901     {
01902       return graph_->beginEdges(current_);
01903     }
01904     
01905     template<class G, class T>
01906     inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::VertexIterator::end() const
01907     {
01908       return graph_->endEdges(current_);
01909     }
01910 
01911     template<class G, class T>
01912     inline typename SubGraph<G,T>::VertexIterator SubGraph<G,T>::begin() const
01913     {
01914       return VertexIterator(this, 0, endVertex_);
01915     }
01916     
01917     
01918     template<class G, class T>
01919     inline typename SubGraph<G,T>::VertexIterator SubGraph<G,T>::end() const
01920     {
01921       return VertexIterator(endVertex_);
01922     }
01923     
01924 
01925     template<class G, class T>
01926     inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::beginEdges(const VertexDescriptor& source) const
01927     {
01928       return EdgeIterator(source, edges_+start_[source]);
01929     }
01930 
01931     template<class G, class T>
01932     inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::endEdges(const VertexDescriptor& source) const
01933     {
01934       return EdgeIterator(edges_+end_[source]);
01935     }
01936 
01937     template<class G, class T>
01938     std::size_t SubGraph<G,T>::noVertices() const
01939     {
01940       return noVertices_;
01941     }
01942 
01943     template<class G, class T>
01944     inline typename SubGraph<G,T>::VertexDescriptor SubGraph<G,T>::maxVertex() const
01945     {
01946       return maxVertex_;
01947     }
01948 
01949     template<class G, class T>
01950     inline std::size_t SubGraph<G,T>::noEdges() const
01951     {
01952       return noEdges_;
01953     }
01954 
01955     template<class G, class T>
01956     inline const typename SubGraph<G,T>::EdgeDescriptor SubGraph<G,T>::findEdge(const VertexDescriptor& source,
01957                                                                       const VertexDescriptor& target) const
01958     {
01959       const EdgeDescriptor edge = std::lower_bound(edges_+start_[source], edges_+end_[source], target);
01960       if(edge==edges_+end_[source] || *edge!=target)
01961         return std::numeric_limits<EdgeDescriptor>::max();
01962 
01963       return edge;
01964     }
01965       
01966     template<class G, class T>
01967     SubGraph<G,T>::~SubGraph()
01968     {
01969       delete[] edges_;
01970       delete[] end_;
01971       delete[] start_;
01972     }
01973     
01974     template<class G, class T>
01975     SubGraph<G,T>::SubGraph(const G& graph, const T& excluded)
01976       : excluded_(excluded), noVertices_(0), endVertex_(0), maxVertex_(graph.maxVertex())
01977     {
01978       start_ = new std::ptrdiff_t[graph.noVertices()];
01979       end_ = new std::ptrdiff_t[graph.noVertices()];
01980       edges_ = new VertexDescriptor[graph.noEdges()];
01981       
01982       VertexDescriptor* edge=edges_;
01983       
01984       typedef typename Graph::ConstVertexIterator Iterator;
01985       Iterator endVertex=graph.end();
01986       
01987       for(Iterator vertex = graph.begin(); vertex != endVertex; ++vertex)
01988         if(excluded_[*vertex])
01989           start_[*vertex]=end_[*vertex]=-1;
01990         else{
01991           ++noVertices_;
01992           endVertex_ = std::max(*vertex, endVertex_);
01993           
01994           start_[*vertex] = edge-edges_;
01995 
01996           typedef typename Graph::ConstEdgeIterator Iterator;
01997           Iterator endEdge = vertex.end();
01998           
01999           for(Iterator iter=vertex.begin(); iter!= endEdge; ++iter)
02000             if(!excluded[iter.target()]){
02001               *edge = iter.target();
02002               ++edge;
02003             }
02004 
02005           end_[*vertex] = edge - edges_;
02006 
02007           // Sort the edges
02008           std::sort(edges_+start_[*vertex], edge);
02009         }
02010       noEdges_ = edge-edges_;
02011       ++endVertex_;
02012     }
02013 
02014     template<class G, class V, class VM>
02015     inline std::size_t VertexPropertiesGraph<G,V,VM>::noEdges() const
02016     {
02017       return graph_.noEdges();
02018     }
02019 
02020     template<class G, class V, class VM>
02021     inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
02022     VertexPropertiesGraph<G,V,VM>::beginEdges(const VertexDescriptor& source)
02023     {
02024       return graph_.beginEdges(source);
02025     }
02026     
02027     template<class G, class V, class VM>
02028     inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
02029     VertexPropertiesGraph<G,V,VM>::endEdges(const VertexDescriptor& source)
02030     {
02031       return graph_.endEdges(source);
02032     }
02033 
02034     template<class G, class V, class VM>
02035     typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
02036     inline VertexPropertiesGraph<G,V,VM>::beginEdges(const VertexDescriptor& source) const
02037     {
02038       return graph_.beginEdges(source);
02039     }
02040     
02041     template<class G, class V, class VM>
02042     typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
02043     VertexPropertiesGraph<G,V,VM>::endEdges(const VertexDescriptor& source) const
02044     {
02045       return graph_.endEdges(source);
02046     }
02047 
02048     template<class G, class V, class VM>
02049     template<class C>
02050     VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
02051     ::VertexIteratorT(const Father& iter,
02052                       C* graph)
02053       : Father(iter), graph_(graph)
02054     {}
02055 
02056     template<class G, class V, class VM>
02057     template<class C>
02058     VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
02059     ::VertexIteratorT(const Father& iter)
02060       : Father(iter)
02061     {}
02062 
02063     template<class G, class V, class VM>
02064     template<class C>
02065     template<class C1>
02066     VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
02067     ::VertexIteratorT(const VertexIteratorT<C1>& other)
02068       : Father(other), graph_(other.graph_)
02069     {}
02070 
02071     template<class G, class V, class VM>
02072     template<class C>
02073     typename SelectType<is_same<C,typename remove_const<C>::type>::value,
02074                         V&, const V&>::Type
02075     inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::properties() const
02076     {
02077       return graph_->getVertexProperties(Father::operator*());
02078     }
02079     
02080     template<class G, class V, class VM>
02081     template<class C>
02082     typename SelectType<is_same<typename remove_const<C>::type,
02083                                  C>::value,
02084                         typename G::EdgeIterator,
02085                         typename G::ConstEdgeIterator>::Type
02086     inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::begin() const
02087     {
02088       return graph_->beginEdges(Father::operator*());
02089     }
02090 
02091     template<class G, class V, class VM>
02092     template<class C>
02093     typename SelectType<is_same<typename remove_const<C>::type,
02094                                  C>::value,
02095                         typename G::EdgeIterator,
02096                         typename G::ConstEdgeIterator>::Type
02097     inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::end() const
02098     {
02099       return graph_->endEdges(Father::operator*());
02100     }
02101 
02102     template<class G, class V, class VM>
02103     inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::begin()
02104     {
02105       return VertexIterator(graph_.begin(), this);
02106     }
02107     
02108     template<class G, class V, class VM>
02109     inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::end()
02110     {
02111       return VertexIterator(graph_.end());
02112     }
02113 
02114     
02115     template<class G, class V, class VM>
02116     inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::begin() const
02117     {
02118       return ConstVertexIterator(graph_.begin(), this);
02119     }
02120     
02121     template<class G, class V, class VM>
02122     inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::end() const
02123     {
02124       return ConstVertexIterator(graph_.end());
02125     }
02126 
02127     template<class G, class V, class VM>
02128     inline V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(const VertexDescriptor& vertex)
02129     {
02130       return vertexProperties_[vmap_[vertex]];
02131     }
02132     
02133     template<class G, class V, class VM>
02134     inline const V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(const VertexDescriptor& vertex) const
02135     {
02136       return vertexProperties_[vmap_[vertex]];
02137     }
02138 
02139     template<class G, class V, class VM>
02140     inline const G& VertexPropertiesGraph<G,V,VM>::graph() const
02141     {
02142       return graph_;
02143     }
02144 
02145     template<class G, class V, class VM>
02146     inline std::size_t VertexPropertiesGraph<G,V,VM>::noVertices() const
02147     {
02148       return graph_.noVertices();
02149     }
02150     
02151     
02152     template<class G, class V, class VM>
02153     inline typename VertexPropertiesGraph<G,V,VM>::VertexDescriptor VertexPropertiesGraph<G,V,VM>::maxVertex() const
02154     {
02155       return graph_.maxVertex();
02156     }
02157 
02158     template<class G, class V, class VM>
02159     VertexPropertiesGraph<G,V,VM>::VertexPropertiesGraph(Graph& graph, const VM vmap)
02160       : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V())
02161     {}
02162 
02163     template<class G, class V, class E, class VM, class EM>
02164     template<class C>
02165     PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const Father& iter,
02166                                                     C* graph)
02167       : Father(iter), graph_(graph)
02168     {}
02169     
02170     template<class G, class V, class E, class VM, class EM>
02171     template<class C>
02172     PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const Father& iter)
02173       : Father(iter)
02174     {}
02175 
02176     template<class G, class V, class E, class VM, class EM>
02177     template<class C>
02178     template<class C1>
02179     PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(const EdgeIteratorT<C1>& other)
02180       : Father(other), graph_(other.graph_)
02181     {}
02182 
02183 
02184     template<class G, class V, class E, class VM, class EM>
02185     inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noEdges() const
02186     {
02187       return graph_.noEdges();
02188     }
02189 
02190     template<class G, class V, class E, class VM, class EM>
02191     template<class C>
02192     inline typename SelectType<is_same<C,typename remove_const<C>::type>::value,E&,const E&>::Type
02193     PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::properties() const
02194     {
02195       return graph_->getEdgeProperties(Father::operator*());
02196     }
02197     
02198     template<class G, class V, class E, class VM, class EM>
02199     inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
02200     PropertiesGraph<G,V,E,VM,EM>::beginEdges(const VertexDescriptor& source)
02201     {
02202       return EdgeIterator(graph_.beginEdges(source), this);
02203     }
02204     
02205     template<class G, class V, class E, class VM, class EM>
02206     inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
02207     PropertiesGraph<G,V,E,VM,EM>::endEdges(const VertexDescriptor& source)
02208     {
02209       return EdgeIterator(graph_.endEdges(source));
02210     }
02211 
02212     template<class G, class V, class E, class VM, class EM>
02213     typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
02214     inline PropertiesGraph<G,V,E,VM,EM>::beginEdges(const VertexDescriptor& source) const
02215     {
02216       return ConstEdgeIterator(graph_.beginEdges(source), this);
02217     }
02218     
02219     template<class G, class V, class E, class VM, class EM>
02220     typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
02221     PropertiesGraph<G,V,E,VM,EM>::endEdges(const VertexDescriptor& source) const
02222     {
02223       return ConstEdgeIterator(graph_.endEdges(source));
02224     }
02225 
02226     template<class G, class V, class E, class VM, class EM>
02227     template<class C>
02228     PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
02229     ::VertexIteratorT(const Father& iter,
02230                       C* graph)
02231       : Father(iter), graph_(graph)
02232     {}
02233 
02234     template<class G, class V, class E, class VM, class EM>
02235     template<class C>
02236     PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
02237     ::VertexIteratorT(const Father& iter)
02238       : Father(iter)
02239     {}
02240 
02241     template<class G, class V, class E, class VM, class EM>
02242     template<class C>
02243     template<class C1>
02244     PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
02245     ::VertexIteratorT(const VertexIteratorT<C1>& other)
02246       : Father(other), graph_(other.graph_)
02247     {}
02248 
02249     template<class G, class V, class E, class VM, class EM>
02250     template<class C>
02251     inline typename SelectType<is_same<C,typename remove_const<C>::type>::value,
02252                         V&, const V&>::Type
02253     PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::properties() const
02254     {
02255       return graph_->getVertexProperties(Father::operator*());
02256     }
02257     
02258     template<class G, class V, class E, class VM, class EM>
02259     template<class C>
02260     inline PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>
02261     PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::begin() const
02262     {
02263       return graph_->beginEdges(Father::operator*());
02264     }
02265 
02266     template<class G, class V, class E, class VM, class EM>
02267     template<class C>
02268     inline PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>
02269     PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::end() const
02270     {
02271       return graph_->endEdges(Father::operator*());
02272     }
02273 
02274     template<class G, class V, class E, class VM, class EM>
02275     inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::begin()
02276     {
02277       return VertexIterator(graph_.begin(), this);
02278     }
02279     
02280     template<class G, class V, class E, class VM, class EM>
02281     inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::end()
02282     {
02283       return VertexIterator(graph_.end());
02284     }
02285 
02286     
02287     template<class G, class V, class E, class VM, class EM>
02288     inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::begin() const
02289     {
02290       return ConstVertexIterator(graph_.begin(), this);
02291     }
02292     
02293     template<class G, class V, class E, class VM, class EM>
02294     inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::end() const
02295     {
02296       return ConstVertexIterator(graph_.end());
02297     }
02298 
02299     template<class G, class V, class E, class VM, class EM>
02300     inline V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(const VertexDescriptor& vertex)
02301     {
02302       return vertexProperties_[vmap_[vertex]];
02303     }
02304     
02305     template<class G, class V, class E, class VM, class EM>
02306     inline const V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(const VertexDescriptor& vertex) const
02307     {
02308       return vertexProperties_[vmap_[vertex]];
02309     }
02310     
02311     template<class G, class V, class E, class VM, class EM>
02312     inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const EdgeDescriptor& edge)
02313     {
02314       return edgeProperties_[emap_[edge]];
02315     }
02316 
02317     template<class G, class V, class E, class VM, class EM>
02318     inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const EdgeDescriptor& edge) const
02319     {
02320       return edgeProperties_[emap_[edge]];
02321     }
02322 
02323     template<class G, class V, class E, class VM, class EM>
02324     inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const VertexDescriptor& source,
02325                                                const VertexDescriptor& target)
02326     {
02327       return getEdgeProperties(graph_.findEdge(source,target));
02328     }
02329 
02330     template<class G, class V, class E, class VM, class EM>
02331     inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(const VertexDescriptor& source,
02332                                                const VertexDescriptor& target) const
02333     {
02334       return getEdgeProperties(graph_.findEdge(source,target));
02335     }
02336 
02337     template<class G, class V, class E, class VM, class EM>
02338     inline const G& PropertiesGraph<G,V,E,VM,EM>::graph() const
02339     {
02340       return graph_;
02341     }
02342 
02343     template<class G, class V, class E, class VM, class EM>
02344     inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noVertices() const
02345     {
02346       return graph_.noVertices();
02347     }
02348     
02349     
02350     template<class G, class V, class E, class VM, class EM>
02351     inline typename PropertiesGraph<G,V,E,VM,EM>::VertexDescriptor PropertiesGraph<G,V,E,VM,EM>::maxVertex() const
02352     {
02353       return graph_.maxVertex();
02354     }
02355 
02356     template<class G, class V, class E, class VM, class EM>
02357     PropertiesGraph<G,V,E,VM,EM>::PropertiesGraph(Graph& graph, const VM& vmap, const EM& emap)
02358       : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V()),
02359         emap_(emap), edgeProperties_(graph_.noEdges(), E())
02360     {}
02361 
02362     template<class G, class V>
02363     inline int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex, 
02364                          V& visitor)
02365     {      
02366       typedef typename G::ConstEdgeIterator iterator;
02367       const iterator end = graph.endEdges(vertex);
02368       int noNeighbours=0;
02369       for(iterator edge = graph.beginEdges(vertex); edge != end; ++edge, ++noNeighbours)
02370         visitor(edge);
02371       return noNeighbours;
02372     }
02373 
02374 #endif // DOXYGEN
02375       
02377   }
02378 }
02379 #endif