// 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_AGGREGATES_HH #define DUNE_AMG_AGGREGATES_HH #include "parameters.hh" #include "graph.hh" #include "properties.hh" #include "combinedfunctor.hh" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace Dune { namespace Amg { /** * @addtogroup ISTL_PAAMG * * @{ */ /** @file * @author Markus Blatt * @brief Provides classes for the Coloring process of AMG */ /** * @brief Base class of all aggregation criterions. */ template class AggregationCriterion : public T { public: /** * @brief The policy for calculating the dependency graph. */ typedef T DependencyPolicy; /** * @brief Constructor. * * The parameters will be initialized with default values suitable * for 2D isotropic problems. * * If that does not fit your needs either use setDefaultValuesIsotropic * setDefaultValuesAnisotropic or setup the values by hand */ AggregationCriterion() : T() {} AggregationCriterion(const Parameters& parms) : T(parms) {} /** * @brief Sets reasonable default values for an isotropic problem. * * Reasonable means that we should end up with cube aggregates of * diameter 2. * * @param dim The dimension of the problem. * @param diameter The preferred diameter for the aggregation. */ void setDefaultValuesIsotropic(std::size_t dim, std::size_t diameter=2) { this->setMaxDistance(diameter-1); std::size_t csize=1; for(; dim>0; dim--) { csize*=diameter; this->setMaxDistance(this->maxDistance()+diameter-1); } this->setMinAggregateSize(csize); this->setMaxAggregateSize(static_cast(csize*1.5)); } /** * @brief Sets reasonable default values for an aisotropic problem. * * Reasonable means that we should end up with cube aggregates with * sides of diameter 2 and sides in one dimension that are longer * (e.g. for 3D: 2x2x3). * * @param dim The dimension of the problem. * @param diameter The preferred diameter for the aggregation. */ void setDefaultValuesAnisotropic(std::size_t dim,std::size_t diameter=2) { setDefaultValuesIsotropic(dim, diameter); this->setMaxDistance(this->maxDistance()+dim-1); } }; template std::ostream& operator<<(std::ostream& os, const AggregationCriterion& criterion) { os<<"{ maxdistance="< class SymmetricMatrixDependency : public Dune::Amg::Parameters { public: /** * @brief The matrix type we build the dependency of. */ typedef M Matrix; /** * @brief The norm to use for examining the matrix entries. */ typedef N Norm; /** * @brief Constant Row iterator of the matrix. */ typedef typename Matrix::row_type Row; /** * @brief Constant column iterator of the matrix. */ typedef typename Matrix::ConstColIterator ColIter; void init(const Matrix* matrix); void initRow(const Row& row, int index); void examine(const ColIter& col); template void examine(G& graph, const typename G::EdgeIterator& edge, const ColIter& col); bool isIsolated(); SymmetricMatrixDependency(const Parameters& parms) : Parameters(parms) {} SymmetricMatrixDependency() : Parameters() {} protected: /** @brief The matrix we work on. */ const Matrix* matrix_; /** @brief The current max value.*/ typedef typename Matrix::field_type field_type; typedef typename FieldTraits::real_type real_type; real_type maxValue_; /** @brief The functor for calculating the norm. */ Norm norm_; /** @brief index of the currently evaluated row. */ int row_; /** @brief The norm of the current diagonal. */ real_type diagonal_; std::vector vals_; typename std::vector::iterator valIter_; }; template inline void SymmetricMatrixDependency::init(const Matrix* matrix) { matrix_ = matrix; } template inline void SymmetricMatrixDependency::initRow(const Row& row, int index) { using std::min; vals_.assign(row.size(), 0.0); assert(vals_.size()==row.size()); valIter_=vals_.begin(); maxValue_ = min(- std::numeric_limits::max(), std::numeric_limits::min()); diagonal_=norm_(row[index]); row_ = index; } template inline void SymmetricMatrixDependency::examine(const ColIter& col) { using std::max; // skip positive offdiagonals if norm preserves sign of them. real_type eij = norm_(*col); if(!N::is_sign_preserving || eij<0) // || eji<0) { *valIter_ = eij/diagonal_*eij/norm_(matrix_->operator[](col.index())[col.index()]); maxValue_ = max(maxValue_, *valIter_); }else *valIter_ =0; ++valIter_; } template template inline void SymmetricMatrixDependency::examine(G&, const typename G::EdgeIterator& edge, const ColIter&) { if(*valIter_ > alpha() * maxValue_) { edge.properties().setDepends(); edge.properties().setInfluences(); } ++valIter_; } template inline bool SymmetricMatrixDependency::isIsolated() { if(diagonal_==0) DUNE_THROW(Dune::ISTLError, "No diagonal entry for row "< class Dependency : public Parameters { public: /** * @brief The matrix type we build the dependency of. */ typedef M Matrix; /** * @brief The norm to use for examining the matrix entries. */ typedef N Norm; /** * @brief Constant Row iterator of the matrix. */ typedef typename Matrix::row_type Row; /** * @brief Constant column iterator of the matrix. */ typedef typename Matrix::ConstColIterator ColIter; void init(const Matrix* matrix); void initRow(const Row& row, int index); void examine(const ColIter& col); template void examine(G& graph, const typename G::EdgeIterator& edge, const ColIter& col); bool isIsolated(); Dependency(const Parameters& parms) : Parameters(parms) {} Dependency() : Parameters() {} protected: /** @brief The matrix we work on. */ const Matrix* matrix_; /** @brief The current max value.*/ typedef typename Matrix::field_type field_type; typedef typename FieldTraits::real_type real_type; real_type maxValue_; /** @brief The functor for calculating the norm. */ Norm norm_; /** @brief index of the currently evaluated row. */ int row_; /** @brief The norm of the current diagonal. */ real_type diagonal_; }; /** * @brief Dependency policy for symmetric matrices. */ template class SymmetricDependency : public Parameters { public: /** * @brief The matrix type we build the dependency of. */ typedef M Matrix; /** * @brief The norm to use for examining the matrix entries. */ typedef N Norm; /** * @brief Constant Row iterator of the matrix. */ typedef typename Matrix::row_type Row; /** * @brief Constant column iterator of the matrix. */ typedef typename Matrix::ConstColIterator ColIter; void init(const Matrix* matrix); void initRow(const Row& row, int index); void examine(const ColIter& col); template void examine(G& graph, const typename G::EdgeIterator& edge, const ColIter& col); bool isIsolated(); SymmetricDependency(const Parameters& parms) : Parameters(parms) {} SymmetricDependency() : Parameters() {} protected: /** @brief The matrix we work on. */ const Matrix* matrix_; /** @brief The current max value.*/ typedef typename Matrix::field_type field_type; typedef typename FieldTraits::real_type real_type; real_type maxValue_; /** @brief The functor for calculating the norm. */ Norm norm_; /** @brief index of the currently evaluated row. */ int row_; /** @brief The norm of the current diagonal. */ real_type diagonal_; private: void initRow(const Row& row, int index, const std::true_type&); void initRow(const Row& row, int index, const std::false_type&); }; /** * @brief Norm that uses only the [N][N] entry of the block to determine couplings. * */ template class Diagonal { public: enum { /* @brief We preserve the sign.*/ is_sign_preserving = true }; /** * @brief compute the norm of a matrix. * @param m The matrix to compute the norm of */ template typename FieldTraits::real_type operator()(const M& m, [[maybe_unused]] typename std::enable_if_t::value>* sfinae = nullptr) const { typedef typename M::field_type field_type; typedef typename FieldTraits::real_type real_type; static_assert( std::is_convertible::value, "use of diagonal norm in AMG not implemented for complex field_type"); return m[N][N]; // possible implementation for complex types: return signed_abs(m[N][N]); } /** * @brief Compute the norm of a scalar * @param m The scalar to compute the norm of */ template auto operator()(const M& m, typename std::enable_if_t::value>* /*sfinae*/ = nullptr) const { typedef typename FieldTraits::real_type real_type; static_assert( std::is_convertible::value, "use of diagonal norm in AMG not implemented for complex field_type"); return m; // possible implementation for complex types: return signed_abs(m[N][N]); } private: //! return sign * abs_value; for real numbers this is just v template static T signed_abs(const T & v) { return v; } //! return sign * abs_value; for complex numbers this is csgn(v) * abs(v) template static T signed_abs(const std::complex & v) { // return sign * abs_value // in case of complex numbers this extends to using the csgn function to determine the sign return csgn(v) * std::abs(v); } //! sign function for complex numbers; for real numbers we assume imag(v) = 0 template static T csgn(const T & v) { return (T(0) < v) - (v < T(0)); } //! sign function for complex numbers template static T csgn(std::complex a) { return csgn(a.real())+(a.real() == 0.0)*csgn(a.imag()); } }; /** * @brief Norm that uses only the [0][0] entry of the block to determine couplings. * */ class FirstDiagonal : public Diagonal<0> {}; /** * @brief Functor using the row sum (infinity) norm to determine strong couplings. * * The is proposed by several people for elasticity problems. */ struct RowSum { enum { /* @brief We preserve the sign.*/ is_sign_preserving = false }; /** * @brief compute the norm of a matrix. * @param m The matrix row to compute the norm of. */ template auto operator()(const M& m) const { using std::abs; if constexpr(Dune::IsNumber::value) return abs(m); else return m.infinity_norm(); } }; struct FrobeniusNorm { enum { /* @brief We preserve the sign.*/ is_sign_preserving = false }; /** * @brief compute the norm of a matrix. * @param m The matrix row to compute the norm of. */ template typename FieldTraits::real_type operator()(const M& m) const { return m.frobenius_norm(); } }; struct AlwaysOneNorm { enum { /* @brief We preserve the sign.*/ is_sign_preserving = false }; /** * @brief compute the norm of a matrix. * @param m The matrix row to compute the norm of. */ template typename FieldTraits::real_type operator()(const M& /*m*/) const { return 1; } }; /** * @brief Criterion taking advantage of symmetric matrices. * * \tparam M The type of the matrix the amg coarsening works on, e.g. BCRSMatrix * \tparam Norm The norm to use to determine the strong couplings between the nodes, e.g. FirstDiagonal or RowSum. */ template class SymmetricCriterion : public AggregationCriterion > { public: SymmetricCriterion(const Parameters& parms) : AggregationCriterion >(parms) {} SymmetricCriterion() {} }; /** * @brief Criterion suitable for unsymmetric matrices. * * Nevertheless the sparsity pattern has to be symmetric. * * \tparam M The type of the matrix the amg coarsening works on, e.g. BCRSMatrix * \tparam Norm The norm to use to determine the strong couplings between the nodes, e.g. FirstDiagonal or RowSum. */ template class UnSymmetricCriterion : public AggregationCriterion > { public: UnSymmetricCriterion(const Parameters& parms) : AggregationCriterion >(parms) {} UnSymmetricCriterion() {} }; // forward declaration template class Aggregator; /** * @brief Class providing information about the mapping of * the vertices onto aggregates. * * It is assumed that the vertices are consecutively numbered * from 0 to the maximum vertex number. */ template class AggregatesMap { public: /** * @brief Identifier of not yet aggregated vertices. */ static const V UNAGGREGATED; /** * @brief Identifier of isolated vertices. */ static const V ISOLATED; /** * @brief The vertex descriptor type. */ typedef V VertexDescriptor; /** * @brief The aggregate descriptor type. */ typedef V AggregateDescriptor; /** * @brief The allocator we use for our lists and the * set. */ typedef PoolAllocator Allocator; /** * @brief The type of a single linked list of vertex * descriptors. */ typedef SLList VertexList; /** * @brief A Dummy visitor that does nothing for each visited edge. */ class DummyEdgeVisitor { public: template void operator()([[maybe_unused]] const EdgeIterator& edge) const {} }; /** * @brief Constructs without allocating memory. */ AggregatesMap(); /** * @brief Constructs with allocating memory. * @param noVertices The number of vertices we will hold information * for. */ AggregatesMap(std::size_t noVertices); /** * @brief Destructor. */ ~AggregatesMap(); /** * @brief Build the aggregates. * @param matrix The matrix describing the dependency. * @param graph The graph corresponding to the matrix. * @param criterion The aggregation criterion. * @param finestLevel Whether this the finest level. In that case rows representing * Dirichlet boundaries will be detected and ignored during aggregation. * @return A tuple of the total number of aggregates, the number of isolated aggregates, the * number of isolated aggregates, the number of aggregates consisting only of one vertex, and * the number of skipped aggregates built. */ template std::tuple buildAggregates(const M& matrix, G& graph, const C& criterion, bool finestLevel); /** * @brief Breadth first search within an aggregate * * \tparam reset If true the visited flags of the vertices * will be reset after the search * \tparam G The type of the graph we perform the search on * \tparam F The type of the visitor to operate on the vertices * * @param start The vertex where the search should start * from. This does not need to belong to the aggregate. * @param aggregate The aggregate id. * @param graph The matrix graph to perform the search on. * @param visitedMap A map to mark the already visited vertices * @param aggregateVisitor A functor that is called with * each G::ConstEdgeIterator with an edge pointing to the * aggregate. Use DummyVisitor if these are of no interest. */ template std::size_t breadthFirstSearch(const VertexDescriptor& start, const AggregateDescriptor& aggregate, const G& graph, F& aggregateVisitor, VM& visitedMap) const; /** * @brief Breadth first search within an aggregate * * \tparam L A container type providing push_back(Vertex), and * pop_front() in case remove is true * \tparam remove If true the entries in the visited list * will be removed. * \tparam reset If true the visited flag will be reset after * the search * * @param start The vertex where the search should start * from. This does not need to belong to the aggregate. * @param aggregate The aggregate id. * @param graph The matrix graph to perform the search on. * @param visited A list to store the visited vertices in. * @param aggregateVisitor A functor that is called with * each G::ConstEdgeIterator with an edge pointing to the * aggregate. Use DummyVisitor these are of no interest. * @param nonAggregateVisitor A functor that is called with * each G::ConstEdgeIterator with an edge pointing to another * aggregate. Use DummyVisitor these are of no interest. * @param visitedMap A map to mark the already visited vertices */ template std::size_t breadthFirstSearch(const VertexDescriptor& start, const AggregateDescriptor& aggregate, const G& graph, L& visited, F1& aggregateVisitor, F2& nonAggregateVisitor, VM& visitedMap) const; /** * @brief Allocate memory for holding the information. * @param noVertices The total number of vertices to be * mapped. */ void allocate(std::size_t noVertices); /** * @brief Get the number of vertices. */ std::size_t noVertices() const; /** * @brief Free the allocated memory. */ void free(); /** * @brief Get the aggregate a vertex belongs to. * @param v The vertex we want to know the aggregate of. * @return The aggregate the vertex is mapped to. */ AggregateDescriptor& operator[](const VertexDescriptor& v); /** * @brief Get the aggregate a vertex belongs to. * @param v The vertex we want to know the aggregate of. * @return The aggregate the vertex is mapped to. */ const AggregateDescriptor& operator[](const VertexDescriptor& v) const; typedef const AggregateDescriptor* const_iterator; const_iterator begin() const { return aggregates_; } const_iterator end() const { return aggregates_+noVertices(); } typedef AggregateDescriptor* iterator; iterator begin() { return aggregates_; } iterator end() { return aggregates_+noVertices(); } private: /** @brief Prevent copying. */ AggregatesMap(const AggregatesMap&) = delete; /** @brief Prevent assignment. */ AggregatesMap& operator=(const AggregatesMap&) = delete; /** * @brief The aggregates the vertices belong to. */ AggregateDescriptor* aggregates_; /** * @brief The number of vertices in the map. */ std::size_t noVertices_; }; /** * @brief Build the dependency of the matrix graph. */ template void buildDependency(G& graph, const typename C::Matrix& matrix, C criterion, bool finestLevel); /** * @brief A class for temporarily storing the vertices of an * aggregate in. */ template class Aggregate { public: /*** * @brief The type of the matrix graph we work with. */ typedef G MatrixGraph; /** * @brief The vertex descriptor type. */ typedef typename MatrixGraph::VertexDescriptor Vertex; /** * @brief The allocator we use for our lists and the * set. */ typedef PoolAllocator Allocator; /** * @brief The type of a single linked list of vertex * descriptors. */ typedef S VertexSet; /** * @brief Type of size used by allocator of sllist */ using size_type = typename VertexSet::size_type; /** @brief Const iterator over a vertex list. */ typedef typename VertexSet::const_iterator const_iterator; /** * @brief Type of the mapping of aggregate members onto distance spheres. */ typedef std::size_t* SphereMap; /** * @brief Constructor. * @param graph The matrix graph we work on. * @param aggregates The mapping of vertices onto aggregates. * @param connectivity The set of vertices connected to the aggregate. * distance spheres. * @param front_ The vertices of the current aggregate front. */ Aggregate(MatrixGraph& graph, AggregatesMap& aggregates, VertexSet& connectivity, std::vector& front_); void invalidate() { --id_; } /** * @brief Reconstruct the aggregat from an seed node. * * Will determine all vertices of the same aggregate * and reference those. */ void reconstruct(const Vertex& vertex); /** * @brief Initialize the aggregate with one vertex. */ void seed(const Vertex& vertex); /** * @brief Add a vertex to the aggregate. */ void add(const Vertex& vertex); void add(std::vector& vertex); /** * @brief Clear the aggregate. */ void clear(); /** * @brief Get the size of the aggregate. */ size_type size(); /** * @brief Get the number of connections to other aggregates. */ size_type connectSize(); /** * @brief Get the id identifying the aggregate. */ int id(); /** @brief get an iterator over the vertices of the aggregate. */ const_iterator begin() const; /** @brief get an iterator over the vertices of the aggregate. */ const_iterator end() const; private: /** * @brief The vertices of the aggregate. */ VertexSet vertices_; /** * @brief The number of the currently referenced * aggregate. */ int id_; /** * @brief The matrix graph the aggregates live on. */ MatrixGraph& graph_; /** * @brief The aggregate mapping we build. */ AggregatesMap& aggregates_; /** * @brief The connections to other aggregates. */ VertexSet& connected_; /** * @brief The vertices of the current aggregate front. */ std::vector& front_; }; /** * @brief Class for building the aggregates. */ template class Aggregator { public: /** * @brief The matrix graph type used. */ typedef G MatrixGraph; /** * @brief The vertex identifier */ typedef typename MatrixGraph::VertexDescriptor Vertex; /** @brief The type of the aggregate descriptor. */ typedef typename MatrixGraph::VertexDescriptor AggregateDescriptor; /** * @brief Constructor. */ Aggregator(); /** * @brief Destructor. */ ~Aggregator(); /** * @brief Build the aggregates. * * \tparam C The type of the coarsening Criterion to use * * @param m The matrix to build the aggregates accordingly. * @param graph A (sub) graph of the matrix. * @param aggregates Aggregate map we will build. All entries should be initialized * to UNAGGREGATED! * @param c The coarsening criterion to use. * @param finestLevel Whether this the finest level. In that case rows representing * Dirichlet boundaries will be detected and ignored during aggregation. * @return A tuple of the total number of aggregates, the number of isolated aggregates, the * number of isolated aggregates, the number of aggregates consisting only of one vertex, and * the number of skipped aggregates built. */ template std::tuple build(const M& m, G& graph, AggregatesMap& aggregates, const C& c, bool finestLevel); private: /** * @brief The allocator we use for our lists and the * set. */ typedef PoolAllocator Allocator; /** * @brief The single linked list we use. */ typedef SLList VertexList; /** * @brief The set of vertices we use. */ typedef std::set,Allocator> VertexSet; /** * @brief The type of mapping of aggregate members to spheres. */ typedef std::size_t* SphereMap; /** * @brief The graph we aggregate for. */ MatrixGraph* graph_; /** * @brief The vertices of the current aggregate- */ Aggregate* aggregate_; /** * @brief The vertices of the current aggregate front. */ std::vector front_; /** * @brief The set of connected vertices. */ VertexSet connected_; /** * @brief Number of vertices mapped. */ int size_; /** * @brief Stack. */ class Stack { public: static const Vertex NullEntry; Stack(const MatrixGraph& graph, const Aggregator& aggregatesBuilder, const AggregatesMap& aggregates); ~Stack(); Vertex pop(); private: enum { N = 1300000 }; /** @brief The graph we work on. */ const MatrixGraph& graph_; /** @brief The aggregates builder. */ const Aggregator& aggregatesBuilder_; /** @brief The aggregates information. */ const AggregatesMap& aggregates_; /** @brief The current size. */ int size_; Vertex maxSize_; /** @brief The index of the top element. */ typename MatrixGraph::ConstVertexIterator begin_; typename MatrixGraph::ConstVertexIterator end_; /** @brief The values on the stack. */ Vertex* vals_; }; friend class Stack; /** * @brief Visits all neighbours of vertex belonging to a * specific aggregate. * * @param vertex The vertex whose neighbours we want to * visit. * @param aggregate The id of the aggregate. * @param visitor The visitor evaluated for each EdgeIterator * (by its method operator()(ConstEdgeIterator edge) */ template void visitAggregateNeighbours(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates, V& visitor) const; /** * @brief An Adaptor for vsitors that only * evaluates edges pointing to a specific aggregate. */ template class AggregateVisitor { public: /** * @brief The type of the adapted visitor */ typedef V Visitor; /** * @brief Constructor. * @param aggregates The aggregate numbers of the * vertices. * @param aggregate The id of the aggregate to visit. * @param visitor The visitor. */ AggregateVisitor(const AggregatesMap& aggregates, const AggregateDescriptor& aggregate, Visitor& visitor); /** * @brief Examine an edge. * * The edge will be examined by the adapted visitor if * it belongs to the right aggregate. */ void operator()(const typename MatrixGraph::ConstEdgeIterator& edge); private: /** @brief Mapping of vertices to aggregates. */ const AggregatesMap& aggregates_; /** @brief The aggregate id we want to visit. */ AggregateDescriptor aggregate_; /** @brief The visitor to use on the aggregate. */ Visitor* visitor_; }; /** * @brief A simple counter functor. */ class Counter { public: /** @brief Constructor */ Counter(); /** @brief Access the current count. */ int value(); protected: /** @brief Increment counter */ void increment(); /** @brief Decrement counter */ void decrement(); private: int count_; }; /** * @brief Counts the number of edges to vertices belonging * to the aggregate front. */ class FrontNeighbourCounter : public Counter { public: /** * @brief Constructor. * @param front The vertices of the front. */ FrontNeighbourCounter(const MatrixGraph& front); void operator()(const typename MatrixGraph::ConstEdgeIterator& edge); private: const MatrixGraph& graph_; }; /** * @brief Count the number of neighbours of a vertex that belong * to the aggregate front. */ int noFrontNeighbours(const Vertex& vertex) const; /** * @brief Counter of TwoWayConnections. */ class TwoWayCounter : public Counter { public: void operator()(const typename MatrixGraph::ConstEdgeIterator& edge); }; /** * @brief Count the number of twoway connection from * a vertex to an aggregate. * * @param vertex The vertex whose connections are counted. * @param aggregate The id of the aggregate the connections * should point to. * @param aggregates The mapping of the vertices onto aggregates. * @return The number of one way connections from the vertex to * the aggregate. */ int twoWayConnections(const Vertex&, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const; /** * @brief Counter of OneWayConnections. */ class OneWayCounter : public Counter { public: void operator()(const typename MatrixGraph::ConstEdgeIterator& edge); }; /** * @brief Count the number of oneway connection from * a vertex to an aggregate. * * @param vertex The vertex whose connections are counted. * @param aggregate The id of the aggregate the connections * should point to. * @param aggregates The mapping of the vertices onto aggregates. * @return The number of one way connections from the vertex to * the aggregate. */ int oneWayConnections(const Vertex&, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const; /** * @brief Connectivity counter * * Increments count if the neighbour is already known as * connected or is not yet aggregated. */ class ConnectivityCounter : public Counter { public: /** * @brief Constructor. * @param connected The set of connected aggregates. * @param aggregates The mapping of aggregates to vertices. */ ConnectivityCounter(const VertexSet& connected, const AggregatesMap& aggregates); void operator()(const typename MatrixGraph::ConstEdgeIterator& edge); private: /** @brief The connected aggregates. */ const VertexSet& connected_; /** @brief The mapping of vertices to aggregates. */ const AggregatesMap& aggregates_; }; /** * @brief Get the connectivity of a vertex. * * For each unaggregated neighbour or neighbour of an aggregate * that is already known as connected the count is increased by * one. In all other cases by two. * * @param vertex The vertex whose connectivity we want. * @param aggregates The mapping of the vertices onto the aggregates. * @return The value of the connectivity. */ double connectivity(const Vertex& vertex, const AggregatesMap& aggregates) const; /** * @brief Test whether the vertex is connected to the aggregate. * @param vertex The vertex descriptor. * @param aggregate The aggregate descriptor. * @param aggregates The mapping of the vertices onto the aggregates. * @return True if there is a connection to the aggregate. */ bool connected(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const; /** * @brief Test whether the vertex is connected to an aggregate of a list. * @param vertex The vertex descriptor. * @param aggregateList The list of aggregate descriptors. * @param aggregates The mapping of the vertices onto the aggregates. * @return True if there is a connection to the aggregate. */ bool connected(const Vertex& vertex, const SLList& aggregateList, const AggregatesMap& aggregates) const; /** * @brief Counts the edges depending on the dependency. * * If the influence flag of the edge is set the counter is * increased and/or if the depends flag is set it is * incremented, too. */ class DependencyCounter : public Counter { public: /** * @brief Constructor. */ DependencyCounter(); void operator()(const typename MatrixGraph::ConstEdgeIterator& edge); }; /** * @brief Adds the targets of each edge to * the list of front vertices. * * Vertices already marked as front nodes will not get added. */ class FrontMarker { public: /** * @brief Constructor. * * @param front The list to store the front vertices in. * @param graph The matrix graph we work on. */ FrontMarker(std::vector& front, MatrixGraph& graph); void operator()(const typename MatrixGraph::ConstEdgeIterator& edge); private: /** @brief The list of front vertices. */ std::vector& front_; /** @brief The matrix graph we work on. */ MatrixGraph& graph_; }; /** * @brief Unmarks all front vertices. */ void unmarkFront(); /** * @brief counts the dependency between a vertex and unaggregated * neighbours. * * If the influence flag of the edge is set the counter is * increased and/or if the depends flag is set it is * incremented, too. * * @param vertex The vertex whose neighbours we count. * @param aggregates The mapping of the vertices onto the aggregates. * @return The sum of the number of unaggregated * neighbours the vertex depends on and the number of unaggregated * neighbours the vertex influences. */ int unusedNeighbours(const Vertex& vertex, const AggregatesMap& aggregates) const; /** * @brief Count connections to neighbours. * * Counts the number of strong connections of a vertex to vertices * that are not yet aggregated * and the ones that belong to specific aggregate. * * @param vertex The vertex that we count the neighbours of. * @param aggregates The mapping of the vertices into aggregates. * @param aggregate The descriptor of the aggregate. * @return The pair of number of connections to unaggregate vertices * and number of connections to vertices of the specific aggregate. */ std::pair neighbours(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const; /** * @brief Counts the number of neighbours belonging to an aggregate. * * * If the influence flag of the edge is set the counter is * increased and/or if the depends flag is set it is * incremented, too. * * @param vertex The vertex whose neighbours we count. * @param aggregate The aggregate id. * @param aggregates The mapping of the vertices onto the aggregates. * @return The sum of the number of * neighbours belonging to the aggregate * the vertex depends on and the number of * neighbours of the aggregate the vertex influences. */ int aggregateNeighbours(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const; /** * @brief Checks whether a vertex is admissible to be added to an aggregate. * * @param vertex The vertex whose admissibility id to be checked. * @param aggregate The id of the aggregate. * @param aggregates The mapping of the vertices onto aggregates. */ bool admissible(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const; /** * @brief The maximum distance of the vertex to any vertex in the * current aggregate. * * @return The maximum of all shortest paths from the vertex to any * vertex of the aggregate. */ std::size_t distance(const Vertex& vertex, const AggregatesMap& aggregates); /** * @brief Find a strongly connected cluster of a vertex. * * @param vertex The vertex whose neighbouring aggregate we search. * @param aggregates The mapping of the vertices onto aggregates. * @return A vertex of neighbouring aggregate the vertex is allowed to * be added to. */ Vertex mergeNeighbour(const Vertex& vertex, const AggregatesMap& aggregates) const; /** * @brief Find a nonisolated connected aggregate. * * @param vertex The vertex whose neighbouring aggregate we search. * @param aggregates The mapping of the vertices onto aggregates. * @param[out] list to store the vertices of neighbouring aggregates the vertex is allowed to * be added to. */ void nonisoNeighbourAggregate(const Vertex& vertex, const AggregatesMap& aggregates, SLList& neighbours) const; /** * @brief Grows the aggregate from a seed. * * @param seed The first vertex of the aggregate. * @param aggregates The mapping of he vertices onto the aggregates. * @param c The coarsen criterium. */ template void growAggregate(const Vertex& vertex, const AggregatesMap& aggregates, const C& c); template void growIsolatedAggregate(const Vertex& vertex, const AggregatesMap& aggregates, const C& c); }; #ifndef DOXYGEN template inline void SymmetricDependency::init(const Matrix* matrix) { matrix_ = matrix; } template inline void SymmetricDependency::initRow(const Row& row, int index) { initRow(row, index, std::is_convertible()); } template inline void SymmetricDependency::initRow(const Row& /*row*/, int /*index*/, const std::false_type&) { DUNE_THROW(InvalidStateException, "field_type needs to convertible to real_type"); } template inline void SymmetricDependency::initRow(const Row& /*row*/, int index, const std::true_type&) { using std::min; maxValue_ = min(- std::numeric_limits::max(), std::numeric_limits::min()); row_ = index; diagonal_ = norm_(matrix_->operator[](row_)[row_]); } template inline void SymmetricDependency::examine(const ColIter& col) { using std::max; real_type eij = norm_(*col); typename Matrix::ConstColIterator opposite_entry = matrix_->operator[](col.index()).find(row_); if ( opposite_entry == matrix_->operator[](col.index()).end() ) { // Consider this a weak connection we disregard. return; } real_type eji = norm_(*opposite_entry); // skip positive offdiagonals if norm preserves sign of them. if(!N::is_sign_preserving || eij<0 || eji<0) maxValue_ = max(maxValue_, eij /diagonal_ * eji/ norm_(matrix_->operator[](col.index())[col.index()])); } template template inline void SymmetricDependency::examine(G& graph, const typename G::EdgeIterator& edge, const ColIter& col) { real_type eij = norm_(*col); typename Matrix::ConstColIterator opposite_entry = matrix_->operator[](col.index()).find(row_); if ( opposite_entry == matrix_->operator[](col.index()).end() ) { // Consider this as a weak connection we disregard. return; } real_type eji = norm_(*opposite_entry); // skip positive offdiagonals if norm preserves sign of them. if(!N::is_sign_preserving || (eij<0 || eji<0)) if(eji / norm_(matrix_->operator[](edge.target())[edge.target()]) * eij/ diagonal_ > alpha() * maxValue_) { edge.properties().setDepends(); edge.properties().setInfluences(); typename G::EdgeProperties& other = graph.getEdgeProperties(edge.target(), edge.source()); other.setInfluences(); other.setDepends(); } } template inline bool SymmetricDependency::isIsolated() { return maxValue_ < beta(); } template inline void Dependency::init(const Matrix* matrix) { matrix_ = matrix; } template inline void Dependency::initRow([[maybe_unused]] const Row& row, int index) { using std::min; maxValue_ = min(- std::numeric_limits::max(), std::numeric_limits::min()); row_ = index; diagonal_ = norm_(matrix_->operator[](row_)[row_]); } template inline void Dependency::examine(const ColIter& col) { using std::max; maxValue_ = max(maxValue_, -norm_(*col)); } template template inline void Dependency::examine(G& graph, const typename G::EdgeIterator& edge, const ColIter& col) { if(-norm_(*col) >= maxValue_ * alpha()) { edge.properties().setDepends(); typedef typename G::EdgeDescriptor ED; ED e= graph.findEdge(edge.target(), edge.source()); if(e!=std::numeric_limits::max()) { typename G::EdgeProperties& other = graph.getEdgeProperties(e); other.setInfluences(); } } } template inline bool Dependency::isIsolated() { return maxValue_ < beta() * diagonal_; } template Aggregate::Aggregate(MatrixGraph& graph, AggregatesMap& aggregates, VertexSet& connected, std::vector& front) : vertices_(), id_(-1), graph_(graph), aggregates_(aggregates), connected_(connected), front_(front) {} template void Aggregate::reconstruct(const Vertex& /*vertex*/) { /* vertices_.push_back(vertex); typedef typename VertexList::const_iterator iterator; iterator begin = vertices_.begin(); iterator end = vertices_.end();*/ throw "Not yet implemented"; // while(begin!=end){ //for(); // } } template inline void Aggregate::seed(const Vertex& vertex) { dvverb<<"Connected cleared"<::UNAGGREGATED && !graph_.getVertexProperties(edge.target()).front()) { front_.push_back(edge.target()); graph_.getVertexProperties(edge.target()).setFront(); } dvverb <<" size="< inline void Aggregate::clear() { vertices_.clear(); connected_.clear(); id_=-1; } template inline typename Aggregate::size_type Aggregate::size() { return vertices_.size(); } template inline typename Aggregate::size_type Aggregate::connectSize() { return connected_.size(); } template inline int Aggregate::id() { return id_; } template inline typename Aggregate::const_iterator Aggregate::begin() const { return vertices_.begin(); } template inline typename Aggregate::const_iterator Aggregate::end() const { return vertices_.end(); } template const V AggregatesMap::UNAGGREGATED = std::numeric_limits::max(); template const V AggregatesMap::ISOLATED = std::numeric_limits::max()-1; template AggregatesMap::AggregatesMap() : aggregates_(0) {} template AggregatesMap::~AggregatesMap() { if(aggregates_!=0) delete[] aggregates_; } template inline AggregatesMap::AggregatesMap(std::size_t noVertices) { allocate(noVertices); } template inline std::size_t AggregatesMap::noVertices() const { return noVertices_; } template inline void AggregatesMap::allocate(std::size_t noVertices) { aggregates_ = new AggregateDescriptor[noVertices]; noVertices_ = noVertices; for(std::size_t i=0; i < noVertices; i++) aggregates_[i]=UNAGGREGATED; } template inline void AggregatesMap::free() { assert(aggregates_ != 0); delete[] aggregates_; aggregates_=0; } template inline typename AggregatesMap::AggregateDescriptor& AggregatesMap::operator[](const VertexDescriptor& v) { return aggregates_[v]; } template inline const typename AggregatesMap::AggregateDescriptor& AggregatesMap::operator[](const VertexDescriptor& v) const { return aggregates_[v]; } template template inline std::size_t AggregatesMap::breadthFirstSearch(const V& start, const AggregateDescriptor& aggregate, const G& graph, F& aggregateVisitor, VM& visitedMap) const { VertexList vlist; DummyEdgeVisitor dummy; return breadthFirstSearch(start, aggregate, graph, vlist, aggregateVisitor, dummy, visitedMap); } template template std::size_t AggregatesMap::breadthFirstSearch(const V& start, const AggregateDescriptor& aggregate, const G& graph, L& visited, F1& aggregateVisitor, F2& nonAggregateVisitor, VM& visitedMap) const { typedef typename L::const_iterator ListIterator; int visitedSpheres = 0; visited.push_back(start); put(visitedMap, start, true); ListIterator current = visited.begin(); ListIterator end = visited.end(); std::size_t i=0, size=visited.size(); // visit the neighbours of all vertices of the // current sphere. while(current != end) { for(; i Aggregator::Aggregator() : graph_(0), aggregate_(0), front_(), connected_(), size_(-1) {} template Aggregator::~Aggregator() { size_=-1; } template void buildDependency(G& graph, const typename C::Matrix& matrix, C criterion, bool firstlevel) { // assert(graph.isBuilt()); typedef typename C::Matrix Matrix; typedef typename G::VertexIterator VertexIterator; criterion.init(&matrix); for(VertexIterator vertex = graph.begin(); vertex != graph.end(); ++vertex) { typedef typename Matrix::row_type Row; const Row& row = matrix[*vertex]; // Tell the criterion what row we will examine now // This might for example be used for calculating the // maximum offdiagonal value criterion.initRow(row, *vertex); // On a first path all columns are examined. After this // the calculator should know whether the vertex is isolated. typedef typename Matrix::ConstColIterator ColIterator; ColIterator end = row.end(); typename FieldTraits::real_type absoffdiag=0.; using std::max; if(firstlevel) { for(ColIterator col = row.begin(); col != end; ++col) if(col.index()!=*vertex) { criterion.examine(col); absoffdiag = max(absoffdiag, Impl::asMatrix(*col).frobenius_norm()); } if(absoffdiag==0) vertex.properties().setExcludedBorder(); } else for(ColIterator col = row.begin(); col != end; ++col) if(col.index()!=*vertex) criterion.examine(col); // reset the vertex properties //vertex.properties().reset(); // Check whether the vertex is isolated. if(criterion.isIsolated()) { //std::cout<<"ISOLATED: "<<*vertex< template inline Aggregator::AggregateVisitor::AggregateVisitor(const AggregatesMap& aggregates, const AggregateDescriptor& aggregate, V& visitor) : aggregates_(aggregates), aggregate_(aggregate), visitor_(&visitor) {} template template inline void Aggregator::AggregateVisitor::operator()(const typename MatrixGraph::ConstEdgeIterator& edge) { if(aggregates_[edge.target()]==aggregate_) visitor_->operator()(edge); } template template inline void Aggregator::visitAggregateNeighbours(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates, V& visitor) const { // Only evaluates for edge pointing to the aggregate AggregateVisitor v(aggregates, aggregate, visitor); visitNeighbours(*graph_, vertex, v); } template inline Aggregator::Counter::Counter() : count_(0) {} template inline void Aggregator::Counter::increment() { ++count_; } template inline void Aggregator::Counter::decrement() { --count_; } template inline int Aggregator::Counter::value() { return count_; } template inline void Aggregator::TwoWayCounter::operator()(const typename MatrixGraph::ConstEdgeIterator& edge) { if(edge.properties().isTwoWay()) Counter::increment(); } template int Aggregator::twoWayConnections(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const { TwoWayCounter counter; visitAggregateNeighbours(vertex, aggregate, aggregates, counter); return counter.value(); } template int Aggregator::oneWayConnections(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const { OneWayCounter counter; visitAggregateNeighbours(vertex, aggregate, aggregates, counter); return counter.value(); } template inline void Aggregator::OneWayCounter::operator()(const typename MatrixGraph::ConstEdgeIterator& edge) { if(edge.properties().isOneWay()) Counter::increment(); } template inline Aggregator::ConnectivityCounter::ConnectivityCounter(const VertexSet& connected, const AggregatesMap& aggregates) : Counter(), connected_(connected), aggregates_(aggregates) {} template inline void Aggregator::ConnectivityCounter::operator()(const typename MatrixGraph::ConstEdgeIterator& edge) { if(connected_.find(aggregates_[edge.target()]) == connected_.end() || aggregates_[edge.target()]==AggregatesMap::UNAGGREGATED) // Would be a new connection Counter::increment(); else{ Counter::increment(); Counter::increment(); } } template inline double Aggregator::connectivity(const Vertex& vertex, const AggregatesMap& aggregates) const { ConnectivityCounter counter(connected_, aggregates); double noNeighbours=visitNeighbours(*graph_, vertex, counter); return (double)counter.value()/noNeighbours; } template inline Aggregator::DependencyCounter::DependencyCounter() : Counter() {} template inline void Aggregator::DependencyCounter::operator()(const typename MatrixGraph::ConstEdgeIterator& edge) { if(edge.properties().depends()) Counter::increment(); if(edge.properties().influences()) Counter::increment(); } template int Aggregator::unusedNeighbours(const Vertex& vertex, const AggregatesMap& aggregates) const { return aggregateNeighbours(vertex, AggregatesMap::UNAGGREGATED, aggregates); } template std::pair Aggregator::neighbours(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const { DependencyCounter unused, aggregated; typedef AggregateVisitor CounterT; typedef std::tuple CounterTuple; CombinedFunctor visitors(CounterTuple(CounterT(aggregates, AggregatesMap::UNAGGREGATED, unused), CounterT(aggregates, aggregate, aggregated))); visitNeighbours(*graph_, vertex, visitors); return std::make_pair(unused.value(), aggregated.value()); } template int Aggregator::aggregateNeighbours(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const { DependencyCounter counter; visitAggregateNeighbours(vertex, aggregate, aggregates, counter); return counter.value(); } template std::size_t Aggregator::distance(const Vertex& vertex, const AggregatesMap& aggregates) { return 0; typename PropertyMapTypeSelector::Type visitedMap = get(VertexVisitedTag(), *graph_); VertexList vlist; typename AggregatesMap::DummyEdgeVisitor dummy; return aggregates.template breadthFirstSearch(vertex, aggregate_->id(), *graph_, vlist, dummy, dummy, visitedMap); } template inline Aggregator::FrontMarker::FrontMarker(std::vector& front, MatrixGraph& graph) : front_(front), graph_(graph) {} template inline void Aggregator::FrontMarker::operator()(const typename MatrixGraph::ConstEdgeIterator& edge) { Vertex target = edge.target(); if(!graph_.getVertexProperties(target).front()) { front_.push_back(target); graph_.getVertexProperties(target).setFront(); } } template inline bool Aggregator::admissible(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const { // Todo Dune::dvverb<<" Admissible not yet implemented!"<endEdges(vertex); for(Iterator edge = graph_->beginEdges(vertex); edge != vend; ++edge) { // if(edge.properties().depends() && !edge.properties().influences() if(edge.properties().isStrong() && aggregates[edge.target()]==aggregate) { // Search for another link to the aggregate Iterator edge1 = edge; for(++edge1; edge1 != vend; ++edge1) { //if(edge1.properties().depends() && !edge1.properties().influences() if(edge1.properties().isStrong() && aggregates[edge.target()]==aggregate) { //Search for an edge connecting the two vertices that is //strong bool found=false; Iterator v2end = graph_->endEdges(edge.target()); for(Iterator edge2 = graph_->beginEdges(edge.target()); edge2 != v2end; ++edge2) { if(edge2.target()==edge1.target() && edge2.properties().isStrong()) { found =true; break; } } if(found) { return true; } } } } } // Situation 2: cluster node depends on front node and other cluster node /// Iterate over all all neighbours of front node vend = graph_->endEdges(vertex); for(Iterator edge = graph_->beginEdges(vertex); edge != vend; ++edge) { //if(!edge.properties().depends() && edge.properties().influences() if(edge.properties().isStrong() && aggregates[edge.target()]==aggregate) { // Search for a link from target that stays within the aggregate Iterator v1end = graph_->endEdges(edge.target()); for(Iterator edge1=graph_->beginEdges(edge.target()); edge1 != v1end; ++edge1) { //if(edge1.properties().depends() && !edge1.properties().influences() if(edge1.properties().isStrong() && aggregates[edge1.target()]==aggregate) { bool found=false; // Check if front node is also connected to this one Iterator v2end = graph_->endEdges(vertex); for(Iterator edge2 = graph_->beginEdges(vertex); edge2 != v2end; ++edge2) { if(edge2.target()==edge1.target()) { if(edge2.properties().isStrong()) found=true; break; } } if(found) { return true; } } } } } return false; } template void Aggregator::unmarkFront() { typedef typename std::vector::const_iterator Iterator; for(Iterator vertex=front_.begin(); vertex != front_.end(); ++vertex) graph_->getVertexProperties(*vertex).resetFront(); front_.clear(); } template inline void Aggregator::nonisoNeighbourAggregate(const Vertex& vertex, const AggregatesMap& aggregates, SLList& neighbours) const { typedef typename MatrixGraph::ConstEdgeIterator Iterator; Iterator end=graph_->beginEdges(vertex); neighbours.clear(); for(Iterator edge=graph_->beginEdges(vertex); edge!=end; ++edge) { if(aggregates[edge.target()]!=AggregatesMap::UNAGGREGATED && graph_->getVertexProperties(edge.target()).isolated()) neighbours.push_back(aggregates[edge.target()]); } } template inline typename G::VertexDescriptor Aggregator::mergeNeighbour(const Vertex& vertex, const AggregatesMap& aggregates) const { typedef typename MatrixGraph::ConstEdgeIterator Iterator; Iterator end = graph_->endEdges(vertex); for(Iterator edge = graph_->beginEdges(vertex); edge != end; ++edge) { if(aggregates[edge.target()] != AggregatesMap::UNAGGREGATED && graph_->getVertexProperties(edge.target()).isolated() == graph_->getVertexProperties(edge.source()).isolated()) { if( graph_->getVertexProperties(vertex).isolated() || ((edge.properties().depends() || edge.properties().influences()) && admissible(vertex, aggregates[edge.target()], aggregates))) return edge.target(); } } return AggregatesMap::UNAGGREGATED; } template Aggregator::FrontNeighbourCounter::FrontNeighbourCounter(const MatrixGraph& graph) : Counter(), graph_(graph) {} template void Aggregator::FrontNeighbourCounter::operator()(const typename MatrixGraph::ConstEdgeIterator& edge) { if(graph_.getVertexProperties(edge.target()).front()) Counter::increment(); } template int Aggregator::noFrontNeighbours(const Vertex& vertex) const { FrontNeighbourCounter counter(*graph_); visitNeighbours(*graph_, vertex, counter); return counter.value(); } template inline bool Aggregator::connected(const Vertex& vertex, const AggregateDescriptor& aggregate, const AggregatesMap& aggregates) const { typedef typename G::ConstEdgeIterator iterator; const iterator end = graph_->endEdges(vertex); for(iterator edge = graph_->beginEdges(vertex); edge != end; ++edge) if(aggregates[edge.target()]==aggregate) return true; return false; } template inline bool Aggregator::connected(const Vertex& vertex, const SLList& aggregateList, const AggregatesMap& aggregates) const { typedef typename SLList::const_iterator Iter; for(Iter i=aggregateList.begin(); i!=aggregateList.end(); ++i) if(connected(vertex, *i, aggregates)) return true; return false; } template template void Aggregator::growIsolatedAggregate(const Vertex& seed, const AggregatesMap& aggregates, const C& c) { SLList connectedAggregates; nonisoNeighbourAggregate(seed, aggregates,connectedAggregates); while(aggregate_->size()< c.minAggregateSize() && aggregate_->connectSize() < c.maxConnectivity()) { double maxCon=-1; std::size_t maxFrontNeighbours=0; Vertex candidate=AggregatesMap::UNAGGREGATED; typedef typename std::vector::const_iterator Iterator; for(Iterator vertex = front_.begin(); vertex != front_.end(); ++vertex) { if(distance(*vertex, aggregates)>c.maxDistance()) continue; // distance of proposes aggregate too big if(connectedAggregates.size()>0) { // there is already a neighbour cluster // front node must be connected to same neighbour cluster if(!connected(*vertex, connectedAggregates, aggregates)) continue; } double con = connectivity(*vertex, aggregates); if(con == maxCon) { std::size_t frontNeighbours = noFrontNeighbours(*vertex); if(frontNeighbours >= maxFrontNeighbours) { maxFrontNeighbours = frontNeighbours; candidate = *vertex; } }else if(con > maxCon) { maxCon = con; maxFrontNeighbours = noFrontNeighbours(*vertex); candidate = *vertex; } } if(candidate==AggregatesMap::UNAGGREGATED) break; aggregate_->add(candidate); } } template template void Aggregator::growAggregate(const Vertex& seed, const AggregatesMap& aggregates, const C& c) { using std::min; std::size_t distance_ =0; while(aggregate_->size() < c.minAggregateSize()&& distance_ candidates; candidates.reserve(30); typedef typename std::vector::const_iterator Iterator; for(Iterator vertex = front_.begin(); vertex != front_.end(); ++vertex) { // Only nonisolated nodes are considered if(graph_->getVertexProperties(*vertex).isolated()) continue; int twoWayCons = twoWayConnections(*vertex, aggregate_->id(), aggregates); /* The case of two way connections. */ if( maxTwoCons == twoWayCons && twoWayCons > 0) { double con = connectivity(*vertex, aggregates); if(con == maxCon) { int neighbours = noFrontNeighbours(*vertex); if(neighbours > maxNeighbours) { maxNeighbours = neighbours; candidates.clear(); candidates.push_back(*vertex); }else{ candidates.push_back(*vertex); } }else if( con > maxCon) { maxCon = con; maxNeighbours = noFrontNeighbours(*vertex); candidates.clear(); candidates.push_back(*vertex); } }else if(twoWayCons > maxTwoCons) { maxTwoCons = twoWayCons; maxCon = connectivity(*vertex, aggregates); maxNeighbours = noFrontNeighbours(*vertex); candidates.clear(); candidates.push_back(*vertex); // two way connections precede maxOneCons = std::numeric_limits::max(); } if(twoWayCons > 0) { continue; // THis is a two-way node, skip tests for one way nodes } /* The one way case */ int oneWayCons = oneWayConnections(*vertex, aggregate_->id(), aggregates); if(oneWayCons==0) continue; // No strong connections, skip the tests. if(!admissible(*vertex, aggregate_->id(), aggregates)) continue; if( maxOneCons == oneWayCons && oneWayCons > 0) { double con = connectivity(*vertex, aggregates); if(con == maxCon) { int neighbours = noFrontNeighbours(*vertex); if(neighbours > maxNeighbours) { maxNeighbours = neighbours; candidates.clear(); candidates.push_back(*vertex); }else{ if(neighbours==maxNeighbours) { candidates.push_back(*vertex); } } }else if( con > maxCon) { maxCon = con; maxNeighbours = noFrontNeighbours(*vertex); candidates.clear(); candidates.push_back(*vertex); } }else if(oneWayCons > maxOneCons) { maxOneCons = oneWayCons; maxCon = connectivity(*vertex, aggregates); maxNeighbours = noFrontNeighbours(*vertex); candidates.clear(); candidates.push_back(*vertex); } } if(!candidates.size()) break; // No more candidates found distance_=distance(seed, aggregates); candidates.resize(min(candidates.size(), c.maxAggregateSize()- aggregate_->size())); aggregate_->add(candidates); } } template template std::tuple AggregatesMap::buildAggregates(const M& matrix, G& graph, const C& criterion, bool finestLevel) { Aggregator aggregator; return aggregator.build(matrix, graph, *this, criterion, finestLevel); } template template std::tuple Aggregator::build(const M& m, G& graph, AggregatesMap& aggregates, const C& c, bool finestLevel) { using std::max; using std::min; // Stack for fast vertex access Stack stack_(graph, *this, aggregates); graph_ = &graph; aggregate_ = new Aggregate(graph, aggregates, connected_, front_); Timer watch; watch.reset(); buildDependency(graph, m, c, finestLevel); dverb<<"Build dependency took "<< watch.elapsed()<<" seconds."<::ISOLATED; ++skippedAggregates; continue; } if(graph.getVertexProperties(seed).isolated()) { if(c.skipIsolated()) { // isolated vertices are not aggregated but skipped on the coarser levels. aggregates[seed]=AggregatesMap::ISOLATED; ++skippedAggregates; // skip rest as no agglomeration is done. continue; }else{ aggregate_->seed(seed); growIsolatedAggregate(seed, aggregates, c); } }else{ aggregate_->seed(seed); growAggregate(seed, aggregates, c); } /* The rounding step. */ while(!(graph.getVertexProperties(seed).isolated()) && aggregate_->size() < c.maxAggregateSize()) { std::vector candidates; candidates.reserve(30); typedef typename std::vector::const_iterator Iterator; for(Iterator vertex = front_.begin(); vertex != front_.end(); ++vertex) { if(graph.getVertexProperties(*vertex).isolated()) continue; // No isolated nodes here if(twoWayConnections( *vertex, aggregate_->id(), aggregates) == 0 && (oneWayConnections( *vertex, aggregate_->id(), aggregates) == 0 || !admissible( *vertex, aggregate_->id(), aggregates) )) continue; std::pair neighbourPair=neighbours(*vertex, aggregate_->id(), aggregates); //if(aggregateNeighbours(*vertex, aggregate_->id(), aggregates) <= unusedNeighbours(*vertex, aggregates)) // continue; if(neighbourPair.first >= neighbourPair.second) continue; if(distance(*vertex, aggregates) > c.maxDistance()) continue; // Distance too far candidates.push_back(*vertex); break; } if(!candidates.size()) break; // no more candidates found. candidates.resize(min(candidates.size(), c.maxAggregateSize()- aggregate_->size())); aggregate_->add(candidates); } // try to merge aggregates consisting of only one nonisolated vertex with other aggregates if(aggregate_->size()==1 && c.maxAggregateSize()>1) { if(!graph.getVertexProperties(seed).isolated()) { Vertex mergedNeighbour = mergeNeighbour(seed, aggregates); if(mergedNeighbour != AggregatesMap::UNAGGREGATED) { // assign vertex to the neighbouring cluster aggregates[seed] = aggregates[mergedNeighbour]; aggregate_->invalidate(); }else{ ++avg; minA=min(minA,static_cast(1)); maxA=max(maxA,static_cast(1)); ++oneAggregates; ++conAggregates; } }else{ ++avg; minA=min(minA,static_cast(1)); maxA=max(maxA,static_cast(1)); ++oneAggregates; ++isoAggregates; } ++avg; }else{ avg+=aggregate_->size(); minA=min(minA,aggregate_->size()); maxA=max(maxA,aggregate_->size()); if(graph.getVertexProperties(seed).isolated()) ++isoAggregates; else ++conAggregates; } } Dune::dinfo<<"connected aggregates: "<0) Dune::dinfo<<" one node aggregates: "<