// SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- // vi: set et ts=4 sw=2 sts=2: #ifndef DUNE_AMG_GRAPH_HH #define DUNE_AMG_GRAPH_HH #include #include #include #include #include #include #include #include #include namespace Dune { namespace Amg { /** * @addtogroup ISTL_PAAMG * * @{ */ /** @file * @author Markus Blatt * @brief Provides classes for building the matrix graph. * * During the coarsening process in AMG the matrix graph together * with the dependencies, what connections in the graph are considered * strong or weak, what vertices are isolated, etc., have to build. * This information will be contained in the MatrixGraph class. */ /** * @brief The (undirected) graph of a matrix. * * The graph of a sparse matrix essentially describes the sparsity * pattern (nonzero entries) of a matrix. * It is assumed that the underlying sparsity pattern is symmetric, * i.e if entry a_ij is present in the storage scheme of the matrix * (i.e. nonzero) so is a_ji. * * The matrix entries can be accessed as weights of the vertices and * edges. */ template class MatrixGraph { public: /** * @brief The type of the matrix we are a graph for. */ typedef M Matrix; /** * @brief The mutable type of the matrix we are a graph for. */ typedef typename std::remove_const::type MutableMatrix; /** * @brief The type of the weights */ typedef typename M::block_type Weight; /** * @brief The vertex descriptor. * * Each descriptor describes exactly one vertex. */ typedef typename M::size_type VertexDescriptor; /** * @brief The edge descriptor. * * Each edge is identifies by exactly one descriptor. */ typedef std::ptrdiff_t EdgeDescriptor; enum { /* * @brief Whether Matrix is mutable. */ mutableMatrix = std::is_same::type>::value }; /** * @brief Iterator over all edges starting from a vertex. */ template class EdgeIteratorT { public: /** * @brief The mutable type of the container type. */ typedef typename std::remove_const::type MutableContainer; /** * @brief The constant type of the container type. */ typedef const typename std::remove_const::type ConstContainer; friend class EdgeIteratorT; friend class EdgeIteratorT; enum { /** @brief whether C is mutable. */ isMutable = std::is_same::value }; /** * @brief The column iterator of the matrix we use. */ typedef typename std::conditional::type ColIterator; /** * @brief The matrix block type we use as weights. */ typedef typename std::conditional::type Weight; /** * @brief Constructor. * @param source The source vertex of the edges. * @param block The matrix column block the iterator is initialized to, * @param end The end iterator of the matrix row. * @param edge The edge descriptor of the current edge. */ EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block, const ColIterator& end, const EdgeDescriptor& edge); /** * @brief Constructor for the end iterator. * * Variables not needed by operator== or operator!= will not be initialized. * @param block The matrix column block the iterator is initialized to. */ EdgeIteratorT(const ColIterator& block); /** * @brief Copy Constructor. * @param other The iterator to copy. */ template EdgeIteratorT(const EdgeIteratorT& other); typedef typename std::conditional::type>::value && C::mutableMatrix, typename M::block_type, const typename M::block_type>::type WeightType; /** * @brief Access the edge weight */ WeightType& weight() const; /** @brief preincrement operator. */ EdgeIteratorT& operator++(); /** @brief Inequality operator. */ bool operator!=(const EdgeIteratorT::type>& other) const; /** @brief Inequality operator. */ bool operator!=(const EdgeIteratorT::type>& other) const; /** @brief Equality operator. */ bool operator==(const EdgeIteratorT::type>& other) const; /** @brief Equality operator. */ bool operator==(const EdgeIteratorT::type>& other) const; /** @brief The index of the target vertex of the current edge. */ VertexDescriptor target() const; /** @brief The index of the source vertex of the current edge. */ VertexDescriptor source() const; /** @brief Get the edge descriptor. */ const EdgeDescriptor& operator*() const; /** @brief Get the edge descriptor. */ const EdgeDescriptor* operator->() const; private: /** @brief Start vertex of the edges. */ VertexDescriptor source_; /** @brief The column iterator describing the current edge. */ ColIterator block_; /*** * @brief The column iterator positioned at the end of the row * of vertex source_ */ ColIterator blockEnd_; /** @brief The edge descriptor. */ EdgeDescriptor edge_; }; /** * @brief The vertex iterator type of the graph. */ template class VertexIteratorT { public: /** * @brief The mutable type of the container type. */ typedef typename std::remove_const::type MutableContainer; /** * @brief The constant type of the container type. */ typedef const typename std::remove_const::type ConstContainer; friend class VertexIteratorT; friend class VertexIteratorT; enum { /** @brief whether C is mutable. */ isMutable = std::is_same::value }; /** * @brief Constructor. * @param graph The graph we are a vertex iterator for. * @param current The current vertex to position on. */ explicit VertexIteratorT(C* graph, const VertexDescriptor& current); /** * @brief Constructor for the end iterator. * * only operator== or operator!= may be called safely on an * iterator constructed this way. * @param current The current vertex to position on. */ explicit VertexIteratorT(const VertexDescriptor& current); VertexIteratorT(const VertexIteratorT& other); /** * @brief Move to the next vertex. * @return This iterator positioned at the next vertex. */ VertexIteratorT& operator++(); /** @brief Inequality operator. */ bool operator!=(const VertexIteratorT& other) const; /** @brief Equality operator. */ bool operator==(const VertexIteratorT& other) const; /** @brief Inequality operator. */ bool operator!=(const VertexIteratorT& other) const; /** @brief Equality operator. */ bool operator==(const VertexIteratorT& other) const; typedef typename std::conditional::type>::value && C::mutableMatrix, typename M::block_type, const typename M::block_type>::type WeightType; /** @brief Access the weight of the vertex. */ WeightType& weight() const; /** * @brief Get the descriptor of the current vertex. * @return The index of the currently referenced vertex. */ const VertexDescriptor& operator*() const; /** * @brief Get an iterator over all edges starting at the * current vertex. * @return Iterator position on the first edge to another vertex. */ EdgeIteratorT begin() const; /** * @brief Get an iterator over all edges starting at the * current vertex. * @return Iterator position on the first edge to another vertex. */ EdgeIteratorT end() const; private: C* graph_; VertexDescriptor current_; }; /** * @brief The constant edge iterator type. */ typedef EdgeIteratorT > ConstEdgeIterator; /** * @brief The mutable edge iterator type. */ typedef EdgeIteratorT > EdgeIterator; /** * @brief The constant vertex iterator type. */ typedef VertexIteratorT > ConstVertexIterator; /** * @brief The mutable vertex iterator type. */ typedef VertexIteratorT > VertexIterator; /** * @brief Constructor. * @param matrix The matrix we are a graph for. */ MatrixGraph(Matrix& matrix); /** * @brief Destructor. */ ~MatrixGraph(); /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned at the first vertex. */ VertexIterator begin(); /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned behind the last vertex. */ VertexIterator end(); /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned at the first vertex. */ ConstVertexIterator begin() const; /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned behind the last vertex. */ ConstVertexIterator end() const; /** * @brief Get an iterator over the edges starting at a vertex. * @param source The vertex where the edges should start. * @return An edge iterator positioned at the first edge starting * from vertex source. */ EdgeIterator beginEdges(const VertexDescriptor& source); /** * @brief Get an iterator over the edges starting at a vertex. * @param source The vertex where the edges should start. * @return An edge iterator positioned behind the last edge starting * from vertex source. */ EdgeIterator endEdges(const VertexDescriptor& source); /** * @brief Get an iterator over the edges starting at a vertex. * @param source The vertex where the edges should start. * @return An edge iterator positioned at the first edge starting * from vertex source. */ ConstEdgeIterator beginEdges(const VertexDescriptor& source) const; /** * @brief Get an iterator over the edges starting at a vertex. * @param source The vertex where the edges should start. * @return An edge iterator positioned behind the last edge starting * from vertex source. */ ConstEdgeIterator endEdges(const VertexDescriptor& source) const; /** * @brief Get the underlying matrix. * @return The matrix of the graph. */ Matrix& matrix(); /** * @brief Get the underlying matrix. * @return The matrix of the graph. */ const Matrix& matrix() const; /** * @brief Get the number of vertices in the graph. */ std::size_t noVertices() const; /** * @brief Get the maximal vertex descriptor. * * @return The minimum value v such that for * all vertices w in the graph w<v holds. */ VertexDescriptor maxVertex() const; /** * @brief Get the number of edges in the graph. */ std::size_t noEdges() const; /** * @brief Find the descriptor of an edge. * @param source The source vertex of the edge we search for. * @param target The target vertex of the edge we search for. * @return The edge we found or numeric_limits::max() if it does not exist. */ EdgeDescriptor findEdge(const VertexDescriptor& source, const VertexDescriptor& target) const; private: /** @brief The matrix we are the graph for. */ Matrix& matrix_; /** @brief The edge descriptor of the first edge of each row. */ EdgeDescriptor* start_; /** Prevent copying. */ MatrixGraph(const MatrixGraph&); }; /** * @brief A subgraph of a graph. * * This is a (cached) view of a graph where certain * vertices and edges pointing to and leading from them * are skipped. * * The vertex descriptors are not changed. */ template class SubGraph { public: /** * @brief The type of the graph we are a sub graph for. */ typedef G Graph; /** * @brief Random access container providing information about * which vertices are excluded. */ typedef T Excluded; /** * @brief The vertex descriptor. */ typedef typename Graph::VertexDescriptor VertexDescriptor; typedef VertexDescriptor* EdgeDescriptor; /** * @brief An index map for mapping the edges to indices. * * This should be used for attaching properties to a SubGraph * using VertexPropertiesGraph od PropertiesGraph. */ class EdgeIndexMap { public: typedef ReadablePropertyMapTag Category; EdgeIndexMap(const EdgeDescriptor& firstEdge) : firstEdge_(firstEdge) {} /** @brief Protect copy construction. */ EdgeIndexMap(const EdgeIndexMap& emap) : firstEdge_(emap.firstEdge_) {} std::size_t operator[](const EdgeDescriptor& edge) const { return edge-firstEdge_; } private: /** @brief The first edge of the graph. */ EdgeDescriptor firstEdge_; /** @brief Protect default construction. */ EdgeIndexMap() {} }; /** * @brief Get an edge index map for the graph. * @return An edge index map for the graph. */ EdgeIndexMap getEdgeIndexMap(); /** * @brief The edge iterator of the graph. */ class EdgeIterator : public RandomAccessIteratorFacade { public: /** * @brief Constructor. * @param source The source vertex of the edge. * @param edge Pointer to the edge the iterator should point to. */ explicit EdgeIterator(const VertexDescriptor& source, const EdgeDescriptor& edge); /** * @brief Constructor for the end iterator. * * Only operator== or operator!= can be called safely on an iterator constructed * this way! * @param edge Pointer to the end of the graph's edge array. */ explicit EdgeIterator(const EdgeDescriptor& edge); /** @brief Equality operator. */ bool equals(const EdgeIterator& other) const; /** @brief Preincrement operator. */ EdgeIterator& increment(); /** @brief Preincrement operator. */ EdgeIterator& decrement(); EdgeIterator& advance(std::ptrdiff_t n); /** @brief The descriptor of the current edge. */ const EdgeDescriptor& dereference() const; /** @brief The index of the target vertex of the current edge. */ const VertexDescriptor& target() const; /** @brief The index of the source vertex of the current edge. */ const VertexDescriptor& source() const; std::ptrdiff_t distanceTo(const EdgeIterator& other) const; private: /** @brief The source vertex of the edge. */ VertexDescriptor source_; /** * @brief The offset of the current edge to the first * one starting at the vertex source_. */ EdgeDescriptor edge_; }; /** * @brief The vertex iterator of the graph. */ class VertexIterator : public ForwardIteratorFacade { public: /** * @brief Constructor. * @param graph The graph over whose vertices to iterate. * @param current The position of the iterator. * @param end The last vertex of the graph. */ explicit VertexIterator(const SubGraph* graph, const VertexDescriptor& current, const VertexDescriptor& end); /** * @brief Constructor for end iterator. * * Use with care! All operations except operator== or operator!= will fail! * @param current The position of the iterator. */ explicit VertexIterator(const VertexDescriptor& current); /** @brief Preincrement operator. */ VertexIterator& increment(); /** @brief Equality iterator. */ bool equals(const VertexIterator& other) const; /** * @brief Get the descriptor of the current vertex. * @return The index of the currently referenced vertex. */ const VertexDescriptor& dereference() const; /** * @brief Get an iterator over all edges starting at the * current vertex. * @return Iterator position on the first edge to another vertex. */ EdgeIterator begin() const; /** * @brief Get an iterator over all edges starting at the * current vertex. * @return Iterator position on the first edge to another vertex. */ EdgeIterator end() const; private: /** @brief The graph we are a vertex iterator for. */ const SubGraph* graph_; /** @brief The current position. */ VertexDescriptor current_; /** @brief The number of vertices of the graph. */ VertexDescriptor end_; }; /** * @brief The constant edge iterator type. */ typedef EdgeIterator ConstEdgeIterator; /** * @brief The constant vertex iterator type. */ typedef VertexIterator ConstVertexIterator; /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned at the first vertex. */ ConstVertexIterator begin() const; /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned behind the last vertex. */ ConstVertexIterator end() const; /** * @brief Get an iterator over the edges starting at a vertex. * @param source The vertex where the edges should start. * @return An edge iterator positioned at the first edge starting * from vertex source. */ ConstEdgeIterator beginEdges(const VertexDescriptor& source) const; /** * @brief Get an iterator over the edges starting at a vertex. * @param source The vertex where the edges should start. * @return An edge iterator positioned behind the last edge starting * from vertex source. */ ConstEdgeIterator endEdges(const VertexDescriptor& source) const; /** * @brief Get the number of vertices in the graph. */ std::size_t noVertices() const; /** * @brief Get the maximal vertex descriptor. * * @return The minimum value v such that for * all vertices w in the graph w<v holds. */ VertexDescriptor maxVertex() const; /** * @brief Get the number of edges in the graph. */ std::size_t noEdges() const; /** * @brief Find the descriptor of an edge. * @param source The source vertex of the edge we search for. * @param target The target vertex of the edge we search for. * @return The edge we found or numeric_limits::max() if it does not exist. */ EdgeDescriptor findEdge(const VertexDescriptor& source, const VertexDescriptor& target) const; /** * @brief Constructor. * * @param graph The graph we are a sub graph for. * @param excluded If excluded[i] is true then vertex i will not appear * in the sub graph. */ SubGraph(const Graph& graph, const T& excluded); /** * @brief Destructor. */ ~SubGraph(); private: /** @brief flags indication which vertices are excluded. */ const T& excluded_; /** @brief The number of vertices in this sub graph. */ std::size_t noVertices_; /** @brief Vertex behind the last valid vertex of this sub graph. */ VertexDescriptor endVertex_; /** @brief The number of edges in this sub graph.*/ int noEdges_; /** * @brief The maximum vertex descriptor of the graph * we are a subgraph for. */ VertexDescriptor maxVertex_; /** @brief The edges of this sub graph. */ VertexDescriptor* edges_; /** @brief The start of the out edges of each vertex. */ std::ptrdiff_t* start_; /** @brief The edge behind the last out edge of each vertex. */ std::ptrdiff_t* end_; /** prevent copying */ SubGraph(const SubGraph&) {} }; /** * @brief Attaches properties to the vertices of a graph. */ template class VertexPropertiesGraph { public: /** * @brief The graph we attach properties to. */ typedef G Graph; /** * @brief The vertex descriptor. */ typedef typename Graph::VertexDescriptor VertexDescriptor; /** * @brief The edge descritor. */ typedef typename Graph::EdgeDescriptor EdgeDescriptor; /** * @brief The type of the properties of the vertices. */ typedef VP VertexProperties; /** * @brief The type of the map for converting the VertexDescriptor * to std::size_t * * Has to provide the following method: * std::size_t operator[](const VertexDescriptor& vertex) * * The following condition has to be met: * Let v1 and v2 be two vertex descriptors with v1 < v2 and map be the * index map. Then map[v1] class VertexIteratorT : public std::conditional::type, C>::value, typename Graph::VertexIterator, typename Graph::ConstVertexIterator>::type { friend class VertexIteratorT::type>; friend class VertexIteratorT::type>; public: /** * @brief The father class. */ typedef typename std::conditional::type, C>::value, typename Graph::VertexIterator, typename Graph::ConstVertexIterator>::type Father; /** * @brief The class of the edge iterator. */ typedef typename std::conditional::type, C>::value, typename Graph::EdgeIterator, typename Graph::ConstEdgeIterator>::type EdgeIterator; /** * @brief Constructor. * @param iter The iterator of the underlying graph. * @param graph The property graph over whose vertices we iterate. */ explicit VertexIteratorT(const Father& iter, C* graph); /** * @brief Constructor for the end iterator. * * Only operator!= or operator== can be called safely on an iterator * constructed this way. * @param iter The iterator of the underlying graph. */ explicit VertexIteratorT(const Father& iter); /** * @brief Copy Constructor. * @param other The iterator to copy. */ template VertexIteratorT(const VertexIteratorT& other); /** * @brief Get the properties of the current Vertex. */ typename std::conditional::type>::value, VertexProperties&, const VertexProperties&>::type properties() const; /** * @brief Get an iterator over the edges starting from the current vertex. * @return An iterator over the edges starting from the current vertex * positioned at the first edge. */ EdgeIterator begin() const; /** * @brief Get an iterator over the edges starting from the current vertex. * @return An iterator over the edges starting from the current vertex * positioned after the last edge. */ EdgeIterator end() const; private: /** * @brief The graph over whose vertices we iterate. */ C* graph_; }; /** * @brief The type of the mutable Vertex iterator. */ typedef VertexIteratorT > VertexIterator; /** * @brief The type of the constant Vertex iterator. */ typedef VertexIteratorT > ConstVertexIterator; /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned at the first vertex. */ VertexIterator begin(); /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned behind the last vertex. */ VertexIterator end(); /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned at the first vertex. */ ConstVertexIterator begin() const; /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned behind the last vertex. */ ConstVertexIterator end() const; /** * @brief Get the properties associated with a vertex. * @param vertex The descriptor identifying the vertex. * @return The properties of the vertex. */ VertexProperties& getVertexProperties(const VertexDescriptor& vertex); /** * @brief Get the properties associated with a vertex. * @param vertex The descriptor identifying the vertex. * @return The properties of the vertex. */ const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const; /** * @brief Get the graph the properties are attached to. * @return The underlying graph. */ const Graph& graph() const; /** * @brief Get the number of vertices in the graph. */ std::size_t noVertices() const; /** * @brief Get the number of edges in the graph. */ std::size_t noEdges() const; /** * @brief Get the maximal vertex descriptor. * * @return The minimum value v such that for * all vertices w in the graph w<v holds. */ VertexDescriptor maxVertex() const; /** * @brief Constructor. * @param graph The graph we attach properties to. * @param vmap The vertex map. */ VertexPropertiesGraph(Graph& graph, const VertexMap vmap=VertexMap()); private: VertexPropertiesGraph(const VertexPropertiesGraph&) {} /** @brief The graph the properties are attached to. */ Graph& graph_; /** @brief The vertex map. */ VertexMap vmap_; /** @brief The vertex properties. */ std::vector vertexProperties_; }; /** * @brief Attaches properties to the edges and vertices of a graph. */ template class PropertiesGraph { public: /** * @brief The graph we attach properties to. */ typedef G Graph; /** * @brief The vertex descriptor. */ typedef typename Graph::VertexDescriptor VertexDescriptor; /** * @brief The edge descritor. */ typedef typename Graph::EdgeDescriptor EdgeDescriptor; /** * @brief The type of the properties of the vertices. */ typedef VP VertexProperties; /** * @brief The type of the map for converting the VertexDescriptor * to std::size_t * * Has to provide the following method: * std::size_t operator[](const VertexDescriptor& vertex) * * The following condition has to be met: * Let v1 and v2 be two vertex descriptors with v1 < v2 and map be the * index map. Then map[v1] class EdgeIteratorT : public std::conditional::type, C>::value, typename Graph::EdgeIterator, typename Graph::ConstEdgeIterator>::type { friend class EdgeIteratorT::type>; friend class EdgeIteratorT::type>; public: /** * @brief The father class. */ typedef typename std::conditional::type, C>::value, typename Graph::EdgeIterator, typename Graph::ConstEdgeIterator>::type Father; /** * @brief Constructor. * @param iter The iterator of the underlying graph. * @param graph The graph over whose edges we iterate on. */ explicit EdgeIteratorT(const Father& iter, C* graph); /** * @brief Constructor for the end iterator. * * Only operator== or operator!= should be called on * an iterator constructed this way. * @param iter The iterator of the underlying graph. */ explicit EdgeIteratorT(const Father& iter); /** * @brief Copy constructor. * @param other the iterator to copy. */ template EdgeIteratorT(const EdgeIteratorT& other); /** * @brief Get the properties of the current edge. */ typename std::conditional::type>::value, EdgeProperties&, const EdgeProperties&>::type properties() const; private: /** * @brief The graph over whose edges we iterate. */ C* graph_; }; /** * @brief The type of the mutable edge iterator. */ typedef EdgeIteratorT > EdgeIterator; /** * @brief The type of the constant edge iterator. */ typedef EdgeIteratorT > ConstEdgeIterator; /** * @brief Get the mutable edge iterator over edges starting at a vertex. * @return An edge iterator over edges starting at a vertex * positioned at the first edge. */ EdgeIterator beginEdges(const VertexDescriptor& source); /** * @brief Get the mutable edge iterator over edges starting at a vertex. * @return An edge iterator over edges starting at a vertex * positioned after the last edge. */ EdgeIterator endEdges(const VertexDescriptor& source); /** * @brief Get the mutable edge iterator over edges starting at a vertex. * @return An edge iterator over edges starting at a vertex * positioned at the first edge. */ ConstEdgeIterator beginEdges(const VertexDescriptor& source) const; /** * @brief Get the mutable edge iterator over edges starting at a vertex. * @return An edge iterator over edges starting at a vertex * positioned after the last edge. */ ConstEdgeIterator endEdges(const VertexDescriptor& source) const; template class VertexIteratorT : public std::conditional::type, C>::value, typename Graph::VertexIterator, typename Graph::ConstVertexIterator>::type { friend class VertexIteratorT::type>; friend class VertexIteratorT::type>; public: /** * @brief The father class. */ typedef typename std::conditional::type, C>::value, typename Graph::VertexIterator, typename Graph::ConstVertexIterator>::type Father; /** * @brief Constructor. * @param iter The iterator of the underlying graph. * @param graph The property graph over whose vertices we iterate. */ explicit VertexIteratorT(const Father& iter, C* graph); /** * @brief Constructor for the end iterator. * * Only operator!= or operator== can be called safely on an iterator * constructed this way. * @param iter The iterator of the underlying graph. */ explicit VertexIteratorT(const Father& iter); /** * @brief Copy Constructor. * @param other The iterator to copy. */ template VertexIteratorT(const VertexIteratorT& other); /** * @brief Get the properties of the current Vertex. */ typename std::conditional::type>::value, VertexProperties&, const VertexProperties&>::type properties() const; /** * @brief Get an iterator over the edges starting from the current vertex. * @return An iterator over the edges starting from the current vertex * positioned at the first edge. */ EdgeIteratorT begin() const; /** * @brief Get an iterator over the edges starting from the current vertex. * @return An iterator over the edges starting from the current vertex * positioned after the last edge. */ EdgeIteratorT end() const; private: /** * @brief The graph over whose vertices we iterate. */ C* graph_; }; /** * @brief The type of the mutable Vertex iterator. */ typedef VertexIteratorT > VertexIterator; /** * @brief The type of the constant Vertex iterator. */ typedef VertexIteratorT > ConstVertexIterator; /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned at the first vertex. */ VertexIterator begin(); /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned behind the last vertex. */ VertexIterator end(); /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned at the first vertex. */ ConstVertexIterator begin() const; /** * @brief Get an iterator over the vertices. * @return A vertex Iterator positioned behind the last vertex. */ ConstVertexIterator end() const; /** * @brief Get the properties associated with a vertex. * @param vertex The descriptor identifying the vertex. * @return The properties of the vertex. */ VertexProperties& getVertexProperties(const VertexDescriptor& vertex); /** * @brief Get the properties associated with a vertex. * @param vertex The descriptor identifying the vertex. * @return The properties of the vertex. */ const VertexProperties& getVertexProperties(const VertexDescriptor& vertex) const; /** * @brief Find the descriptor of an edge. * @param source The source vertex of the edge we search for. * @param target The target vertex of the edge we search for. * @return The edge we found or numeric_limits::max() if it does not exist. */ EdgeDescriptor findEdge(const VertexDescriptor& source, const VertexDescriptor& target) { return graph_.findEdge(source,target); } /** * @brief Get the properties associated with a edge. * @param edge The descriptor identifying the edge. * @return The properties of the edge. */ EdgeProperties& getEdgeProperties(const EdgeDescriptor& edge); /** * @brief Get the properties associated with a edge. * @param edge The descriptor identifying the edge. * @return The properties of the edge. */ const EdgeProperties& getEdgeProperties(const EdgeDescriptor& edge) const; /** * @brief Get the properties associated with a edge. * @param source The descriptor identifying the source vertex of the edge. * @param target The descriptor identifying the target vertex of the edge. * @return The properties of the edge. */ EdgeProperties& getEdgeProperties(const VertexDescriptor& source, const VertexDescriptor& target); /** * @brief Get the properties associated with a edge. * @param source The descriptor identifying the source vertex of the edge. * @param target The descriptor identifying the target vertex of the edge. * @return The properties of the edge. */ const EdgeProperties& getEdgeProperties(const VertexDescriptor& source, const VertexDescriptor& target) const; /** * @brief Get the graph the properties are attached to. * @return The underlying graph. */ const Graph& graph() const; /** * @brief Get the number of vertices in the graph. */ std::size_t noVertices() const; /** * @brief Get the number of edges in the graph. */ std::size_t noEdges() const; /** * @brief Get the maximal vertex descriptor. * * @return The minimum value v such that for * all vertices w in the graph w<v holds. */ VertexDescriptor maxVertex() const; /** * @brief Constructor. * @param graph The graph we attach properties to. * @param vmap The map of the vertices onto indices. * @param emap The map of the edges onto indices. */ PropertiesGraph(Graph& graph, const VertexMap& vmap=VertexMap(), const EdgeMap& emap=EdgeMap()); private: PropertiesGraph(const PropertiesGraph&) {} /** @brief The graph the properties are attached to. */ Graph& graph_; /** @brief The vertex properties. */ /** @brief The mapping of the vertices to indices. */ VertexMap vmap_; std::vector vertexProperties_; /** @brief The mapping of the edges to indices. */ EdgeMap emap_; /** @brief The edge properties. */ std::vector edgeProperties_; }; /** * @brief Wrapper to access the internal edge properties of a graph * via operator[]() */ template class GraphVertexPropertiesSelector { public: /** * @brief The type of the graph with internal properties. */ typedef G Graph; /** * @brief The type of the vertex properties. */ typedef typename G::VertexProperties VertexProperties; /** * @brief The vertex descriptor. */ typedef typename G::VertexDescriptor Vertex; /** * @brief Constructor. * @param g The graph whose properties we access. */ GraphVertexPropertiesSelector(G& g) : graph_(g) {} /** * @brief Default constructor. */ GraphVertexPropertiesSelector() : graph_(0) {} /** * @brief Get the properties associated to a vertex. * @param vertex The vertex whose Properties we want. */ VertexProperties& operator[](const Vertex& vertex) const { return graph_->getVertexProperties(vertex); } private: Graph* graph_; }; /** * @brief Wrapper to access the internal vertex properties of a graph * via operator[]() */ template class GraphEdgePropertiesSelector { public: /** * @brief The type of the graph with internal properties. */ typedef G Graph; /** * @brief The type of the vertex properties. */ typedef typename G::EdgeProperties EdgeProperties; /** * @brief The edge descriptor. */ typedef typename G::EdgeDescriptor Edge; /** * @brief Constructor. * @param g The graph whose properties we access. */ GraphEdgePropertiesSelector(G& g) : graph_(g) {} /** * @brief Default constructor. */ GraphEdgePropertiesSelector() : graph_(0) {} /** * @brief Get the properties associated to a vertex. * @param edge The edge whose Properties we want. */ EdgeProperties& operator[](const Edge& edge) const { return graph_->getEdgeProperties(edge); } private: Graph* graph_; }; /** * @brief Visit all neighbour vertices of a vertex in a graph. * * @param graph The graph whose vertices to visit. * @param vertex The vertex whose neighbours we want to * visit. * @param visitor The visitor evaluated for each EdgeIterator * (by its method operator()(const ConstEdgeIterator& edge) * @return The number of neighbours of the vertex. */ template int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex, V& visitor); #ifndef DOXYGEN template MatrixGraph::MatrixGraph(M& matrix) : matrix_(matrix) { if(matrix_.N()!=matrix_.M()) DUNE_THROW(ISTLError, "Matrix has to have as many columns as rows!"); start_ = new EdgeDescriptor[matrix_.N()+1]; typedef typename M::ConstIterator Iterator; start_[matrix_.begin().index()] = 0; for(Iterator row=matrix_.begin(); row != matrix_.end(); ++row) start_[row.index()+1] = start_[row.index()] + row->size(); } template MatrixGraph::~MatrixGraph() { delete[] start_; } template inline std::size_t MatrixGraph::noEdges() const { return start_[matrix_.N()]; } template inline std::size_t MatrixGraph::noVertices() const { return matrix_.N(); } template inline typename MatrixGraph::VertexDescriptor MatrixGraph::maxVertex() const { return matrix_.N()-1; } template typename MatrixGraph::EdgeDescriptor MatrixGraph::findEdge(const VertexDescriptor& source, const VertexDescriptor& target) const { typename M::ConstColIterator found =matrix_[source].find(target); if(found == matrix_[source].end()) return std::numeric_limits::max(); std::size_t offset = found.offset(); if(target>source) offset--; assert(offset inline M& MatrixGraph::matrix() { return matrix_; } template inline const M& MatrixGraph::matrix() const { return matrix_; } template template MatrixGraph::EdgeIteratorT::EdgeIteratorT(const VertexDescriptor& source, const ColIterator& block, const ColIterator& end, const EdgeDescriptor& edge) : source_(source), block_(block), blockEnd_(end), edge_(edge) { if(block_!=blockEnd_ && block_.index() == source_) { // This is the edge from the diagonal to the diagonal. Skip it. ++block_; } } template template MatrixGraph::EdgeIteratorT::EdgeIteratorT(const ColIterator& block) : block_(block) {} template template template MatrixGraph::EdgeIteratorT::EdgeIteratorT(const EdgeIteratorT& other) : source_(other.source_), block_(other.block_), blockEnd_(other.blockEnd_), edge_(other.edge_) {} template template inline typename MatrixGraph::template EdgeIteratorT::WeightType& MatrixGraph::EdgeIteratorT::weight() const { return *block_; } template template inline typename MatrixGraph::template EdgeIteratorT& MatrixGraph::EdgeIteratorT::operator++() { ++block_; ++edge_; if(block_!=blockEnd_ && block_.index() == source_) { // This is the edge from the diagonal to the diagonal. Skip it. ++block_; } return *this; } template template inline bool MatrixGraph::EdgeIteratorT::operator!=(const typename MatrixGraph::template EdgeIteratorT::type>& other) const { return block_!=other.block_; } template template inline bool MatrixGraph::EdgeIteratorT::operator!=(const typename MatrixGraph::template EdgeIteratorT::type>& other) const { return block_!=other.block_; } template template inline bool MatrixGraph::EdgeIteratorT::operator==(const typename MatrixGraph::template EdgeIteratorT::type>& other) const { return block_==other.block_; } template template inline bool MatrixGraph::EdgeIteratorT::operator==(const typename MatrixGraph::template EdgeIteratorT::type>& other) const { return block_==other.block_; } template template inline typename MatrixGraph::VertexDescriptor MatrixGraph::EdgeIteratorT::target() const { return block_.index(); } template template inline typename MatrixGraph::VertexDescriptor MatrixGraph::EdgeIteratorT::source() const { return source_; } template template inline const typename MatrixGraph::EdgeDescriptor& MatrixGraph::EdgeIteratorT::operator*() const { return edge_; } template template inline const typename MatrixGraph::EdgeDescriptor* MatrixGraph::EdgeIteratorT::operator->() const { return &edge_; } template template MatrixGraph::VertexIteratorT::VertexIteratorT(C* graph, const VertexDescriptor& current) : graph_(graph), current_(current) {} template template MatrixGraph::VertexIteratorT::VertexIteratorT(const VertexDescriptor& current) : current_(current) {} template template MatrixGraph::VertexIteratorT::VertexIteratorT(const VertexIteratorT& other) : graph_(other.graph_), current_(other.current_) {} template template inline bool MatrixGraph::VertexIteratorT::operator!=(const VertexIteratorT& other) const { return current_ != other.current_; } template template inline bool MatrixGraph::VertexIteratorT::operator!=(const VertexIteratorT& other) const { return current_ != other.current_; } template template inline bool MatrixGraph::VertexIteratorT::operator==(const VertexIteratorT& other) const { return current_ == other.current_; } template template inline bool MatrixGraph::VertexIteratorT::operator==(const VertexIteratorT& other) const { return current_ == other.current_; } template template inline typename MatrixGraph::template VertexIteratorT& MatrixGraph::VertexIteratorT::operator++() { ++current_; return *this; } template template inline typename MatrixGraph::template VertexIteratorT::WeightType& MatrixGraph::VertexIteratorT::weight() const { return graph_->matrix()[current_][current_]; } template template inline const typename MatrixGraph::VertexDescriptor& MatrixGraph::VertexIteratorT::operator*() const { return current_; } template template inline typename MatrixGraph::template EdgeIteratorT MatrixGraph::VertexIteratorT::begin() const { return graph_->beginEdges(current_); } template template inline typename MatrixGraph::template EdgeIteratorT MatrixGraph::VertexIteratorT::end() const { return graph_->endEdges(current_); } template inline typename MatrixGraph::template VertexIteratorT > MatrixGraph::begin() { return VertexIterator(this,0); } template inline typename MatrixGraph::template VertexIteratorT > MatrixGraph::end() { return VertexIterator(matrix_.N()); } template inline typename MatrixGraph::template VertexIteratorT > MatrixGraph::begin() const { return ConstVertexIterator(this, 0); } template inline typename MatrixGraph::template VertexIteratorT > MatrixGraph::end() const { return ConstVertexIterator(matrix_.N()); } template inline typename MatrixGraph::template EdgeIteratorT > MatrixGraph::beginEdges(const VertexDescriptor& source) { return EdgeIterator(source, matrix_.operator[](source).begin(), matrix_.operator[](source).end(), start_[source]); } template inline typename MatrixGraph::template EdgeIteratorT > MatrixGraph::endEdges(const VertexDescriptor& source) { return EdgeIterator(matrix_.operator[](source).end()); } template inline typename MatrixGraph::template EdgeIteratorT > MatrixGraph::beginEdges(const VertexDescriptor& source) const { return ConstEdgeIterator(source, matrix_.operator[](source).begin(), matrix_.operator[](source).end(), start_[source]); } template inline typename MatrixGraph::template EdgeIteratorT > MatrixGraph::endEdges(const VertexDescriptor& source) const { return ConstEdgeIterator(matrix_.operator[](source).end()); } template SubGraph::EdgeIterator::EdgeIterator(const VertexDescriptor& source, const EdgeDescriptor& edge) : source_(source), edge_(edge) {} template SubGraph::EdgeIterator::EdgeIterator(const EdgeDescriptor& edge) : edge_(edge) {} template typename SubGraph::EdgeIndexMap SubGraph::getEdgeIndexMap() { return EdgeIndexMap(edges_); } template inline bool SubGraph::EdgeIterator::equals(const EdgeIterator & other) const { return other.edge_==edge_; } template inline typename SubGraph::EdgeIterator& SubGraph::EdgeIterator::increment() { ++edge_; return *this; } template inline typename SubGraph::EdgeIterator& SubGraph::EdgeIterator::decrement() { --edge_; return *this; } template inline typename SubGraph::EdgeIterator& SubGraph::EdgeIterator::advance(std::ptrdiff_t n) { edge_+=n; return *this; } template inline const typename G::VertexDescriptor& SubGraph::EdgeIterator::source() const { return source_; } template inline const typename G::VertexDescriptor& SubGraph::EdgeIterator::target() const { return *edge_; } template inline const typename SubGraph::EdgeDescriptor& SubGraph::EdgeIterator::dereference() const { return edge_; } template inline std::ptrdiff_t SubGraph::EdgeIterator::distanceTo(const EdgeIterator & other) const { return other.edge_-edge_; } template SubGraph::VertexIterator::VertexIterator(const SubGraph* graph, const VertexDescriptor& current, const VertexDescriptor& end) : graph_(graph), current_(current), end_(end) { // Skip excluded vertices typedef typename T::const_iterator Iterator; for(Iterator vertex = graph_->excluded_.begin(); current_ != end_ && *vertex; ++vertex) ++current_; assert(current_ == end_ || !graph_->excluded_[current_]); } template SubGraph::VertexIterator::VertexIterator(const VertexDescriptor& current) : current_(current) {} template inline typename SubGraph::VertexIterator& SubGraph::VertexIterator::increment() { ++current_; //Skip excluded vertices while(current_ != end_ && graph_->excluded_[current_]) ++current_; assert(current_ == end_ || !graph_->excluded_[current_]); return *this; } template inline bool SubGraph::VertexIterator::equals(const VertexIterator & other) const { return current_==other.current_; } template inline const typename G::VertexDescriptor& SubGraph::VertexIterator::dereference() const { return current_; } template inline typename SubGraph::EdgeIterator SubGraph::VertexIterator::begin() const { return graph_->beginEdges(current_); } template inline typename SubGraph::EdgeIterator SubGraph::VertexIterator::end() const { return graph_->endEdges(current_); } template inline typename SubGraph::VertexIterator SubGraph::begin() const { return VertexIterator(this, 0, endVertex_); } template inline typename SubGraph::VertexIterator SubGraph::end() const { return VertexIterator(endVertex_); } template inline typename SubGraph::EdgeIterator SubGraph::beginEdges(const VertexDescriptor& source) const { return EdgeIterator(source, edges_+start_[source]); } template inline typename SubGraph::EdgeIterator SubGraph::endEdges(const VertexDescriptor& source) const { return EdgeIterator(edges_+end_[source]); } template std::size_t SubGraph::noVertices() const { return noVertices_; } template inline typename SubGraph::VertexDescriptor SubGraph::maxVertex() const { return maxVertex_; } template inline std::size_t SubGraph::noEdges() const { return noEdges_; } template inline typename SubGraph::EdgeDescriptor SubGraph::findEdge(const VertexDescriptor& source, const VertexDescriptor& target) const { const EdgeDescriptor edge = std::lower_bound(edges_+start_[source], edges_+end_[source], target); if(edge==edges_+end_[source] || *edge!=target) return std::numeric_limits::max(); return edge; } template SubGraph::~SubGraph() { delete[] edges_; delete[] end_; delete[] start_; } template SubGraph::SubGraph(const G& graph, const T& excluded) : excluded_(excluded), noVertices_(0), endVertex_(0), maxVertex_(graph.maxVertex()) { start_ = new std::ptrdiff_t[graph.noVertices()]; end_ = new std::ptrdiff_t[graph.noVertices()]; edges_ = new VertexDescriptor[graph.noEdges()]; VertexDescriptor* edge=edges_; // Cater for the case that there are no vertices. // Otherwise endVertex_ will get 1 below. if ( graph.noVertices() == 0) return; typedef typename Graph::ConstVertexIterator Iterator; Iterator endVertex=graph.end(); for(Iterator vertex = graph.begin(); vertex != endVertex; ++vertex) if(excluded_[*vertex]) start_[*vertex]=end_[*vertex]=-1; else{ ++noVertices_; endVertex_ = std::max(*vertex, endVertex_); start_[*vertex] = edge-edges_; auto endEdge = vertex.end(); for(auto iter=vertex.begin(); iter!= endEdge; ++iter) if(!excluded[iter.target()]) { *edge = iter.target(); ++edge; } end_[*vertex] = edge - edges_; // Sort the edges std::sort(edges_+start_[*vertex], edge); } noEdges_ = edge-edges_; ++endVertex_; } template inline std::size_t VertexPropertiesGraph::noEdges() const { return graph_.noEdges(); } template inline typename VertexPropertiesGraph::EdgeIterator VertexPropertiesGraph::beginEdges(const VertexDescriptor& source) { return graph_.beginEdges(source); } template inline typename VertexPropertiesGraph::EdgeIterator VertexPropertiesGraph::endEdges(const VertexDescriptor& source) { return graph_.endEdges(source); } template typename VertexPropertiesGraph::ConstEdgeIterator inline VertexPropertiesGraph::beginEdges(const VertexDescriptor& source) const { return graph_.beginEdges(source); } template typename VertexPropertiesGraph::ConstEdgeIterator VertexPropertiesGraph::endEdges(const VertexDescriptor& source) const { return graph_.endEdges(source); } template template VertexPropertiesGraph::VertexIteratorT ::VertexIteratorT(const Father& iter, C* graph) : Father(iter), graph_(graph) {} template template VertexPropertiesGraph::VertexIteratorT ::VertexIteratorT(const Father& iter) : Father(iter) {} template template template VertexPropertiesGraph::VertexIteratorT ::VertexIteratorT(const VertexIteratorT& other) : Father(other), graph_(other.graph_) {} template template typename std::conditional::type>::value, V&, const V&>::type inline VertexPropertiesGraph::VertexIteratorT::properties() const { return graph_->getVertexProperties(Father::operator*()); } template template typename std::conditional::type, C>::value, typename G::EdgeIterator, typename G::ConstEdgeIterator>::type inline VertexPropertiesGraph::VertexIteratorT::begin() const { return graph_->beginEdges(Father::operator*()); } template template typename std::conditional::type, C>::value, typename G::EdgeIterator, typename G::ConstEdgeIterator>::type inline VertexPropertiesGraph::VertexIteratorT::end() const { return graph_->endEdges(Father::operator*()); } template inline typename VertexPropertiesGraph::VertexIterator VertexPropertiesGraph::begin() { return VertexIterator(graph_.begin(), this); } template inline typename VertexPropertiesGraph::VertexIterator VertexPropertiesGraph::end() { return VertexIterator(graph_.end()); } template inline typename VertexPropertiesGraph::ConstVertexIterator VertexPropertiesGraph::begin() const { return ConstVertexIterator(graph_.begin(), this); } template inline typename VertexPropertiesGraph::ConstVertexIterator VertexPropertiesGraph::end() const { return ConstVertexIterator(graph_.end()); } template inline V& VertexPropertiesGraph::getVertexProperties(const VertexDescriptor& vertex) { return vertexProperties_[vmap_[vertex]]; } template inline const V& VertexPropertiesGraph::getVertexProperties(const VertexDescriptor& vertex) const { return vertexProperties_[vmap_[vertex]]; } template inline const G& VertexPropertiesGraph::graph() const { return graph_; } template inline std::size_t VertexPropertiesGraph::noVertices() const { return graph_.noVertices(); } template inline typename VertexPropertiesGraph::VertexDescriptor VertexPropertiesGraph::maxVertex() const { return graph_.maxVertex(); } template VertexPropertiesGraph::VertexPropertiesGraph(Graph& graph, const VM vmap) : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V()) {} template template PropertiesGraph::EdgeIteratorT::EdgeIteratorT(const Father& iter, C* graph) : Father(iter), graph_(graph) {} template template PropertiesGraph::EdgeIteratorT::EdgeIteratorT(const Father& iter) : Father(iter) {} template template template PropertiesGraph::EdgeIteratorT::EdgeIteratorT(const EdgeIteratorT& other) : Father(other), graph_(other.graph_) {} template inline std::size_t PropertiesGraph::noEdges() const { return graph_.noEdges(); } template template inline typename std::conditional::type>::value,E&,const E&>::type PropertiesGraph::EdgeIteratorT::properties() const { return graph_->getEdgeProperties(Father::operator*()); } template inline typename PropertiesGraph::EdgeIterator PropertiesGraph::beginEdges(const VertexDescriptor& source) { return EdgeIterator(graph_.beginEdges(source), this); } template inline typename PropertiesGraph::EdgeIterator PropertiesGraph::endEdges(const VertexDescriptor& source) { return EdgeIterator(graph_.endEdges(source)); } template typename PropertiesGraph::ConstEdgeIterator inline PropertiesGraph::beginEdges(const VertexDescriptor& source) const { return ConstEdgeIterator(graph_.beginEdges(source), this); } template typename PropertiesGraph::ConstEdgeIterator PropertiesGraph::endEdges(const VertexDescriptor& source) const { return ConstEdgeIterator(graph_.endEdges(source)); } template template PropertiesGraph::VertexIteratorT ::VertexIteratorT(const Father& iter, C* graph) : Father(iter), graph_(graph) {} template template PropertiesGraph::VertexIteratorT ::VertexIteratorT(const Father& iter) : Father(iter) {} template template template PropertiesGraph::VertexIteratorT ::VertexIteratorT(const VertexIteratorT& other) : Father(other), graph_(other.graph_) {} template template inline typename std::conditional::type>::value, V&, const V&>::type PropertiesGraph::VertexIteratorT::properties() const { return graph_->getVertexProperties(Father::operator*()); } template template inline typename PropertiesGraph::template EdgeIteratorT PropertiesGraph::VertexIteratorT::begin() const { return graph_->beginEdges(Father::operator*()); } template template inline typename PropertiesGraph::template EdgeIteratorT PropertiesGraph::VertexIteratorT::end() const { return graph_->endEdges(Father::operator*()); } template inline typename PropertiesGraph::VertexIterator PropertiesGraph::begin() { return VertexIterator(graph_.begin(), this); } template inline typename PropertiesGraph::VertexIterator PropertiesGraph::end() { return VertexIterator(graph_.end()); } template inline typename PropertiesGraph::ConstVertexIterator PropertiesGraph::begin() const { return ConstVertexIterator(graph_.begin(), this); } template inline typename PropertiesGraph::ConstVertexIterator PropertiesGraph::end() const { return ConstVertexIterator(graph_.end()); } template inline V& PropertiesGraph::getVertexProperties(const VertexDescriptor& vertex) { return vertexProperties_[vmap_[vertex]]; } template inline const V& PropertiesGraph::getVertexProperties(const VertexDescriptor& vertex) const { return vertexProperties_[vmap_[vertex]]; } template inline E& PropertiesGraph::getEdgeProperties(const EdgeDescriptor& edge) { return edgeProperties_[emap_[edge]]; } template inline const E& PropertiesGraph::getEdgeProperties(const EdgeDescriptor& edge) const { return edgeProperties_[emap_[edge]]; } template inline E& PropertiesGraph::getEdgeProperties(const VertexDescriptor& source, const VertexDescriptor& target) { return getEdgeProperties(graph_.findEdge(source,target)); } template inline const E& PropertiesGraph::getEdgeProperties(const VertexDescriptor& source, const VertexDescriptor& target) const { return getEdgeProperties(graph_.findEdge(source,target)); } template inline const G& PropertiesGraph::graph() const { return graph_; } template inline std::size_t PropertiesGraph::noVertices() const { return graph_.noVertices(); } template inline typename PropertiesGraph::VertexDescriptor PropertiesGraph::maxVertex() const { return graph_.maxVertex(); } template PropertiesGraph::PropertiesGraph(Graph& graph, const VM& vmap, const EM& emap) : graph_(graph), vmap_(vmap), vertexProperties_(vmap_[graph_.maxVertex()+1], V()), emap_(emap), edgeProperties_(graph_.noEdges(), E()) {} template inline int visitNeighbours(const G& graph, const typename G::VertexDescriptor& vertex, V& visitor) { typedef typename G::ConstEdgeIterator iterator; const iterator end = graph.endEdges(vertex); int noNeighbours=0; for(iterator edge = graph.beginEdges(vertex); edge != end; ++edge, ++noNeighbours) visitor(edge); return noNeighbours; } #endif // DOXYGEN /** @} */ } } #endif