4 #ifndef DUNE_AMG_GRAPH_HH
5 #define DUNE_AMG_GRAPH_HH
12 #include <dune/common/typetraits.hh>
13 #include <dune/common/iteratorfacades.hh>
15 #include <dune/common/propertymap.hh>
65 typedef typename M::block_type
Weight;
118 typename Matrix::row_type::ConstIterator>
::type
125 const typename M::block_type>
::type
154 typename M::block_type,
const typename M::block_type>
::type
264 typename M::block_type,
const typename M::block_type>
::type
440 template<
class G,
class T>
474 : firstEdge_(firstEdge)
479 : firstEdge_(emap.firstEdge_)
484 return edge-firstEdge_;
503 class EdgeIterator :
public RandomAccessIteratorFacade<EdgeIterator,const EdgeDescriptor>
558 :
public ForwardIteratorFacade<VertexIterator,const VertexDescriptor>
695 std::size_t noVertices_;
708 std::ptrdiff_t* start_;
710 std::ptrdiff_t* end_;
720 template<
class G,
class VP,
class VM=IdentityMap>
798 :
public conditional<is_same<typename remove_const<C>::type,
800 typename Graph::VertexIterator,
801 typename Graph::ConstVertexIterator>
::type
809 typedef typename conditional<is_same<typename remove_const<C>::type,
811 typename Graph::VertexIterator,
812 typename Graph::ConstVertexIterator>
::type
818 typedef typename conditional<is_same<typename remove_const<C>::type,
820 typename Graph::EdgeIterator,
821 typename Graph::ConstEdgeIterator>
::type
852 typename conditional<is_same<C,typename remove_const<C>::type>::value,
854 const VertexProperties&>
::type
968 std::vector<VertexProperties> vertexProperties_;
975 template<
class G,
class VP,
class EP,
class VM=IdentityMap,
class EM=IdentityMap>
1033 :
public conditional<is_same<typename remove_const<C>::type,
1035 typename Graph::EdgeIterator,
1036 typename Graph::ConstEdgeIterator>
::type
1045 typedef typename conditional<is_same<typename remove_const<C>::type,
1047 typename Graph::EdgeIterator,
1048 typename Graph::ConstEdgeIterator>
::type
1078 typename conditional<is_same<C,typename remove_const<C>::type>::value,
1080 const EdgeProperties&>
::type
1135 :
public conditional<is_same<typename remove_const<C>::type,
1137 typename Graph::VertexIterator,
1138 typename Graph::ConstVertexIterator>
::type
1146 typedef typename conditional<is_same<typename remove_const<C>::type,
1148 typename Graph::VertexIterator,
1149 typename Graph::ConstVertexIterator>
::type
1180 typename conditional<is_same<C,typename remove_const<C>::type>::value,
1182 const VertexProperties&>
::type
1265 const VertexDescriptor& target)
1267 return graph_.findEdge(source,target);
1334 const EdgeMap& emap=EdgeMap());
1345 std::vector<VertexProperties> vertexProperties_;
1349 std::vector<EdgeProperties> edgeProperties_;
1358 template<
typename G>
1396 return graph_->getVertexProperties(vertex);
1406 template<
typename G>
1421 typedef typename G::EdgeDescriptor
Edge;
1443 return graph_->getEdgeProperties(edge);
1460 template<
class G,
class V>
1461 int visitNeighbours(
const G& graph,
const typename G::VertexDescriptor& vertex,
1467 MatrixGraph<M>::MatrixGraph(M& matrix)
1470 if(matrix_.N()!=matrix_.M())
1471 DUNE_THROW(
ISTLError,
"Matrix has to have as many columns as rows!");
1473 start_ =
new EdgeDescriptor[matrix_.N()+1];
1475 typedef typename M::ConstIterator Iterator;
1476 Iterator
row = matrix_.begin();
1477 start_[row.index()] = 0;
1479 for(Iterator row=matrix_.begin(); row != matrix_.end(); ++
row)
1480 start_[row.index()+1] = start_[row.index()] + row->size();
1492 return start_[matrix_.N()];
1504 return matrix_.N()-1;
1508 typename MatrixGraph<M>::EdgeDescriptor
1510 const VertexDescriptor& target)
const
1512 typename M::ConstColIterator found =matrix_[source].find(target);
1513 if(found == matrix_[source].end())
1514 return std::numeric_limits<EdgeDescriptor>::max();
1515 std::size_t offset = found.offset();
1519 assert(offset<noEdges());
1521 return start_[source]+offset;
1539 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(
const VertexDescriptor& source,
const ColIterator& block,
1540 const ColIterator& end,
const EdgeDescriptor& edge)
1541 : source_(source), block_(block), blockEnd_(end), edge_(edge)
1543 if(block_!=blockEnd_ && block_.index() == source_) {
1551 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(
const ColIterator& block)
1558 MatrixGraph<M>::EdgeIteratorT<C>::EdgeIteratorT(
const EdgeIteratorT<C1>& other)
1559 : source_(other.source_), block_(other.block_), blockEnd_(other.blockEnd_), edge_(other.edge_)
1565 inline typename MatrixGraph<M>::template EdgeIteratorT<C>::WeightType&
1566 MatrixGraph<M>::EdgeIteratorT<C>::weight()
const
1573 inline typename MatrixGraph<M>::template EdgeIteratorT<C>& MatrixGraph<M>::EdgeIteratorT<C>::operator++()
1578 if(block_!=blockEnd_ && block_.index() == source_) {
1588 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(
const typename MatrixGraph<M>::template EdgeIteratorT<
typename remove_const<C>::type>& other)
const
1590 return block_!=other.block_;
1595 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(
const typename MatrixGraph<M>::template EdgeIteratorT<
const typename remove_const<C>::type>& other)
const
1597 return block_!=other.block_;
1602 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator==(
const typename MatrixGraph<M>::template EdgeIteratorT<
typename remove_const<C>::type>& other)
const
1604 return block_==other.block_;
1609 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator==(
const typename MatrixGraph<M>::template EdgeIteratorT<
const typename remove_const<C>::type>& other)
const
1611 return block_==other.block_;
1616 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::target()
const
1618 return block_.index();
1623 inline typename MatrixGraph<M>::VertexDescriptor MatrixGraph<M>::EdgeIteratorT<C>::source()
const
1630 inline const typename MatrixGraph<M>::EdgeDescriptor& MatrixGraph<M>::EdgeIteratorT<C>::operator*()
const
1637 inline const typename MatrixGraph<M>::EdgeDescriptor* MatrixGraph<M>::EdgeIteratorT<C>::operator->()
const
1644 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(C* graph,
1645 const VertexDescriptor& current)
1646 : graph_(graph), current_(current)
1652 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(
const VertexDescriptor& current)
1658 MatrixGraph<M>::VertexIteratorT<C>::VertexIteratorT(
const VertexIteratorT<MutableContainer>& other)
1659 : graph_(other.graph_), current_(other.current_)
1664 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(
const VertexIteratorT<MutableContainer>& other)
const
1666 return current_ != other.current_;
1671 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(
const VertexIteratorT<ConstContainer>& other)
const
1673 return current_ != other.current_;
1679 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(
const VertexIteratorT<MutableContainer>& other)
const
1681 return current_ == other.current_;
1686 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(
const VertexIteratorT<ConstContainer>& other)
const
1688 return current_ == other.current_;
1693 inline typename MatrixGraph<M>::template VertexIteratorT<C>& MatrixGraph<M>::VertexIteratorT<C>::operator++()
1701 inline typename MatrixGraph<M>::template VertexIteratorT<C>::WeightType&
1702 MatrixGraph<M>::VertexIteratorT<C>::weight()
const
1704 return graph_->matrix()[current_][current_];
1709 inline const typename MatrixGraph<M>::VertexDescriptor&
1710 MatrixGraph<M>::VertexIteratorT<C>::operator*()
const
1717 inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1720 return graph_->beginEdges(current_);
1725 inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1728 return graph_->endEdges(current_);
1732 inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1735 return VertexIterator(
this,0);
1739 inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1742 return VertexIterator(matrix_.N());
1747 inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1750 return ConstVertexIterator(
this, 0);
1754 inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1757 return ConstVertexIterator(matrix_.N());
1761 inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1764 return EdgeIterator(source, matrix_.operator[](source).begin(),
1765 matrix_.operator[](source).end(), start_[source]);
1769 inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1772 return EdgeIterator(matrix_.operator[](source).end());
1777 inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
1780 return ConstEdgeIterator(source, matrix_.operator[](source).begin(),
1781 matrix_.operator[](source).end(), start_[source]);
1785 inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
1788 return ConstEdgeIterator(matrix_.operator[](source).end());
1792 template<
class G,
class T>
1794 const EdgeDescriptor& edge)
1795 : source_(source), edge_(edge)
1799 template<
class G,
class T>
1804 template<
class G,
class T>
1807 return EdgeIndexMap(edges_);
1810 template<
class G,
class T>
1813 return other.edge_==edge_;
1816 template<
class G,
class T>
1823 template<
class G,
class T>
1830 template<
class G,
class T>
1836 template<
class G,
class T>
1842 template<
class G,
class T>
1849 template<
class G,
class T>
1855 template<
class G,
class T>
1858 return other.edge_-edge_;
1861 template<
class G,
class T>
1865 : graph_(graph), current_(current), end_(end)
1868 typedef typename T::const_iterator Iterator;
1870 for(Iterator vertex = graph_->excluded_.begin();
1871 current_ != end_ && *vertex;
1874 assert(current_ == end_ || !graph_->excluded_[current_]);
1877 template<
class G,
class T>
1882 template<
class G,
class T>
1887 while(current_ != end_ && graph_->excluded_[current_])
1890 assert(current_ == end_ || !graph_->excluded_[current_]);
1894 template<
class G,
class T>
1897 return current_==other.current_;
1900 template<
class G,
class T>
1906 template<
class G,
class T>
1909 return graph_->beginEdges(current_);
1912 template<
class G,
class T>
1915 return graph_->endEdges(current_);
1918 template<
class G,
class T>
1921 return VertexIterator(
this, 0, endVertex_);
1925 template<
class G,
class T>
1928 return VertexIterator(endVertex_);
1932 template<
class G,
class T>
1935 return EdgeIterator(source, edges_+start_[source]);
1938 template<
class G,
class T>
1941 return EdgeIterator(edges_+end_[source]);
1944 template<
class G,
class T>
1950 template<
class G,
class T>
1956 template<
class G,
class T>
1962 template<
class G,
class T>
1966 const EdgeDescriptor edge = std::lower_bound(edges_+start_[source], edges_+end_[source], target);
1967 if(edge==edges_+end_[source] || *edge!=target)
1968 return std::numeric_limits<EdgeDescriptor>::max();
1973 template<
class G,
class T>
1981 template<
class G,
class T>
1983 : excluded_(excluded), noVertices_(0), endVertex_(0), maxVertex_(graph.
maxVertex())
1985 start_ =
new std::ptrdiff_t[graph.noVertices()];
1986 end_ =
new std::ptrdiff_t[graph.noVertices()];
1987 edges_ =
new VertexDescriptor[graph.noEdges()];
1989 VertexDescriptor* edge=edges_;
1991 typedef typename Graph::ConstVertexIterator Iterator;
1992 Iterator endVertex=graph.end();
1994 for(Iterator vertex = graph.begin(); vertex != endVertex; ++vertex)
1995 if(excluded_[*vertex])
1996 start_[*vertex]=end_[*vertex]=-1;
1999 endVertex_ = std::max(*vertex, endVertex_);
2001 start_[*vertex] = edge-edges_;
2003 typedef typename Graph::ConstEdgeIterator Iterator;
2004 Iterator endEdge = vertex.end();
2006 for(Iterator iter=vertex.begin(); iter!= endEdge; ++iter)
2007 if(!excluded[iter.target()]) {
2008 *edge = iter.target();
2012 end_[*vertex] = edge - edges_;
2015 std::sort(edges_+start_[*vertex], edge);
2017 noEdges_ = edge-edges_;
2021 template<
class G,
class V,
class VM>
2024 return graph_.noEdges();
2027 template<
class G,
class V,
class VM>
2028 inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2031 return graph_.beginEdges(source);
2034 template<
class G,
class V,
class VM>
2035 inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2038 return graph_.endEdges(source);
2041 template<
class G,
class V,
class VM>
2042 typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2045 return graph_.beginEdges(source);
2048 template<
class G,
class V,
class VM>
2049 typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2052 return graph_.endEdges(source);
2055 template<
class G,
class V,
class VM>
2057 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2058 ::VertexIteratorT(
const Father& iter,
2060 : Father(iter), graph_(graph)
2063 template<
class G,
class V,
class VM>
2065 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2066 ::VertexIteratorT(
const Father& iter)
2070 template<
class G,
class V,
class VM>
2073 VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>
2074 ::VertexIteratorT(
const VertexIteratorT<C1>& other)
2075 : Father(other), graph_(other.graph_)
2078 template<
class G,
class V,
class VM>
2082 inline VertexPropertiesGraph<G,V,VM>::VertexIteratorT<C>::properties()
const
2084 return graph_->getVertexProperties(Father::operator*());
2087 template<
class G,
class V,
class VM>
2091 typename G::EdgeIterator,
2092 typename G::ConstEdgeIterator>
::type
2095 return graph_->beginEdges(Father::operator*());
2098 template<
class G,
class V,
class VM>
2102 typename G::EdgeIterator,
2103 typename G::ConstEdgeIterator>
::type
2106 return graph_->endEdges(Father::operator*());
2109 template<
class G,
class V,
class VM>
2112 return VertexIterator(graph_.begin(),
this);
2115 template<
class G,
class V,
class VM>
2118 return VertexIterator(graph_.end());
2122 template<
class G,
class V,
class VM>
2125 return ConstVertexIterator(graph_.begin(),
this);
2128 template<
class G,
class V,
class VM>
2131 return ConstVertexIterator(graph_.end());
2134 template<
class G,
class V,
class VM>
2137 return vertexProperties_[vmap_[vertex]];
2140 template<
class G,
class V,
class VM>
2143 return vertexProperties_[vmap_[vertex]];
2146 template<
class G,
class V,
class VM>
2152 template<
class G,
class V,
class VM>
2155 return graph_.noVertices();
2159 template<
class G,
class V,
class VM>
2162 return graph_.maxVertex();
2165 template<
class G,
class V,
class VM>
2167 : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V())
2170 template<
class G,
class V,
class E,
class VM,
class EM>
2172 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(
const Father& iter,
2174 : Father(iter), graph_(graph)
2177 template<
class G,
class V,
class E,
class VM,
class EM>
2179 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(
const Father& iter)
2183 template<
class G,
class V,
class E,
class VM,
class EM>
2186 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::EdgeIteratorT(
const EdgeIteratorT<C1>& other)
2187 : Father(other), graph_(other.graph_)
2191 template<
class G,
class V,
class E,
class VM,
class EM>
2194 return graph_.noEdges();
2197 template<
class G,
class V,
class E,
class VM,
class EM>
2200 PropertiesGraph<G,V,E,VM,EM>::EdgeIteratorT<C>::properties()
const
2202 return graph_->getEdgeProperties(Father::operator*());
2205 template<
class G,
class V,
class E,
class VM,
class EM>
2206 inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2209 return EdgeIterator(graph_.beginEdges(source),
this);
2212 template<
class G,
class V,
class E,
class VM,
class EM>
2213 inline typename PropertiesGraph<G,V,E,VM,EM>::EdgeIterator
2216 return EdgeIterator(graph_.endEdges(source));
2219 template<
class G,
class V,
class E,
class VM,
class EM>
2220 typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2223 return ConstEdgeIterator(graph_.beginEdges(source),
this);
2226 template<
class G,
class V,
class E,
class VM,
class EM>
2227 typename PropertiesGraph<G,V,E,VM,EM>::ConstEdgeIterator
2230 return ConstEdgeIterator(graph_.endEdges(source));
2233 template<
class G,
class V,
class E,
class VM,
class EM>
2235 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2236 ::VertexIteratorT(
const Father& iter,
2238 : Father(iter), graph_(graph)
2241 template<
class G,
class V,
class E,
class VM,
class EM>
2243 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2244 ::VertexIteratorT(
const Father& iter)
2248 template<
class G,
class V,
class E,
class VM,
class EM>
2251 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>
2252 ::VertexIteratorT(
const VertexIteratorT<C1>& other)
2253 : Father(other), graph_(other.graph_)
2256 template<
class G,
class V,
class E,
class VM,
class EM>
2260 PropertiesGraph<G,V,E,VM,EM>::VertexIteratorT<C>::properties()
const
2262 return graph_->getVertexProperties(Father::operator*());
2265 template<
class G,
class V,
class E,
class VM,
class EM>
2267 inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2270 return graph_->beginEdges(Father::operator*());
2273 template<
class G,
class V,
class E,
class VM,
class EM>
2275 inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2278 return graph_->endEdges(Father::operator*());
2281 template<
class G,
class V,
class E,
class VM,
class EM>
2284 return VertexIterator(graph_.begin(),
this);
2287 template<
class G,
class V,
class E,
class VM,
class EM>
2290 return VertexIterator(graph_.end());
2294 template<
class G,
class V,
class E,
class VM,
class EM>
2297 return ConstVertexIterator(graph_.begin(),
this);
2300 template<
class G,
class V,
class E,
class VM,
class EM>
2303 return ConstVertexIterator(graph_.end());
2306 template<
class G,
class V,
class E,
class VM,
class EM>
2309 return vertexProperties_[vmap_[vertex]];
2312 template<
class G,
class V,
class E,
class VM,
class EM>
2315 return vertexProperties_[vmap_[vertex]];
2318 template<
class G,
class V,
class E,
class VM,
class EM>
2321 return edgeProperties_[emap_[edge]];
2324 template<
class G,
class V,
class E,
class VM,
class EM>
2327 return edgeProperties_[emap_[edge]];
2330 template<
class G,
class V,
class E,
class VM,
class EM>
2332 const VertexDescriptor& target)
2334 return getEdgeProperties(graph_.findEdge(source,target));
2337 template<
class G,
class V,
class E,
class VM,
class EM>
2339 const VertexDescriptor& target)
const
2341 return getEdgeProperties(graph_.findEdge(source,target));
2344 template<
class G,
class V,
class E,
class VM,
class EM>
2350 template<
class G,
class V,
class E,
class VM,
class EM>
2353 return graph_.noVertices();
2357 template<
class G,
class V,
class E,
class VM,
class EM>
2360 return graph_.maxVertex();
2363 template<
class G,
class V,
class E,
class VM,
class EM>
2365 : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V()),
2366 emap_(emap), edgeProperties_(graph_.noEdges(), E())
2369 template<
class G,
class V>
2370 inline int visitNeighbours(
const G& graph,
const typename G::VertexDescriptor& vertex,
2373 typedef typename G::ConstEdgeIterator iterator;
2374 const iterator end = graph.endEdges(vertex);
2376 for(iterator edge = graph.beginEdges(vertex); edge != end; ++edge, ++noNeighbours)
2378 return noNeighbours;