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;
116 typedef typename conditional<
isMutable && C::mutableMatrix,
typename Matrix::row_type::Iterator,
117 typename Matrix::row_type::ConstIterator>::type
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
177 VertexDescriptor
target()
const;
180 VertexDescriptor
source()
const;
190 VertexDescriptor source_;
199 EdgeDescriptor edge_;
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
272 const VertexDescriptor&
operator*()
const;
290 VertexDescriptor current_;
328 VertexIterator
begin();
334 VertexIterator
end();
340 ConstVertexIterator
begin()
const;
346 ConstVertexIterator
end()
const;
354 EdgeIterator
beginEdges(
const VertexDescriptor& source);
362 EdgeIterator
endEdges(
const VertexDescriptor& source);
371 ConstEdgeIterator
beginEdges(
const VertexDescriptor& source)
const;
379 ConstEdgeIterator
endEdges(
const VertexDescriptor& source)
const;
391 const Matrix&
matrix()
const;
417 EdgeDescriptor
findEdge(
const VertexDescriptor& source,
418 const VertexDescriptor& target)
const;
424 EdgeDescriptor* start_;
439 template<
class G,
class T>
473 : firstEdge_(firstEdge)
478 : firstEdge_(emap.firstEdge_)
483 return edge-firstEdge_;
487 EdgeDescriptor firstEdge_;
502 class EdgeIterator :
public RandomAccessIteratorFacade<EdgeIterator,const EdgeDescriptor>
536 const VertexDescriptor&
target()
const;
539 const VertexDescriptor&
source()
const;
545 VertexDescriptor source_;
550 EdgeDescriptor edge_;
557 :
public ForwardIteratorFacade<VertexIterator,const VertexDescriptor>
567 const VertexDescriptor&
end);
608 VertexDescriptor current_;
610 VertexDescriptor end_;
627 ConstVertexIterator
begin()
const;
633 ConstVertexIterator
end()
const;
641 ConstEdgeIterator
beginEdges(
const VertexDescriptor& source)
const;
649 ConstEdgeIterator
endEdges(
const VertexDescriptor& source)
const;
674 EdgeDescriptor
findEdge(
const VertexDescriptor& source,
675 const VertexDescriptor& target)
const;
683 SubGraph(
const Graph& graph,
const T& excluded);
694 std::size_t noVertices_;
696 VertexDescriptor endVertex_;
703 VertexDescriptor maxVertex_;
705 VertexDescriptor* edges_;
707 std::ptrdiff_t* start_;
709 std::ptrdiff_t* end_;
719 template<
class G,
class VP,
class VM=IdentityMap>
771 EdgeIterator
beginEdges(
const VertexDescriptor& source);
778 EdgeIterator
endEdges(
const VertexDescriptor& source);
785 ConstEdgeIterator
beginEdges(
const VertexDescriptor& source)
const;
792 ConstEdgeIterator
endEdges(
const VertexDescriptor& source)
const;
797 :
public conditional<is_same<typename remove_const<C>::type,
799 typename Graph::VertexIterator,
800 typename Graph::ConstVertexIterator>::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
851 typename conditional<is_same<C,typename remove_const<C>::type>::value,
853 const VertexProperties&>::type
861 EdgeIterator
begin() const;
868 EdgeIterator
end() const;
931 const Graph&
graph() const;
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
1044 typedef typename conditional<is_same<typename remove_const<C>::type,
1046 typename Graph::EdgeIterator,
1047 typename Graph::ConstEdgeIterator>::type
1077 typename conditional<is_same<C,typename remove_const<C>::type>::value,
1079 const EdgeProperties&>::type
1094 EdgeProperties,VM,EM> > EdgeIterator;
1101 EdgeProperties,VM,EM> > ConstEdgeIterator;
1108 EdgeIterator
beginEdges(const VertexDescriptor& source);
1115 EdgeIterator
endEdges(const VertexDescriptor& source);
1122 ConstEdgeIterator
beginEdges(const VertexDescriptor& source) const;
1129 ConstEdgeIterator
endEdges(const VertexDescriptor& source) const;
1134 :
public conditional<is_same<typename remove_const<C>::type,
1136 typename Graph::VertexIterator,
1137 typename Graph::ConstVertexIterator>::type
1145 typedef typename conditional<is_same<typename remove_const<C>::type,
1147 typename Graph::VertexIterator,
1148 typename Graph::ConstVertexIterator>::type
1179 typename conditional<is_same<C,typename remove_const<C>::type>::value,
1181 const VertexProperties&>::type
1263 EdgeDescriptor findEdge(const VertexDescriptor& source,
1264 const VertexDescriptor& target)
1266 return graph_.findEdge(source,target);
1274 EdgeProperties& getEdgeProperties(
const EdgeDescriptor& edge);
1282 const EdgeProperties& getEdgeProperties(
const EdgeDescriptor& edge)
const;
1290 EdgeProperties& getEdgeProperties(
const VertexDescriptor& source,
1291 const VertexDescriptor& target);
1299 const EdgeProperties& getEdgeProperties(
const VertexDescriptor& source,
1300 const VertexDescriptor& target)
const;
1306 const Graph&
graph()
const;
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>
1460 int visitNeighbours(
const G& graph,
const typename G::VertexDescriptor& vertex,
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;
1506 typename MatrixGraph<M>::EdgeDescriptor
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;
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_) {
1586 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(
const typename MatrixGraph<M>::template EdgeIteratorT<
typename remove_const<C>::type>& other)
const
1588 return block_!=other.block_;
1593 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator!=(
const typename MatrixGraph<M>::template EdgeIteratorT<
const typename remove_const<C>::type>& other)
const
1595 return block_!=other.block_;
1600 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator==(
const typename MatrixGraph<M>::template EdgeIteratorT<
typename remove_const<C>::type>& other)
const
1602 return block_==other.block_;
1607 inline bool MatrixGraph<M>::EdgeIteratorT<C>::operator==(
const typename MatrixGraph<M>::template EdgeIteratorT<
const typename remove_const<C>::type>& other)
const
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_)
1662 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(
const VertexIteratorT<MutableContainer>& other)
const
1664 return current_ != other.current_;
1669 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator!=(
const VertexIteratorT<ConstContainer>& other)
const
1671 return current_ != other.current_;
1677 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(
const VertexIteratorT<MutableContainer>& other)
const
1679 return current_ == other.current_;
1684 inline bool MatrixGraph<M>::VertexIteratorT<C>::operator==(
const VertexIteratorT<ConstContainer>& other)
const
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>
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>
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>
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>
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>
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_;
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>
2022 return graph_.noEdges();
2025 template<
class G,
class V,
class VM>
2026 inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2029 return graph_.beginEdges(source);
2032 template<
class G,
class V,
class VM>
2033 inline typename VertexPropertiesGraph<G,V,VM>::EdgeIterator
2036 return graph_.endEdges(source);
2039 template<
class G,
class V,
class VM>
2040 typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
2043 return graph_.beginEdges(source);
2046 template<
class G,
class V,
class VM>
2047 typename VertexPropertiesGraph<G,V,VM>::ConstEdgeIterator
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
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
2104 return graph_->endEdges(Father::operator*());
2107 template<
class G,
class V,
class VM>
2110 return VertexIterator(graph_.begin(),
this);
2113 template<
class G,
class V,
class VM>
2116 return VertexIterator(graph_.end());
2120 template<
class G,
class V,
class VM>
2123 return ConstVertexIterator(graph_.begin(),
this);
2126 template<
class G,
class V,
class VM>
2129 return ConstVertexIterator(graph_.end());
2132 template<
class G,
class V,
class VM>
2135 return vertexProperties_[vmap_[vertex]];
2138 template<
class G,
class V,
class VM>
2141 return vertexProperties_[vmap_[vertex]];
2144 template<
class G,
class V,
class VM>
2150 template<
class G,
class V,
class VM>
2153 return graph_.noVertices();
2157 template<
class G,
class V,
class VM>
2160 return graph_.maxVertex();
2163 template<
class G,
class V,
class VM>
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>
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
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
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
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
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>
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>
2276 return graph_->endEdges(Father::operator*());
2279 template<
class G,
class V,
class E,
class VM,
class EM>
2282 return VertexIterator(graph_.begin(),
this);
2285 template<
class G,
class V,
class E,
class VM,
class EM>
2288 return VertexIterator(graph_.end());
2292 template<
class G,
class V,
class E,
class VM,
class EM>
2295 return ConstVertexIterator(graph_.begin(),
this);
2298 template<
class G,
class V,
class E,
class VM,
class EM>
2301 return ConstVertexIterator(graph_.end());
2304 template<
class G,
class V,
class E,
class VM,
class EM>
2307 return vertexProperties_[vmap_[vertex]];
2310 template<
class G,
class V,
class E,
class VM,
class EM>
2313 return vertexProperties_[vmap_[vertex]];
2316 template<
class G,
class V,
class E,
class VM,
class EM>
2319 return edgeProperties_[emap_[edge]];
2322 template<
class G,
class V,
class E,
class VM,
class EM>
2325 return edgeProperties_[emap_[edge]];
2328 template<
class G,
class V,
class E,
class VM,
class EM>
2330 const VertexDescriptor& target)
2332 return getEdgeProperties(graph_.findEdge(source,target));
2335 template<
class G,
class V,
class E,
class VM,
class EM>
2337 const VertexDescriptor& target)
const
2339 return getEdgeProperties(graph_.findEdge(source,target));
2342 template<
class G,
class V,
class E,
class VM,
class EM>
2348 template<
class G,
class V,
class E,
class VM,
class EM>
2351 return graph_.noVertices();
2355 template<
class G,
class V,
class E,
class VM,
class EM>
2358 return graph_.maxVertex();
2361 template<
class G,
class V,
class E,
class VM,
class EM>
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;
EdgeIteratorT< C > & operator++()
preincrement operator.
const EdgeDescriptor & operator*() const
Get the edge descriptor.
std::ptrdiff_t distanceTo(const EdgeIterator &other) const
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:996
conditional< is_same< C, typename remove_const< C >::type >::value &&C::mutableMatrix, typename M::block_type, const typename M::block_type >::type WeightType
Definition: graph.hh:264
EdgeIterator endEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
VertexIteratorT(C *graph, const VertexDescriptor ¤t)
Constructor.
Row row
Definition: matrixmatrix.hh:345
bool equals(const EdgeIterator &other) const
Equality operator.
EM EdgeMap
The type of the map for converting the EdgeDescriptor to std::size_t.
Definition: graph.hh:1028
std::size_t noVertices() const
Get the number of vertices in the graph.
conditional< is_same< typename remove_const< C >::type, C >::value, typename Graph::EdgeIterator, typename Graph::ConstEdgeIterator >::type Father
The father class.
Definition: graph.hh:1048
EdgeIteratorT(const VertexDescriptor &source, const ColIterator &block, const ColIterator &end, const EdgeDescriptor &edge)
Constructor.
std::size_t noEdges() const
Get the number of edges in the graph.
VertexIterator begin()
Get an iterator over the vertices.
ConstVertexIterator begin() const
Get an iterator over the vertices.
EdgeIterator endEdges(const VertexDescriptor &source)
Get an iterator over the edges starting at a vertex.
EdgeIterator beginEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
conditional< is_same< C, typename remove_const< C >::type >::value &&C::mutableMatrix, typename M::block_type, const typename M::block_type >::type WeightType
Definition: graph.hh:154
const VertexDescriptor & target() const
The index of the target vertex of the current edge.
remove_const< C >::type MutableContainer
The mutable type of the container type.
Definition: graph.hh:99
const VertexDescriptor & source() const
The index of the source vertex of the current edge.
The edge iterator of the graph.
Definition: graph.hh:502
conditional< isMutable &&C::mutableMatrix, typename Matrix::row_type::Iterator, typename Matrix::row_type::ConstIterator >::type ColIterator
The column iterator of the matrix we use.
Definition: graph.hh:118
ConstEdgeIterator endEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
ReadablePropertyMapTag Category
Definition: graph.hh:470
VertexIterator end()
Get an iterator over the vertices.
std::size_t noEdges() const
Get the number of edges in the graph.
MatrixGraph(Matrix &matrix)
Constructor.
derive error class from the base class in common
Definition: istlexception.hh:16
EP EdgeProperties
The type of the properties of the edges;.
Definition: graph.hh:1014
T Excluded
Random access container providing information about which vertices are excluded.
Definition: graph.hh:452
~MatrixGraph()
Destructor.
The vertex iterator of the graph.
Definition: graph.hh:556
VertexDescriptor target() const
The index of the target vertex of the current edge.
GraphEdgePropertiesSelector()
Default constructor.
Definition: graph.hh:1432
Matrix & matrix()
Get the underlying matrix.
SubGraph(const Graph &graph, const T &excluded)
Constructor.
std::size_t noVertices() const
Get the number of vertices in the graph.
G Graph
The type of the graph we are a sub graph for.
Definition: graph.hh:446
VertexProperties & operator[](const Vertex &vertex) const
Get the properties associated to a vertex.
Definition: graph.hh:1393
M::block_type Weight
The type of the weights.
Definition: graph.hh:64
EdgeIteratorT< const MatrixGraph< Matrix > > ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:296
G Graph
The graph we attach properties to.
Definition: graph.hh:726
Graph::ConstEdgeIterator ConstEdgeIterator
The type of the constant edge iterator.
Definition: graph.hh:764
const VertexDescriptor & dereference() const
Get the descriptor of the current vertex.
VertexIterator & increment()
Preincrement operator.
VertexIterator end()
Get an iterator over the vertices.
conditional< is_same< typename remove_const< C >::type, C >::value, typename Graph::VertexIterator, typename Graph::ConstVertexIterator >::type Father
The father class.
Definition: graph.hh:812
ConstEdgeIterator beginEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
EdgeDescriptor findEdge(const VertexDescriptor &source, const VertexDescriptor &target) const
Find the descriptor of an edge.
const remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:103
VertexDescriptor * EdgeDescriptor
Definition: graph.hh:459
EdgeIterator & advance(std::ptrdiff_t n)
std::size_t noVertices() const
Get the number of vertices in the graph.
EdgeIndexMap(const EdgeDescriptor &firstEdge)
Definition: graph.hh:472
VertexIterator ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:621
EdgeIterator end() const
Get an iterator over all edges starting at the current vertex.
EdgeIndexMap getEdgeIndexMap()
Get an edge index map for the graph.
EdgeIteratorT< MatrixGraph< Matrix > > EdgeIterator
The mutable edge iterator type.
Definition: graph.hh:301
EdgeIterator ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:616
VertexIteratorT< const MatrixGraph< Matrix > > ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:306
bool equals(const VertexIterator &other) const
Equality iterator.
GraphVertexPropertiesSelector()
Default constructor.
Definition: graph.hh:1384
EdgeIterator(const VertexDescriptor &source, const EdgeDescriptor &edge)
Constructor.
const EdgeDescriptor & dereference() const
The descriptor of the current edge.
EdgeIteratorT< C > end() const
Get an iterator over all edges starting at the current vertex.
VertexIteratorT< C > & operator++()
Move to the next vertex.
remove_const< M >::type MutableMatrix
The mutable type of the matrix we are a graph for.
Definition: graph.hh:59
EdgeIterator end() const
Get an iterator over the edges starting from the current vertex.
An index map for mapping the edges to indices.
Definition: graph.hh:467
whether C is mutable.
Definition: graph.hh:223
std::size_t noVertices() const
Get the number of vertices in the graph.
EdgeIterator endEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
const remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:216
conditional< is_same< C, typename remove_const< C >::type >::value, VertexProperties &, const VertexProperties & >::type properties() const
Get the properties of the current Vertex.
A subgraph of a graph.
Definition: graph.hh:440
EdgeIndexMap(const EdgeIndexMap &emap)
Protect copy construction.
Definition: graph.hh:477
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:741
EdgeProperties & getEdgeProperties(const EdgeDescriptor &edge)
Get the properties associated with a edge.
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:754
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
conditional< isMutable &&C::mutableMatrix, typename M::block_type, const typename M::block_type >::type Weight
The matrix block type we use as weights.
Definition: graph.hh:125
Definition: graph.hh:1031
const Graph & graph() const
Get the graph the properties are attached to.
bool operator!=(const EdgeIteratorT< typename remove_const< C >::type > &other) const
Inequality operator.
WeightType & weight() const
Access the weight of the vertex.
EdgeDescriptor findEdge(const VertexDescriptor &source, const VertexDescriptor &target) const
Find the descriptor of an edge.
std::size_t noEdges() const
Get the number of edges in the graph.
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1364
GraphVertexPropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1378
VertexIterator begin()
Get an iterator over the vertices.
const EdgeDescriptor * operator->() const
Get the edge descriptor.
The vertex iterator type of the graph.
Definition: graph.hh:206
VertexIterator begin()
Get an iterator over the vertices.
EdgeProperties & operator[](const Edge &edge) const
Get the properties associated to a vertex.
Definition: graph.hh:1440
std::size_t operator[](const EdgeDescriptor &edge) const
Definition: graph.hh:481
Wrapper to access the internal edge properties of a graph via operator[]()
Definition: graph.hh:1358
EdgeIterator & decrement()
Preincrement operator.
VertexProperties & getVertexProperties(const VertexDescriptor &vertex)
Get the properties associated with a vertex.
M Matrix
The type of the matrix we are a graph for.
Definition: graph.hh:54
Attaches properties to the vertices of a graph.
Definition: graph.hh:720
bool operator!=(const VertexIteratorT< ConstContainer > &other) const
Inequality operator.
G::EdgeProperties EdgeProperties
The type of the vertex properties.
Definition: graph.hh:1416
const Graph & graph() const
Get the graph the properties are attached to.
conditional< is_same< typename remove_const< C >::type, C >::value, typename Graph::VertexIterator, typename Graph::ConstVertexIterator >::type Father
The father class.
Definition: graph.hh:1149
VertexDescriptor source() const
The index of the source vertex of the current edge.
ConstVertexIterator end() const
Get an iterator over the vertices.
PropertiesGraph(Graph &graph, const VertexMap &vmap=VertexMap(), const EdgeMap &emap=EdgeMap())
Constructor.
VertexIterator(const SubGraph< G, T > *graph, const VertexDescriptor ¤t, const VertexDescriptor &end)
Constructor.
EdgeIterator begin() const
Get an iterator over all edges starting at the current vertex.
G Graph
The graph we attach properties to.
Definition: graph.hh:981
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:986
bool operator==(const VertexIteratorT< ConstContainer > &other) const
Equality operator.
std::size_t noEdges() const
Get the number of edges in the graph.
EdgeIterator beginEdges(const VertexDescriptor &source)
Get an iterator over the edges starting at a vertex.
EdgeIterator & increment()
Preincrement operator.
G::VertexDescriptor Vertex
The vertex descriptor.
Definition: graph.hh:1372
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:731
EdgeIteratorT< C > begin() const
Get an iterator over all edges starting at the current vertex.
G::VertexProperties VertexProperties
The type of the vertex properties.
Definition: graph.hh:1368
Graph::EdgeIterator EdgeIterator
The type of the mutable edge iterator.
Definition: graph.hh:759
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1412
EdgeIterator begin() const
Get an iterator over the edges starting from the current vertex.
bool operator==(const EdgeIteratorT< typename remove_const< C >::type > &other) const
Equality operator.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
VertexProperties & getVertexProperties(const VertexDescriptor &vertex)
Get the properties associated with a vertex.
VertexIterator end()
Get an iterator over the vertices.
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:736
VertexIteratorT< MatrixGraph< Matrix > > VertexIterator
The mutable vertex iterator type.
Definition: graph.hh:311
Definition: basearray.hh:19
Iterator over all edges starting from a vertex.
Definition: graph.hh:92
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:991
WeightType & weight() const
Access the edge weight.
G::EdgeDescriptor Edge
The edge descriptor.
Definition: graph.hh:1420
const VertexDescriptor & operator*() const
Get the descriptor of the current vertex.
The (undirected) graph of a matrix.
Definition: graph.hh:48
GraphEdgePropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1426
remove_const< C >::type MutableContainer
The mutable type of the container type.
Definition: graph.hh:212
whether C is mutable.
Definition: graph.hh:110
M::size_type VertexDescriptor
The vertex descriptor.
Definition: graph.hh:71
VertexPropertiesGraph(Graph &graph, const VertexMap vmap=VertexMap())
Constructor.
EdgeIterator beginEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
Definition: graph.hh:1133
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:457
Attaches properties to the edges and vertices of a graph.
Definition: graph.hh:975
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:1009
int visitNeighbours(const G &graph, const typename G::VertexDescriptor &vertex, V &visitor)
Visit all neighbour vertices of a vertex in a graph.
Wrapper to access the internal vertex properties of a graph via operator[]()
Definition: graph.hh:1406
std::ptrdiff_t EdgeDescriptor
The edge descriptor.
Definition: graph.hh:78