3#ifndef DUNE_AMG_GRAPH_HH
4#define DUNE_AMG_GRAPH_HH
13#include <dune/istl/istlexception.hh>
14#include <dune/common/propertymap.hh>
64 typedef typename M::block_type
Weight;
84 mutableMatrix = is_same<M, typename remove_const<M>::type>::value
110 isMutable = is_same<C, MutableContainer>::value
123 typedef typename conditional<
isMutable && C::mutableMatrix,
typename M::block_type,
124 const typename M::block_type>::type
152 typedef typename conditional<is_same<C, typename remove_const<C>::type>::value && C::mutableMatrix,
153 typename M::block_type,
const typename M::block_type>::type
223 isMutable = is_same<C, MutableContainer>::value
262 typedef typename conditional<is_same<C, typename remove_const<C>::type>::value && C::mutableMatrix,
263 typename M::block_type,
const typename M::block_type>::type
439 template<
class G,
class T>
473 : firstEdge_(firstEdge)
478 : firstEdge_(emap.firstEdge_)
481 std::size_t operator[](
const EdgeDescriptor& edge)
const
483 return edge-firstEdge_;
487 EdgeDescriptor firstEdge_;
541 std::ptrdiff_t distanceTo(
const EdgeIterator& other)
const;
550 EdgeDescriptor edge_;
694 std::size_t noVertices_;
707 std::ptrdiff_t* start_;
709 std::ptrdiff_t* end_;
719 template<
class G,
class VP,
class VM=IdentityMap>
796 class VertexIteratorT
797 :
public conditional<is_same<typename remove_const<C>::type,
799 typename Graph::VertexIterator,
800 typename Graph::ConstVertexIterator>::type
802 friend class VertexIteratorT<const typename remove_const<C>::type>;
803 friend class VertexIteratorT<typename remove_const<C>::type>;
808 typedef typename conditional<is_same<typename remove_const<C>::type,
810 typename Graph::VertexIterator,
811 typename Graph::ConstVertexIterator>::type
817 typedef typename conditional<is_same<typename remove_const<C>::type,
819 typename Graph::EdgeIterator,
820 typename Graph::ConstEdgeIterator>::type
828 explicit VertexIteratorT(const Father& iter,
839 explicit VertexIteratorT(const Father& iter);
846 VertexIteratorT(const VertexIteratorT<C1>& other);
851 typename conditional<is_same<C,typename remove_const<C>::type>::value,
853 const VertexProperties&>::type
880 typedef VertexIteratorT<VertexPropertiesGraph<Graph,
886 typedef VertexIteratorT<const VertexPropertiesGraph<Graph,
967 std::vector<VertexProperties> vertexProperties_;
974 template<
class G,
class VP,
class EP,
class VM=IdentityMap,
class EM=IdentityMap>
1032 :
public conditional<is_same<typename remove_const<C>::type,
1034 typename Graph::EdgeIterator,
1035 typename Graph::ConstEdgeIterator>::type
1038 friend class EdgeIteratorT<const typename remove_const<C>::type>;
1039 friend class EdgeIteratorT<typename remove_const<C>::type>;
1044 typedef typename conditional<is_same<typename remove_const<C>::type,
1046 typename Graph::EdgeIterator,
1047 typename Graph::ConstEdgeIterator>::type
1055 explicit EdgeIteratorT(const Father& iter,
1065 explicit EdgeIteratorT(const Father& iter);
1072 EdgeIteratorT(const EdgeIteratorT<C1>& other);
1077 typename conditional<is_same<C,typename remove_const<C>::type>::value,
1079 const EdgeProperties&>::type
1092 typedef EdgeIteratorT<PropertiesGraph<Graph,
1099 typedef EdgeIteratorT<const PropertiesGraph<Graph,
1133 class VertexIteratorT
1134 :
public conditional<is_same<typename remove_const<C>::type,
1136 typename Graph::VertexIterator,
1137 typename Graph::ConstVertexIterator>::type
1139 friend class VertexIteratorT<const typename remove_const<C>::type>;
1140 friend class VertexIteratorT<typename remove_const<C>::type>;
1145 typedef typename conditional<is_same<typename remove_const<C>::type,
1147 typename Graph::VertexIterator,
1148 typename Graph::ConstVertexIterator>::type
1156 explicit VertexIteratorT(const Father& iter,
1167 explicit VertexIteratorT(const Father& iter);
1174 VertexIteratorT(const VertexIteratorT<C1>& other);
1179 typename conditional<is_same<C,typename remove_const<C>::type>::value,
1181 const VertexProperties&>::type
1189 EdgeIteratorT<C>
begin() const;
1196 EdgeIteratorT<C>
end() const;
1208 typedef VertexIteratorT<PropertiesGraph<Graph,
1215 typedef VertexIteratorT<const PropertiesGraph<Graph,
1264 const VertexDescriptor& target)
1266 return graph_.findEdge(source,target);
1344 std::vector<VertexProperties> vertexProperties_;
1348 std::vector<EdgeProperties> edgeProperties_;
1357 template<
typename G>
1395 return graph_->getVertexProperties(vertex);
1405 template<
typename G>
1420 typedef typename G::EdgeDescriptor
Edge;
1442 return graph_->getEdgeProperties(edge);
1459 template<
class G,
class V>
1469 if(matrix_.N()!=matrix_.M())
1472 start_ =
new EdgeDescriptor[matrix_.N()+1];
1474 typedef typename M::ConstIterator Iterator;
1475 start_[matrix_.begin().index()] = 0;
1477 for(Iterator row=matrix_.begin(); row != matrix_.end(); ++row)
1478 start_[row.index()+1] = start_[row.index()] + row->size();
1482 MatrixGraph<M>::~MatrixGraph()
1488 inline std::size_t MatrixGraph<M>::noEdges()
const
1490 return start_[matrix_.N()];
1494 inline std::size_t MatrixGraph<M>::noVertices()
const
1500 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::maxVertex()
const
1502 return matrix_.N()-1;
1506 typename MatrixGraph<M>::EdgeDescriptor
1507 MatrixGraph<M>::findEdge(
const VertexDescriptor& source,
1508 const VertexDescriptor& target)
const
1510 typename M::ConstColIterator found =matrix_[source].find(target);
1511 if(found == matrix_[source].end())
1512 return std::numeric_limits<EdgeDescriptor>::max();
1513 std::size_t offset = found.offset();
1517 assert(offset<noEdges());
1519 return start_[source]+offset;
1524 inline M& MatrixGraph<M>::matrix()
1530 inline const M& MatrixGraph<M>::matrix()
const
1537 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(
const VertexDescriptor& source,
const ColIterator& block,
1538 const ColIterator& end,
const EdgeDescriptor& edge)
1539 : source_(source), block_(block), blockEnd_(end), edge_(edge)
1541 if(block_!=blockEnd_ && block_.index() == source_) {
1549 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(
const ColIterator& block)
1556 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(
const EdgeIteratorT<C1>& other)
1557 : source_(other.source_), block_(other.block_), blockEnd_(other.blockEnd_), edge_(other.edge_)
1563 inline typename MatrixGraph<M>::template EdgeIteratorT<C>::WeightType&
1564 MatrixGraph<M>::EdgeIteratorT<C>::weight()
const
1571 inline typename MatrixGraph<M>::template EdgeIteratorT<C>& MatrixGraph<M>::EdgeIteratorT<C>::operator++()
1576 if(block_!=blockEnd_ && block_.index() == source_) {
1588 return block_!=other.block_;
1595 return block_!=other.block_;
1602 return block_==other.block_;
1609 return block_==other.block_;
1614 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::target()
const
1616 return block_.index();
1621 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::source()
const
1628 inline const typename MatrixGraph<M>::EdgeDescriptor& MatrixGraph<M>::EdgeIteratorT<C>::operator*()
const
1635 inline const typename MatrixGraph<M>::EdgeDescriptor* MatrixGraph<M>::EdgeIteratorT<C>::operator->()
const
1642 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(C* graph,
1643 const VertexDescriptor& current)
1644 : graph_(graph), current_(current)
1650 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(
const VertexDescriptor& current)
1656 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(
const VertexIteratorT<MutableContainer>& other)
1657 : graph_(other.graph_), current_(other.current_)
1664 return current_ != other.current_;
1671 return current_ != other.current_;
1679 return current_ == other.current_;
1686 return current_ == other.current_;
1691 inline typename MatrixGraph<M>::template VertexIteratorT<C>& MatrixGraph<M>::VertexIteratorT<C>::operator++()
1699 inline typename MatrixGraph<M>::template VertexIteratorT<C>::WeightType&
1700 MatrixGraph<M>::VertexIteratorT<C>::weight()
const
1702 return graph_->matrix()[current_][current_];
1707 inline const typename MatrixGraph<M>::VertexDescriptor&
1708 MatrixGraph<M>::VertexIteratorT<C>::operator*()
const
1715 inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1716 MatrixGraph<M>::VertexIteratorT<C>::begin()
const
1718 return graph_->beginEdges(current_);
1723 inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1724 MatrixGraph<M>::VertexIteratorT<C>::end()
const
1726 return graph_->endEdges(current_);
1730 inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1731 MatrixGraph<M>::begin()
1733 return VertexIterator(
this,0);
1737 inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1738 MatrixGraph<M>::end()
1740 return VertexIterator(matrix_.N());
1745 inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1746 MatrixGraph<M>::begin()
const
1748 return ConstVertexIterator(
this, 0);
1752 inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1753 MatrixGraph<M>::end()
const
1755 return ConstVertexIterator(matrix_.N());
1759 inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1760 MatrixGraph<M>::beginEdges(
const VertexDescriptor& source)
1762 return EdgeIterator(source, matrix_.operator[](source).begin(),
1763 matrix_.operator[](source).end(), start_[source]);
1767 inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1768 MatrixGraph<M>::endEdges(
const VertexDescriptor& source)
1770 return EdgeIterator(matrix_.operator[](source).end());
1775 inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
1776 MatrixGraph<M>::beginEdges(
const VertexDescriptor& source)
const
1778 return ConstEdgeIterator(source, matrix_.operator[](source).begin(),
1779 matrix_.operator[](source).end(), start_[source]);
1783 inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
1784 MatrixGraph<M>::endEdges(
const VertexDescriptor& source)
const
1786 return ConstEdgeIterator(matrix_.operator[](source).end());
1790 template<
class G,
class T>
1791 SubGraph<G,T>::EdgeIterator::EdgeIterator(
const VertexDescriptor& source,
1792 const EdgeDescriptor& edge)
1793 : source_(source), edge_(edge)
1797 template<
class G,
class T>
1798 SubGraph<G,T>::EdgeIterator::EdgeIterator(
const EdgeDescriptor& edge)
1802 template<
class G,
class T>
1803 typename SubGraph<G,T>::EdgeIndexMap SubGraph<G,T>::getEdgeIndexMap()
1805 return EdgeIndexMap(edges_);
1808 template<
class G,
class T>
1809 inline bool SubGraph<G,T>::EdgeIterator::equals(
const EdgeIterator & other)
const
1811 return other.edge_==edge_;
1814 template<
class G,
class T>
1815 inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::increment()
1821 template<
class G,
class T>
1822 inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::decrement()
1828 template<
class G,
class T>
1829 inline typename SubGraph<G,T>::EdgeIterator& SubGraph<G,T>::EdgeIterator::advance(std::ptrdiff_t n)
1834 template<
class G,
class T>
1835 inline const typename G::VertexDescriptor& SubGraph<G,T>::EdgeIterator::source()
const
1840 template<
class G,
class T>
1841 inline const typename G::VertexDescriptor& SubGraph<G,T>::EdgeIterator::target()
const
1847 template<
class G,
class T>
1848 inline const typename SubGraph<G,T>::EdgeDescriptor& SubGraph<G,T>::EdgeIterator::dereference()
const
1853 template<
class G,
class T>
1854 inline std::ptrdiff_t SubGraph<G,T>::EdgeIterator::distanceTo(
const EdgeIterator & other)
const
1856 return other.edge_-edge_;
1859 template<
class G,
class T>
1860 SubGraph<G,T>::VertexIterator::VertexIterator(
const SubGraph<G,T>* graph,
1861 const VertexDescriptor& current,
1862 const VertexDescriptor& end)
1863 : graph_(graph), current_(current), end_(end)
1866 typedef typename T::const_iterator Iterator;
1868 for(Iterator vertex = graph_->excluded_.begin();
1869 current_ != end_ && *vertex;
1872 assert(current_ == end_ || !graph_->excluded_[current_]);
1875 template<
class G,
class T>
1876 SubGraph<G,T>::VertexIterator::VertexIterator(
const VertexDescriptor& current)
1880 template<
class G,
class T>
1881 inline typename SubGraph<G,T>::VertexIterator& SubGraph<G,T>::VertexIterator::increment()
1885 while(current_ != end_ && graph_->excluded_[current_])
1888 assert(current_ == end_ || !graph_->excluded_[current_]);
1892 template<
class G,
class T>
1893 inline bool SubGraph<G,T>::VertexIterator::equals(
const VertexIterator & other)
const
1895 return current_==other.current_;
1898 template<
class G,
class T>
1899 inline const typename G::VertexDescriptor& SubGraph<G,T>::VertexIterator::dereference()
const
1904 template<
class G,
class T>
1905 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::VertexIterator::begin()
const
1907 return graph_->beginEdges(current_);
1910 template<
class G,
class T>
1911 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::VertexIterator::end()
const
1913 return graph_->endEdges(current_);
1916 template<
class G,
class T>
1917 inline typename SubGraph<G,T>::VertexIterator SubGraph<G,T>::begin()
const
1919 return VertexIterator(
this, 0, endVertex_);
1923 template<
class G,
class T>
1924 inline typename SubGraph<G,T>::VertexIterator SubGraph<G,T>::end()
const
1926 return VertexIterator(endVertex_);
1930 template<
class G,
class T>
1931 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::beginEdges(
const VertexDescriptor& source)
const
1933 return EdgeIterator(source, edges_+start_[source]);
1936 template<
class G,
class T>
1937 inline typename SubGraph<G,T>::EdgeIterator SubGraph<G,T>::endEdges(
const VertexDescriptor& source)
const
1939 return EdgeIterator(edges_+end_[source]);
1942 template<
class G,
class T>
1943 std::size_t SubGraph<G,T>::noVertices()
const
1948 template<
class G,
class T>
1949 inline typename SubGraph<G,T>::VertexDescriptor SubGraph<G,T>::maxVertex()
const
1954 template<
class G,
class T>
1955 inline std::size_t SubGraph<G,T>::noEdges()
const
1960 template<
class G,
class T>
1961 inline typename SubGraph<G,T>::EdgeDescriptor SubGraph<G,T>::findEdge(
const VertexDescriptor& source,
1962 const VertexDescriptor& target)
const
1964 const EdgeDescriptor edge = std::lower_bound(edges_+start_[source], edges_+end_[source], target);
1965 if(edge==edges_+end_[source] || *edge!=target)
1966 return std::numeric_limits<EdgeDescriptor>::max();
1971 template<
class G,
class T>
1972 SubGraph<G,T>::~SubGraph()
1979 template<
class G,
class T>
1980 SubGraph<G,T>::SubGraph(
const G& graph,
const T& excluded)
1981 : excluded_(excluded), noVertices_(0), endVertex_(0), maxVertex_(graph.maxVertex())
1983 start_ =
new std::ptrdiff_t[graph.noVertices()];
1984 end_ =
new std::ptrdiff_t[graph.noVertices()];
1985 edges_ =
new VertexDescriptor[graph.noEdges()];
1987 VertexDescriptor* edge=edges_;
1989 typedef typename Graph::ConstVertexIterator Iterator;
1990 Iterator endVertex=graph.end();
1992 for(Iterator vertex = graph.begin(); vertex != endVertex; ++vertex)
1993 if(excluded_[*vertex])
1994 start_[*vertex]=end_[*vertex]=-1;
1997 endVertex_ = std::max(*vertex, endVertex_);
1999 start_[*vertex] = edge-edges_;
2001 typedef typename Graph::ConstEdgeIterator Iterator;
2002 Iterator endEdge = vertex.end();
2004 for(Iterator iter=vertex.begin(); iter!= endEdge; ++iter)
2005 if(!excluded[iter.target()]) {
2006 *edge = iter.target();
2010 end_[*vertex] = edge - edges_;
2013 std::sort(edges_+start_[*vertex], edge);
2015 noEdges_ = edge-edges_;
2019 template<
class G,
class V,
class VM>
2020 inline std::size_t VertexPropertiesGraph<G,V,VM>::noEdges()
const
2022 return graph_.noEdges();
2025 template<
class G,
class V,
class VM>
2026 inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2027 VertexPropertiesGraph<G,V,VM>::beginEdges(
const VertexDescriptor& source)
2029 return graph_.beginEdges(source);
2032 template<
class G,
class V,
class VM>
2033 inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2034 VertexPropertiesGraph<G,V,VM>::endEdges(
const VertexDescriptor& source)
2036 return graph_.endEdges(source);
2039 template<
class G,
class V,
class VM>
2040 typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2041 inline VertexPropertiesGraph<G,V,VM>::beginEdges(
const VertexDescriptor& source)
const
2043 return graph_.beginEdges(source);
2046 template<
class G,
class V,
class VM>
2047 typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2048 VertexPropertiesGraph<G,V,VM>::endEdges(
const VertexDescriptor& source)
const
2050 return graph_.endEdges(source);
2053 template<
class G,
class V,
class VM>
2055 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2056 ::VertexIteratorT(
const Father& iter,
2058 : Father(iter), graph_(graph)
2061 template<
class G,
class V,
class VM>
2063 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2064 ::VertexIteratorT(
const Father& iter)
2068 template<
class G,
class V,
class VM>
2071 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2072 ::VertexIteratorT(
const VertexIteratorT<C1>& other)
2073 : Father(other), graph_(other.graph_)
2076 template<
class G,
class V,
class VM>
2078 typename conditional<is_same<C,typename remove_const<C>::type>::value,
2080 inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::properties()
const
2082 return graph_->getVertexProperties(Father::operator*());
2085 template<
class G,
class V,
class VM>
2087 typename conditional<is_same<typename remove_const<C>::type,
2089 typename G::EdgeIterator,
2090 typename G::ConstEdgeIterator>::type
2091 inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::begin()
const
2093 return graph_->beginEdges(Father::operator*());
2096 template<
class G,
class V,
class VM>
2098 typename conditional<is_same<typename remove_const<C>::type,
2100 typename G::EdgeIterator,
2101 typename G::ConstEdgeIterator>::type
2102 inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::end()
const
2104 return graph_->endEdges(Father::operator*());
2107 template<
class G,
class V,
class VM>
2108 inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::begin()
2110 return VertexIterator(graph_.begin(),
this);
2113 template<
class G,
class V,
class VM>
2114 inline typename VertexPropertiesGraph<G,V,VM>::VertexIterator VertexPropertiesGraph<G,V,VM>::end()
2116 return VertexIterator(graph_.end());
2120 template<
class G,
class V,
class VM>
2121 inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::begin()
const
2123 return ConstVertexIterator(graph_.begin(),
this);
2126 template<
class G,
class V,
class VM>
2127 inline typename VertexPropertiesGraph<G,V,VM>::ConstVertexIterator VertexPropertiesGraph<G,V,VM>::end()
const
2129 return ConstVertexIterator(graph_.end());
2132 template<
class G,
class V,
class VM>
2133 inline V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(
const VertexDescriptor& vertex)
2135 return vertexProperties_[vmap_[vertex]];
2138 template<
class G,
class V,
class VM>
2139 inline const V& VertexPropertiesGraph<G,V,VM>::getVertexProperties(
const VertexDescriptor& vertex)
const
2141 return vertexProperties_[vmap_[vertex]];
2144 template<
class G,
class V,
class VM>
2145 inline const G& VertexPropertiesGraph<G,V,VM>::graph()
const
2150 template<
class G,
class V,
class VM>
2151 inline std::size_t VertexPropertiesGraph<G,V,VM>::noVertices()
const
2153 return graph_.noVertices();
2157 template<
class G,
class V,
class VM>
2158 inline typename VertexPropertiesGraph<G,V,VM>::VertexDescriptor VertexPropertiesGraph<G,V,VM>::maxVertex()
const
2160 return graph_.maxVertex();
2163 template<
class G,
class V,
class VM>
2164 VertexPropertiesGraph<G,V,VM>::VertexPropertiesGraph(Graph& graph,
const VM vmap)
2165 : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V())
2168 template<
class G,
class V,
class E,
class VM,
class EM>
2170 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(
const Father& iter,
2172 : Father(iter), graph_(graph)
2175 template<
class G,
class V,
class E,
class VM,
class EM>
2177 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(
const Father& iter)
2181 template<
class G,
class V,
class E,
class VM,
class EM>
2184 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(
const EdgeIteratorT<C1>& other)
2185 : Father(other), graph_(other.graph_)
2189 template<
class G,
class V,
class E,
class VM,
class EM>
2190 inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noEdges()
const
2192 return graph_.noEdges();
2195 template<
class G,
class V,
class E,
class VM,
class EM>
2197 inline typename conditional<is_same<C,typename remove_const<C>::type>::value,E&,
const E&>::type
2198 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::properties()
const
2200 return graph_->getEdgeProperties(Father::operator*());
2203 template<
class G,
class V,
class E,
class VM,
class EM>
2204 inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2205 PropertiesGraph<G,V,E,VM,EM>::beginEdges(
const VertexDescriptor& source)
2207 return EdgeIterator(graph_.beginEdges(source),
this);
2210 template<
class G,
class V,
class E,
class VM,
class EM>
2211 inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2212 PropertiesGraph<G,V,E,VM,EM>::endEdges(
const VertexDescriptor& source)
2214 return EdgeIterator(graph_.endEdges(source));
2217 template<
class G,
class V,
class E,
class VM,
class EM>
2218 typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2219 inline PropertiesGraph<G,V,E,VM,EM>::beginEdges(
const VertexDescriptor& source)
const
2221 return ConstEdgeIterator(graph_.beginEdges(source),
this);
2224 template<
class G,
class V,
class E,
class VM,
class EM>
2225 typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2226 PropertiesGraph<G,V,E,VM,EM>::endEdges(
const VertexDescriptor& source)
const
2228 return ConstEdgeIterator(graph_.endEdges(source));
2231 template<
class G,
class V,
class E,
class VM,
class EM>
2233 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2234 ::VertexIteratorT(
const Father& iter,
2236 : Father(iter), graph_(graph)
2239 template<
class G,
class V,
class E,
class VM,
class EM>
2241 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2242 ::VertexIteratorT(
const Father& iter)
2246 template<
class G,
class V,
class E,
class VM,
class EM>
2249 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2250 ::VertexIteratorT(
const VertexIteratorT<C1>& other)
2251 : Father(other), graph_(other.graph_)
2254 template<
class G,
class V,
class E,
class VM,
class EM>
2256 inline typename conditional<is_same<C,typename remove_const<C>::type>::value,
2258 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::properties()
const
2260 return graph_->getVertexProperties(Father::operator*());
2263 template<
class G,
class V,
class E,
class VM,
class EM>
2265 inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2266 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::begin()
const
2268 return graph_->beginEdges(Father::operator*());
2271 template<
class G,
class V,
class E,
class VM,
class EM>
2273 inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2274 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::end()
const
2276 return graph_->endEdges(Father::operator*());
2279 template<
class G,
class V,
class E,
class VM,
class EM>
2280 inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::begin()
2282 return VertexIterator(graph_.begin(),
this);
2285 template<
class G,
class V,
class E,
class VM,
class EM>
2286 inline typename PropertiesGraph<G,V,E,VM,EM>::VertexIterator PropertiesGraph<G,V,E,VM,EM>::end()
2288 return VertexIterator(graph_.end());
2292 template<
class G,
class V,
class E,
class VM,
class EM>
2293 inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::begin()
const
2295 return ConstVertexIterator(graph_.begin(),
this);
2298 template<
class G,
class V,
class E,
class VM,
class EM>
2299 inline typename PropertiesGraph<G,V,E,VM,EM>::ConstVertexIterator PropertiesGraph<G,V,E,VM,EM>::end()
const
2301 return ConstVertexIterator(graph_.end());
2304 template<
class G,
class V,
class E,
class VM,
class EM>
2305 inline V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(
const VertexDescriptor& vertex)
2307 return vertexProperties_[vmap_[vertex]];
2310 template<
class G,
class V,
class E,
class VM,
class EM>
2311 inline const V& PropertiesGraph<G,V,E,VM,EM>::getVertexProperties(
const VertexDescriptor& vertex)
const
2313 return vertexProperties_[vmap_[vertex]];
2316 template<
class G,
class V,
class E,
class VM,
class EM>
2317 inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(
const EdgeDescriptor& edge)
2319 return edgeProperties_[emap_[edge]];
2322 template<
class G,
class V,
class E,
class VM,
class EM>
2323 inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(
const EdgeDescriptor& edge)
const
2325 return edgeProperties_[emap_[edge]];
2328 template<
class G,
class V,
class E,
class VM,
class EM>
2329 inline E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(
const VertexDescriptor& source,
2330 const VertexDescriptor& target)
2332 return getEdgeProperties(graph_.findEdge(source,target));
2335 template<
class G,
class V,
class E,
class VM,
class EM>
2336 inline const E& PropertiesGraph<G,V,E,VM,EM>::getEdgeProperties(
const VertexDescriptor& source,
2337 const VertexDescriptor& target)
const
2339 return getEdgeProperties(graph_.findEdge(source,target));
2342 template<
class G,
class V,
class E,
class VM,
class EM>
2343 inline const G& PropertiesGraph<G,V,E,VM,EM>::graph()
const
2348 template<
class G,
class V,
class E,
class VM,
class EM>
2349 inline std::size_t PropertiesGraph<G,V,E,VM,EM>::noVertices()
const
2351 return graph_.noVertices();
2355 template<
class G,
class V,
class E,
class VM,
class EM>
2356 inline typename PropertiesGraph<G,V,E,VM,EM>::VertexDescriptor PropertiesGraph<G,V,E,VM,EM>::maxVertex()
const
2358 return graph_.maxVertex();
2361 template<
class G,
class V,
class E,
class VM,
class EM>
2362 PropertiesGraph<G,V,E,VM,EM>::PropertiesGraph(Graph& graph,
const VM& vmap,
const EM& emap)
2363 : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V()),
2364 emap_(emap), edgeProperties_(graph_.noEdges(), E())
2367 template<
class G,
class V>
2368 inline int visitNeighbours(
const G& graph,
const typename G::VertexDescriptor& vertex,
2371 typedef typename G::ConstEdgeIterator iterator;
2372 const iterator end = graph.endEdges(vertex);
2374 for(iterator edge = graph.beginEdges(vertex); edge != end; ++edge, ++noNeighbours)
2376 return noNeighbours;
Wrapper to access the internal vertex properties of a graph via operator[]()
Definition: graph.hh:1407
EdgeProperties & operator[](const Edge &edge) const
Get the properties associated to a vertex.
Definition: graph.hh:1440
G::EdgeProperties EdgeProperties
The type of the vertex properties.
Definition: graph.hh:1416
G::EdgeDescriptor Edge
The edge descriptor.
Definition: graph.hh:1420
GraphEdgePropertiesSelector()
Default constructor.
Definition: graph.hh:1432
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1412
GraphEdgePropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1426
Wrapper to access the internal edge properties of a graph via operator[]()
Definition: graph.hh:1359
GraphVertexPropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1378
VertexProperties & operator[](const Vertex &vertex) const
Get the properties associated to a vertex.
Definition: graph.hh:1393
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1364
G::VertexProperties VertexProperties
The type of the vertex properties.
Definition: graph.hh:1368
GraphVertexPropertiesSelector()
Default constructor.
Definition: graph.hh:1384
G::VertexDescriptor Vertex
The vertex descriptor.
Definition: graph.hh:1372
Iterator over all edges starting from a vertex.
Definition: graph.hh:93
EdgeIteratorT(const VertexDescriptor &source, const ColIterator &block, const ColIterator &end, const EdgeDescriptor &edge)
Constructor.
bool operator!=(const EdgeIteratorT< typename remove_const< C >::type > &other) const
Inequality operator.
@ isMutable
whether C is mutable.
Definition: graph.hh:110
VertexDescriptor target() const
The index of the target vertex of the current edge.
EdgeIteratorT< C > & operator++()
preincrement operator.
const remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:103
remove_const< C >::type MutableContainer
The mutable type of the container type.
Definition: graph.hh:99
conditional< isMutable &&C::mutableMatrix, typenameM::block_type, consttypenameM::block_type >::type Weight
The matrix block type we use as weights.
Definition: graph.hh:125
EdgeIteratorT(const EdgeIteratorT< C1 > &other)
Copy Constructor.
bool operator==(const EdgeIteratorT< const typename remove_const< C >::type > &other) const
Equality operator.
WeightType & weight() const
Access the edge weight.
VertexDescriptor source() const
The index of the source vertex of the current edge.
EdgeIteratorT(const ColIterator &block)
Constructor for the end iterator.
bool operator!=(const EdgeIteratorT< const typename remove_const< C >::type > &other) const
Inequality operator.
const EdgeDescriptor & operator*() const
Get the edge descriptor.
conditional< isMutable &&C::mutableMatrix, typenameMatrix::row_type::Iterator, typenameMatrix::row_type::ConstIterator >::type ColIterator
The column iterator of the matrix we use.
Definition: graph.hh:118
const EdgeDescriptor * operator->() const
Get the edge descriptor.
bool operator==(const EdgeIteratorT< typename remove_const< C >::type > &other) const
Equality operator.
The vertex iterator type of the graph.
Definition: graph.hh:207
EdgeIteratorT< C > begin() const
Get an iterator over all edges starting at the current vertex.
const VertexDescriptor & operator*() const
Get the descriptor of the current vertex.
WeightType & weight() const
Access the weight of the vertex.
VertexIteratorT(C *graph, const VertexDescriptor ¤t)
Constructor.
remove_const< C >::type MutableContainer
The mutable type of the container type.
Definition: graph.hh:212
bool operator!=(const VertexIteratorT< MutableContainer > &other) const
Inequality operator.
bool operator==(const VertexIteratorT< MutableContainer > &other) const
Equality operator.
VertexIteratorT< C > & operator++()
Move to the next vertex.
EdgeIteratorT< C > end() const
Get an iterator over all edges starting at the current vertex.
const remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:216
bool operator==(const VertexIteratorT< ConstContainer > &other) const
Equality operator.
bool operator!=(const VertexIteratorT< ConstContainer > &other) const
Inequality operator.
@ isMutable
whether C is mutable.
Definition: graph.hh:223
VertexIteratorT(const VertexDescriptor ¤t)
Constructor for the end iterator.
The (undirected) graph of a matrix.
Definition: graph.hh:49
MatrixGraph(Matrix &matrix)
Constructor.
VertexIterator end()
Get an iterator over the vertices.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
M Matrix
The type of the matrix we are a graph for.
Definition: graph.hh:54
ConstVertexIterator begin() const
Get an iterator over the vertices.
VertexIteratorT< const MatrixGraph< Matrix > > ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:306
~MatrixGraph()
Destructor.
std::ptrdiff_t EdgeDescriptor
The edge descriptor.
Definition: graph.hh:78
ConstEdgeIterator endEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
remove_const< M >::type MutableMatrix
The mutable type of the matrix we are a graph for.
Definition: graph.hh:59
M::size_type VertexDescriptor
The vertex descriptor.
Definition: graph.hh:71
const Matrix & matrix() const
Get the underlying matrix.
ConstEdgeIterator beginEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
ConstVertexIterator end() const
Get an iterator over the vertices.
EdgeIteratorT< const MatrixGraph< Matrix > > ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:296
EdgeIterator beginEdges(const VertexDescriptor &source)
Get an iterator over the edges starting at a vertex.
std::size_t noVertices() const
Get the number of vertices in the graph.
EdgeDescriptor findEdge(const VertexDescriptor &source, const VertexDescriptor &target) const
Find the descriptor of an edge.
M::block_type Weight
The type of the weights.
Definition: graph.hh:64
EdgeIteratorT< MatrixGraph< Matrix > > EdgeIterator
The mutable edge iterator type.
Definition: graph.hh:301
VertexIteratorT< MatrixGraph< Matrix > > VertexIterator
The mutable vertex iterator type.
Definition: graph.hh:311
EdgeIterator endEdges(const VertexDescriptor &source)
Get an iterator over the edges starting at a vertex.
std::size_t noEdges() const
Get the number of edges in the graph.
Matrix & matrix()
Get the underlying matrix.
VertexIterator begin()
Get an iterator over the vertices.
Attaches properties to the edges and vertices of a graph.
Definition: graph.hh:976
EdgeIteratorT< PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > EdgeIterator
The type of the mutable edge iterator.
Definition: graph.hh:1094
std::size_t noVertices() const
Get the number of vertices in the graph.
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:991
const EdgeProperties & getEdgeProperties(const VertexDescriptor &source, const VertexDescriptor &target) const
Get the properties associated with a edge.
const EdgeProperties & getEdgeProperties(const EdgeDescriptor &edge) const
Get the properties associated with a edge.
const Graph & graph() const
Get the graph the properties are attached to.
EdgeIteratorT< const PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > ConstEdgeIterator
The type of the constant edge iterator.
Definition: graph.hh:1101
VertexIteratorT< PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > VertexIterator
The type of the mutable Vertex iterator.
Definition: graph.hh:1210
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
G Graph
The graph we attach properties to.
Definition: graph.hh:981
EM EdgeMap
The type of the map for converting the EdgeDescriptor to std::size_t.
Definition: graph.hh:1028
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:1009
VertexIteratorT< const PropertiesGraph< Graph, VertexProperties, EdgeProperties, VM, EM > > ConstVertexIterator
The type of the constant Vertex iterator.
Definition: graph.hh:1217
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:996
std::size_t noEdges() const
Get the number of edges in the graph.
EP EdgeProperties
The type of the properties of the edges;.
Definition: graph.hh:1014
EdgeProperties & getEdgeProperties(const VertexDescriptor &source, const VertexDescriptor &target)
Get the properties associated with a edge.
EdgeProperties & getEdgeProperties(const EdgeDescriptor &edge)
Get the properties associated with a edge.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:986
PropertiesGraph(Graph &graph, const VertexMap &vmap=VertexMap(), const EdgeMap &emap=EdgeMap())
Constructor.
An index map for mapping the edges to indices.
Definition: graph.hh:468
EdgeIndexMap(const EdgeIndexMap &emap)
Protect copy construction.
Definition: graph.hh:477
The edge iterator of the graph.
Definition: graph.hh:503
const EdgeDescriptor & dereference() const
The descriptor of the current edge.
EdgeIterator(const EdgeDescriptor &edge)
Constructor for the end iterator.
bool equals(const EdgeIterator &other) const
Equality operator.
EdgeIterator & increment()
Preincrement operator.
const VertexDescriptor & target() const
The index of the target vertex of the current edge.
const VertexDescriptor & source() const
The index of the source vertex of the current edge.
EdgeIterator & decrement()
Preincrement operator.
EdgeIterator(const VertexDescriptor &source, const EdgeDescriptor &edge)
Constructor.
The vertex iterator of the graph.
Definition: graph.hh:558
VertexIterator(const VertexDescriptor ¤t)
Constructor for end iterator.
VertexIterator & increment()
Preincrement operator.
EdgeIterator begin() const
Get an iterator over all edges starting at the current vertex.
bool equals(const VertexIterator &other) const
Equality iterator.
VertexIterator(const SubGraph< G, T > *graph, const VertexDescriptor ¤t, const VertexDescriptor &end)
Constructor.
EdgeIterator end() const
Get an iterator over all edges starting at the current vertex.
const VertexDescriptor & dereference() const
Get the descriptor of the current vertex.
A subgraph of a graph.
Definition: graph.hh:441
EdgeDescriptor findEdge(const VertexDescriptor &source, const VertexDescriptor &target) const
Find the descriptor of an edge.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
EdgeIndexMap getEdgeIndexMap()
Get an edge index map for the graph.
std::size_t noEdges() const
Get the number of edges in the graph.
ConstEdgeIterator endEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
ConstVertexIterator end() const
Get an iterator over the vertices.
ConstEdgeIterator beginEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
std::size_t noVertices() const
Get the number of vertices in the graph.
T Excluded
Random access container providing information about which vertices are excluded.
Definition: graph.hh:452
EdgeIterator ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:616
G Graph
The type of the graph we are a sub graph for.
Definition: graph.hh:446
VertexIterator ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:621
SubGraph(const Graph &graph, const T &excluded)
Constructor.
ConstVertexIterator begin() const
Get an iterator over the vertices.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:457
Attaches properties to the vertices of a graph.
Definition: graph.hh:721
VertexIterator end()
Get an iterator over the vertices.
const Graph & graph() const
Get the graph the properties are attached to.
Graph::ConstEdgeIterator ConstEdgeIterator
The type of the constant edge iterator.
Definition: graph.hh:764
VertexProperties & getVertexProperties(const VertexDescriptor &vertex)
Get the properties associated with a vertex.
std::size_t noEdges() const
Get the number of edges in the graph.
VertexIteratorT< const VertexPropertiesGraph< Graph, VertexProperties, VM > > ConstVertexIterator
The type of the constant Vertex iterator.
Definition: graph.hh:887
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:736
ConstEdgeIterator endEdges(const VertexDescriptor &source) const
Get the mutable edge iterator over edges starting at a vertex.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:731
G Graph
The graph we attach properties to.
Definition: graph.hh:726
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:754
EdgeIterator endEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
EdgeIterator beginEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:741
std::size_t noVertices() const
Get the number of vertices in the graph.
ConstEdgeIterator beginEdges(const VertexDescriptor &source) const
Get the mutable edge iterator over edges starting at a vertex.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
VertexIteratorT< VertexPropertiesGraph< Graph, VertexProperties, VM > > VertexIterator
The type of the mutable Vertex iterator.
Definition: graph.hh:881
VertexIterator begin()
Get an iterator over the vertices.
Graph::EdgeIterator EdgeIterator
The type of the mutable edge iterator.
Definition: graph.hh:759
block_vector_unmanaged< B, A >::Iterator Iterator
make iterators available as types
Definition: bvector.hh:608
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:141
derive error class from the base class in common
Definition: istlexception.hh:16
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:430
Iterator implementation class
Definition: basearray.hh:80
#define DUNE_THROW(E, m)
Definition: exceptions.hh:243
int visitNeighbours(const G &graph, const typename G::VertexDescriptor &vertex, V &visitor)
Visit all neighbour vertices of a vertex in a graph.
EnableIfInterOperable< T1, T2, bool >::type operator==(const ForwardIteratorFacade< T1, V1, R1, D > &lhs, const ForwardIteratorFacade< T2, V2, R2, D > &rhs)
Checks for equality.
Definition: iteratorfacades.hh:230
EnableIfInterOperable< T1, T2, bool >::type operator!=(const ForwardIteratorFacade< T1, V1, R1, D > &lhs, const ForwardIteratorFacade< T2, V2, R2, D > &rhs)
Checks for inequality.
Definition: iteratorfacades.hh:252
This file implements iterator facade classes for writing stl conformant iterators.
Dune namespace.
Definition: alignment.hh:10
Tag for the category of readable property maps.
Definition: propertymap.hh:37
Traits for type conversions and type information.