3 #ifndef DUNE_AMG_GRAPH_HH
4 #define DUNE_AMG_GRAPH_HH
11 #include <dune/common/typetraits.hh>
12 #include <dune/common/iteratorfacades.hh>
14 #include <dune/common/propertymap.hh>
64 typedef typename M::block_type
Weight;
84 mutableMatrix = std::is_same<M, typename std::remove_const<M>::type>::value
116 typedef typename std::conditional<
isMutable && C::mutableMatrix,
typename Matrix::row_type::Iterator,
117 typename Matrix::row_type::ConstIterator>::type
123 typedef typename std::conditional<
isMutable && C::mutableMatrix,
typename M::block_type,
124 const typename M::block_type>::type
152 typedef typename std::conditional<std::is_same<C, typename std::remove_const<C>::type>::value && C::mutableMatrix,
153 typename M::block_type,
const typename M::block_type>::type
262 typedef typename std::conditional<std::is_same<C, typename std::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_)
483 return edge-firstEdge_;
502 class EdgeIterator :
public RandomAccessIteratorFacade<EdgeIterator,const EdgeDescriptor>
557 :
public ForwardIteratorFacade<VertexIterator,const VertexDescriptor>
694 std::size_t noVertices_;
707 std::ptrdiff_t* start_;
709 std::ptrdiff_t* end_;
719 template<
class G,
class VP,
class VM=IdentityMap>
797 :
public std::conditional<std::is_same<typename std::remove_const<C>::type,
799 typename Graph::VertexIterator,
800 typename Graph::ConstVertexIterator>::type
808 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
810 typename Graph::VertexIterator,
811 typename Graph::ConstVertexIterator>::type
817 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
819 typename Graph::EdgeIterator,
820 typename Graph::ConstEdgeIterator>::type
851 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
853 const VertexProperties&>::type
967 std::vector<VertexProperties> vertexProperties_;
974 template<
class G,
class VP,
class EP,
class VM=IdentityMap,
class EM=IdentityMap>
1032 :
public std::conditional<std::is_same<typename std::remove_const<C>::type,
1034 typename Graph::EdgeIterator,
1035 typename Graph::ConstEdgeIterator>::type
1044 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
1046 typename Graph::EdgeIterator,
1047 typename Graph::ConstEdgeIterator>::type
1077 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
1079 const EdgeProperties&>::type
1134 :
public std::conditional<std::is_same<typename std::remove_const<C>::type,
1136 typename Graph::VertexIterator,
1137 typename Graph::ConstVertexIterator>::type
1145 typedef typename std::conditional<std::is_same<typename std::remove_const<C>::type,
1147 typename Graph::VertexIterator,
1148 typename Graph::ConstVertexIterator>::type
1179 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
1181 const VertexProperties&>::type
1264 const VertexDescriptor& target)
1266 return graph_.findEdge(source,target);
1333 const EdgeMap& emap=EdgeMap());
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())
1470 DUNE_THROW(
ISTLError,
"Matrix has to have as many columns as rows!");
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();
1490 return start_[matrix_.N()];
1502 return matrix_.N()-1;
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;
1538 const ColIterator& end,
const EdgeDescriptor& edge)
1539 : source_(source), block_(block), blockEnd_(end), edge_(edge)
1541 if(block_!=blockEnd_ && block_.index() == source_) {
1557 : source_(other.source_), block_(other.block_), blockEnd_(other.blockEnd_), edge_(other.edge_)
1563 inline typename MatrixGraph<M>::template EdgeIteratorT<C>::WeightType&
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_;
1616 return block_.index();
1643 const VertexDescriptor& current)
1644 : graph_(graph), current_(current)
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_;
1699 inline typename MatrixGraph<M>::template VertexIteratorT<C>::WeightType&
1702 return graph_->matrix()[current_][current_];
1715 inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1718 return graph_->beginEdges(current_);
1723 inline typename MatrixGraph<M>::template EdgeIteratorT<C>
1726 return graph_->endEdges(current_);
1730 inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1733 return VertexIterator(
this,0);
1737 inline typename MatrixGraph<M>::template VertexIteratorT<MatrixGraph<M> >
1740 return VertexIterator(matrix_.N());
1745 inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1748 return ConstVertexIterator(
this, 0);
1752 inline typename MatrixGraph<M>::template VertexIteratorT<const MatrixGraph<M> >
1755 return ConstVertexIterator(matrix_.N());
1759 inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1762 return EdgeIterator(source, matrix_.operator[](source).begin(),
1763 matrix_.operator[](source).end(), start_[source]);
1767 inline typename MatrixGraph<M>::template EdgeIteratorT<MatrixGraph<M> >
1770 return EdgeIterator(matrix_.operator[](source).end());
1775 inline typename MatrixGraph<M>::template EdgeIteratorT<const MatrixGraph<M> >
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> >
1786 return ConstEdgeIterator(matrix_.operator[](source).end());
1790 template<
class G,
class T>
1792 const EdgeDescriptor& edge)
1793 : source_(source), edge_(edge)
1797 template<
class G,
class T>
1802 template<
class G,
class T>
1805 return EdgeIndexMap(edges_);
1808 template<
class G,
class T>
1811 return other.edge_==edge_;
1814 template<
class G,
class T>
1821 template<
class G,
class T>
1828 template<
class G,
class T>
1834 template<
class G,
class T>
1840 template<
class G,
class T>
1847 template<
class G,
class T>
1853 template<
class G,
class T>
1856 return other.edge_-edge_;
1859 template<
class G,
class T>
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>
1880 template<
class G,
class T>
1885 while(current_ != end_ && graph_->excluded_[current_])
1888 assert(current_ == end_ || !graph_->excluded_[current_]);
1892 template<
class G,
class T>
1895 return current_==other.current_;
1898 template<
class G,
class T>
1904 template<
class G,
class T>
1907 return graph_->beginEdges(current_);
1910 template<
class G,
class T>
1913 return graph_->endEdges(current_);
1916 template<
class G,
class T>
1919 return VertexIterator(
this, 0, endVertex_);
1923 template<
class G,
class T>
1926 return VertexIterator(endVertex_);
1930 template<
class G,
class T>
1933 return EdgeIterator(source, edges_+start_[source]);
1936 template<
class G,
class T>
1939 return EdgeIterator(edges_+end_[source]);
1942 template<
class G,
class T>
1948 template<
class G,
class T>
1954 template<
class G,
class T>
1960 template<
class G,
class T>
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>
1979 template<
class G,
class T>
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_;
1991 if ( graph.noVertices() == 0)
1994 typedef typename Graph::ConstVertexIterator Iterator;
1995 Iterator endVertex=graph.end();
1997 for(Iterator vertex = graph.begin(); vertex != endVertex; ++vertex)
1998 if(excluded_[*vertex])
1999 start_[*vertex]=end_[*vertex]=-1;
2002 endVertex_ = std::max(*vertex, endVertex_);
2004 start_[*vertex] = edge-edges_;
2006 typedef typename Graph::ConstEdgeIterator Iterator;
2007 Iterator endEdge = vertex.end();
2009 for(Iterator iter=vertex.begin(); iter!= endEdge; ++iter)
2010 if(!excluded[iter.target()]) {
2011 *edge = iter.target();
2015 end_[*vertex] = edge - edges_;
2018 std::sort(edges_+start_[*vertex], edge);
2020 noEdges_ = edge-edges_;
2024 template<
class G,
class V,
class VM>
2027 return graph_.noEdges();
2030 template<
class G,
class V,
class VM>
2034 return graph_.beginEdges(source);
2037 template<
class G,
class V,
class VM>
2041 return graph_.endEdges(source);
2044 template<
class G,
class V,
class VM>
2048 return graph_.beginEdges(source);
2051 template<
class G,
class V,
class VM>
2055 return graph_.endEdges(source);
2058 template<
class G,
class V,
class VM>
2063 : Father(iter), graph_(graph)
2066 template<
class G,
class V,
class VM>
2073 template<
class G,
class V,
class VM>
2078 : Father(other), graph_(other.graph_)
2081 template<
class G,
class V,
class VM>
2083 typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
2087 return graph_->getVertexProperties(Father::operator*());
2090 template<
class G,
class V,
class VM>
2092 typename std::conditional<std::is_same<typename std::remove_const<C>::type,
2094 typename G::EdgeIterator,
2095 typename G::ConstEdgeIterator>::type
2098 return graph_->beginEdges(Father::operator*());
2101 template<
class G,
class V,
class VM>
2103 typename std::conditional<std::is_same<typename std::remove_const<C>::type,
2105 typename G::EdgeIterator,
2106 typename G::ConstEdgeIterator>::type
2109 return graph_->endEdges(Father::operator*());
2112 template<
class G,
class V,
class VM>
2115 return VertexIterator(graph_.begin(),
this);
2118 template<
class G,
class V,
class VM>
2121 return VertexIterator(graph_.end());
2125 template<
class G,
class V,
class VM>
2128 return ConstVertexIterator(graph_.begin(),
this);
2131 template<
class G,
class V,
class VM>
2134 return ConstVertexIterator(graph_.end());
2137 template<
class G,
class V,
class VM>
2140 return vertexProperties_[vmap_[vertex]];
2143 template<
class G,
class V,
class VM>
2146 return vertexProperties_[vmap_[vertex]];
2149 template<
class G,
class V,
class VM>
2155 template<
class G,
class V,
class VM>
2158 return graph_.noVertices();
2162 template<
class G,
class V,
class VM>
2165 return graph_.maxVertex();
2168 template<
class G,
class V,
class VM>
2170 : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V())
2173 template<
class G,
class V,
class E,
class VM,
class EM>
2177 : Father(iter), graph_(graph)
2180 template<
class G,
class V,
class E,
class VM,
class EM>
2186 template<
class G,
class V,
class E,
class VM,
class EM>
2190 : Father(other), graph_(other.graph_)
2194 template<
class G,
class V,
class E,
class VM,
class EM>
2197 return graph_.noEdges();
2200 template<
class G,
class V,
class E,
class VM,
class EM>
2202 inline typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,E&,
const E&>::type
2205 return graph_->getEdgeProperties(Father::operator*());
2208 template<
class G,
class V,
class E,
class VM,
class EM>
2212 return EdgeIterator(graph_.beginEdges(source),
this);
2215 template<
class G,
class V,
class E,
class VM,
class EM>
2219 return EdgeIterator(graph_.endEdges(source));
2222 template<
class G,
class V,
class E,
class VM,
class EM>
2226 return ConstEdgeIterator(graph_.beginEdges(source),
this);
2229 template<
class G,
class V,
class E,
class VM,
class EM>
2233 return ConstEdgeIterator(graph_.endEdges(source));
2236 template<
class G,
class V,
class E,
class VM,
class EM>
2241 : Father(iter), graph_(graph)
2244 template<
class G,
class V,
class E,
class VM,
class EM>
2251 template<
class G,
class V,
class E,
class VM,
class EM>
2256 : Father(other), graph_(other.graph_)
2259 template<
class G,
class V,
class E,
class VM,
class EM>
2261 inline typename std::conditional<std::is_same<C,typename std::remove_const<C>::type>::value,
2265 return graph_->getVertexProperties(Father::operator*());
2268 template<
class G,
class V,
class E,
class VM,
class EM>
2270 inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2273 return graph_->beginEdges(Father::operator*());
2276 template<
class G,
class V,
class E,
class VM,
class EM>
2278 inline typename PropertiesGraph<G,V,E,VM,EM>::template EdgeIteratorT<C>
2281 return graph_->endEdges(Father::operator*());
2284 template<
class G,
class V,
class E,
class VM,
class EM>
2287 return VertexIterator(graph_.begin(),
this);
2290 template<
class G,
class V,
class E,
class VM,
class EM>
2293 return VertexIterator(graph_.end());
2297 template<
class G,
class V,
class E,
class VM,
class EM>
2300 return ConstVertexIterator(graph_.begin(),
this);
2303 template<
class G,
class V,
class E,
class VM,
class EM>
2306 return ConstVertexIterator(graph_.end());
2309 template<
class G,
class V,
class E,
class VM,
class EM>
2312 return vertexProperties_[vmap_[vertex]];
2315 template<
class G,
class V,
class E,
class VM,
class EM>
2318 return vertexProperties_[vmap_[vertex]];
2321 template<
class G,
class V,
class E,
class VM,
class EM>
2324 return edgeProperties_[emap_[edge]];
2327 template<
class G,
class V,
class E,
class VM,
class EM>
2330 return edgeProperties_[emap_[edge]];
2333 template<
class G,
class V,
class E,
class VM,
class EM>
2335 const VertexDescriptor& target)
2337 return getEdgeProperties(graph_.findEdge(source,target));
2340 template<
class G,
class V,
class E,
class VM,
class EM>
2342 const VertexDescriptor& target)
const
2344 return getEdgeProperties(graph_.findEdge(source,target));
2347 template<
class G,
class V,
class E,
class VM,
class EM>
2353 template<
class G,
class V,
class E,
class VM,
class EM>
2356 return graph_.noVertices();
2360 template<
class G,
class V,
class E,
class VM,
class EM>
2363 return graph_.maxVertex();
2366 template<
class G,
class V,
class E,
class VM,
class EM>
2368 : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V()),
2369 emap_(emap), edgeProperties_(graph_.noEdges(), E())
2372 template<
class G,
class V>
2373 inline int visitNeighbours(
const G& graph,
const typename G::VertexDescriptor& vertex,
2376 typedef typename G::ConstEdgeIterator iterator;
2377 const iterator end = graph.endEdges(vertex);
2379 for(iterator edge = graph.beginEdges(vertex); edge != end; ++edge, ++noNeighbours)
2381 return noNeighbours;