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;
117 typedef typename conditional<
isMutable && C::mutableMatrix,
typename Matrix::row_type::Iterator,
118 typename Matrix::row_type::ConstIterator>
::type
124 typedef typename conditional<
isMutable && C::mutableMatrix,
typename M::block_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,
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;
EdgeProperties & getEdgeProperties(const EdgeDescriptor &edge)
Get the properties associated with a edge.
const EdgeDescriptor * operator->() const
Get the edge descriptor.
conditional< is_same< typename remove_const< C >::type, C >::value, typename Graph::VertexIterator, typename Graph::ConstVertexIterator >::type Father
The father class.
Definition: graph.hh:1150
The vertex iterator of the graph.
Definition: graph.hh:557
whether C is mutable.
Definition: graph.hh:224
G Graph
The type of the graph we are a sub graph for.
Definition: graph.hh:447
bool operator==(const EdgeIteratorT< typename remove_const< C >::type > &other) const
Equality operator.
int visitNeighbours(const G &graph, const typename G::VertexDescriptor &vertex, V &visitor)
Visit all neighbour vertices of a vertex in a graph.
Attaches properties to the vertices of a graph.
Definition: graph.hh:721
M::size_type VertexDescriptor
The vertex descriptor.
Definition: graph.hh:72
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:126
Iterator over all edges starting from a vertex.
Definition: graph.hh:93
const remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:217
EdgeIndexMap(const EdgeDescriptor &firstEdge)
Definition: graph.hh:473
VertexIterator begin()
Get an iterator over the vertices.
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:997
WeightType & weight() const
Access the edge weight.
EdgeIteratorT< C > end() const
Get an iterator over all edges starting at the current vertex.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
VertexIteratorT< MatrixGraph< Matrix > > VertexIterator
The mutable vertex iterator type.
Definition: graph.hh:312
Wrapper to access the internal vertex properties of a graph via operator[]()
Definition: graph.hh:1407
conditional< is_same< C, typename remove_const< C >::type >::value, VertexProperties &, const VertexProperties & >::type properties() const
Get the properties of the current Vertex.
EdgeIterator & decrement()
Preincrement operator.
The vertex iterator type of the graph.
Definition: graph.hh:207
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:992
Attaches properties to the edges and vertices of a graph.
Definition: graph.hh:976
PropertiesGraph(Graph &graph, const VertexMap &vmap=VertexMap(), const EdgeMap &emap=EdgeMap())
Constructor.
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.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:987
whether C is mutable.
Definition: graph.hh:111
ConstEdgeIterator beginEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
G::EdgeProperties EdgeProperties
The type of the vertex properties.
Definition: graph.hh:1417
EdgeIteratorT(const VertexDescriptor &source, const ColIterator &block, const ColIterator &end, const EdgeDescriptor &edge)
Constructor.
VertexIterator & increment()
Preincrement operator.
VertexDescriptor source() const
The index of the source vertex of the current edge.
bool operator==(const VertexIteratorT< ConstContainer > &other) const
Equality operator.
remove_const< C >::type MutableContainer
The mutable type of the container type.
Definition: graph.hh:213
G Graph
The graph we attach properties to.
Definition: graph.hh:727
The (undirected) graph of a matrix.
Definition: graph.hh:49
SubGraph(const Graph &graph, const T &excluded)
Constructor.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:458
remove_const< C >::type MutableContainer
The mutable type of the container type.
Definition: graph.hh:100
std::ptrdiff_t distanceTo(const EdgeIterator &other) const
VertexProperties & getVertexProperties(const VertexDescriptor &vertex)
Get the properties associated with a vertex.
VertexDescriptor * EdgeDescriptor
Definition: graph.hh:460
std::size_t noEdges() const
Get the number of edges in the graph.
G::EdgeDescriptor Edge
The edge descriptor.
Definition: graph.hh:1421
Graph::ConstEdgeIterator ConstEdgeIterator
The type of the constant edge iterator.
Definition: graph.hh:765
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1365
EdgeIteratorT< C > begin() const
Get an iterator over all edges starting at the current vertex.
ReadablePropertyMapTag Category
Definition: graph.hh:471
GraphVertexPropertiesSelector()
Default constructor.
Definition: graph.hh:1385
bool equals(const VertexIterator &other) const
Equality iterator.
std::size_t noVertices() const
Get the number of vertices in the graph.
EM EdgeMap
The type of the map for converting the EdgeDescriptor to std::size_t.
Definition: graph.hh:1029
A subgraph of a graph.
Definition: graph.hh:441
VertexIterator end()
Get an iterator over the vertices.
EdgeIterator endEdges(const VertexDescriptor &source)
Get an iterator over the edges starting at a vertex.
std::ptrdiff_t EdgeDescriptor
The edge descriptor.
Definition: graph.hh:79
conditional< is_same< typename remove_const< C >::type, C >::value, typename Graph::EdgeIterator, typename Graph::ConstEdgeIterator >::type EdgeIterator
The class of the edge iterator.
Definition: graph.hh:822
EdgeIteratorT< C > & operator++()
preincrement operator.
GraphEdgePropertiesSelector()
Default constructor.
Definition: graph.hh:1433
EdgeIterator ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:617
G Graph
The type of the graph with internal properties.
Definition: graph.hh:1413
const VertexDescriptor & source() const
The index of the source vertex of the current edge.
EdgeIterator beginEdges(const VertexDescriptor &source)
Get an iterator over the edges starting at a vertex.
EdgeIterator(const VertexDescriptor &source, const EdgeDescriptor &edge)
Constructor.
std::size_t noEdges() const
Get the number of edges in the graph.
VertexIterator end()
Get an iterator over the vertices.
VertexProperties & operator[](const Vertex &vertex) const
Get the properties associated to a vertex.
Definition: graph.hh:1394
The edge iterator of the graph.
Definition: graph.hh:503
VertexIterator begin()
Get an iterator over the vertices.
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:155
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:755
const VertexDescriptor & operator*() const
Get the descriptor of the current vertex.
remove_const< M >::type MutableMatrix
The mutable type of the matrix we are a graph for.
Definition: graph.hh:60
ConstVertexIterator end() const
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:813
EdgeIterator & increment()
Preincrement operator.
EdgeIterator endEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
Class representing the properties of an ede in the matrix graph.
Definition: dependency.hh:38
const EdgeDescriptor & dereference() const
The descriptor of the current edge.
EdgeIterator end() const
Get an iterator over all edges starting at the current vertex.
G::VertexProperties VertexProperties
The type of the vertex properties.
Definition: graph.hh:1369
MatrixGraph(Matrix &matrix)
Constructor.
EdgeIterator begin() const
Get an iterator over the edges starting from the current vertex.
VertexIterator begin()
Get an iterator over the vertices.
Graph::VertexDescriptor VertexDescriptor
The vertex descriptor.
Definition: graph.hh:732
VertexDescriptor target() const
The index of the target vertex of the current edge.
const EdgeDescriptor & operator*() const
Get the edge descriptor.
G Graph
The graph we attach properties to.
Definition: graph.hh:982
MM_TYPE type
Definition: matrixmarket.hh:267
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
const 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:65
Definition: graph.hh:1134
VertexIterator end()
Get an iterator over the vertices.
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:265
Row row
Definition: matrixmatrix.hh:345
const VertexDescriptor & dereference() const
Get the descriptor of the current vertex.
EP EdgeProperties
The type of the properties of the edges;.
Definition: graph.hh:1015
An index map for mapping the edges to indices.
Definition: graph.hh:468
Matrix & matrix()
Get the underlying matrix.
EdgeIterator endEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
VertexPropertiesGraph(Graph &graph, const VertexMap vmap=VertexMap())
Constructor.
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:119
const remove_const< C >::type ConstContainer
The constant type of the container type.
Definition: graph.hh:104
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
G::VertexDescriptor Vertex
The vertex descriptor.
Definition: graph.hh:1373
EdgeIterator end() const
Get an iterator over the edges starting from the current vertex.
GraphEdgePropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1427
Graph::EdgeIterator EdgeIterator
The type of the mutable edge iterator.
Definition: graph.hh:760
derive error class from the base class in common
Definition: istlexception.hh:16
EdgeIterator beginEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
const VertexDescriptor & target() const
The index of the target vertex of the current edge.
VertexIterator ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:622
VertexIterator(const SubGraph< G, T > *graph, const VertexDescriptor ¤t, const VertexDescriptor &end)
Constructor.
M Matrix
The type of the matrix we are a graph for.
Definition: graph.hh:55
ConstEdgeIterator endEdges(const VertexDescriptor &source) const
Get an iterator over the edges starting at a vertex.
VertexIteratorT< const MatrixGraph< Matrix > > ConstVertexIterator
The constant vertex iterator type.
Definition: graph.hh:307
GraphVertexPropertiesSelector(G &g)
Constructor.
Definition: graph.hh:1379
EdgeIndexMap getEdgeIndexMap()
Get an edge index map for the graph.
bool equals(const EdgeIterator &other) const
Equality operator.
conditional< is_same< typename remove_const< C >::type, C >::value, typename Graph::EdgeIterator, typename Graph::ConstEdgeIterator >::type Father
The father class.
Definition: graph.hh:1049
const Graph & graph() const
Get the graph the properties are attached to.
VM VertexMap
The type of the map for converting the VertexDescriptor to std::size_t.
Definition: graph.hh:1010
Graph::EdgeDescriptor EdgeDescriptor
The edge descritor.
Definition: graph.hh:737
EdgeProperties & operator[](const Edge &edge) const
Get the properties associated to a vertex.
Definition: graph.hh:1441
EdgeIterator beginEdges(const VertexDescriptor &source)
Get the mutable edge iterator over edges starting at a vertex.
VertexDescriptor maxVertex() const
Get the maximal vertex descriptor.
const Graph & graph() const
Get the graph the properties are attached to.
std::size_t noVertices() const
Get the number of vertices in the graph.
EdgeIteratorT< MatrixGraph< Matrix > > EdgeIterator
The mutable edge iterator type.
Definition: graph.hh:302
Definition: graph.hh:1032
std::size_t noEdges() const
Get the number of edges in the graph.
EdgeIndexMap(const EdgeIndexMap &emap)
Protect copy construction.
Definition: graph.hh:478
std::size_t noVertices() const
Get the number of vertices in the graph.
EdgeIteratorT< const MatrixGraph< Matrix > > ConstEdgeIterator
The constant edge iterator type.
Definition: graph.hh:297
EdgeIterator & advance(std::ptrdiff_t n)
VertexProperties & getVertexProperties(const VertexDescriptor &vertex)
Get the properties associated with a vertex.
VP VertexProperties
The type of the properties of the vertices.
Definition: graph.hh:742
~MatrixGraph()
Destructor.
VertexIteratorT(C *graph, const VertexDescriptor ¤t)
Constructor.
bool operator!=(const EdgeIteratorT< typename remove_const< C >::type > &other) const
Inequality operator.
std::size_t operator[](const EdgeDescriptor &edge) const
Definition: graph.hh:482
T Excluded
Random access container providing information about which vertices are excluded.
Definition: graph.hh:453
bool operator!=(const VertexIteratorT< ConstContainer > &other) const
Inequality operator.
ConstVertexIterator begin() const
Get an iterator over the vertices.
std::size_t noVertices() const
Get the number of vertices in the graph.
EdgeIterator begin() const
Get an iterator over all edges starting at the current vertex.
Wrapper to access the internal edge properties of a graph via operator[]()
Definition: graph.hh:1359
VertexIteratorT< C > & operator++()
Move to the next vertex.
WeightType & weight() const
Access the weight of the vertex.