Line data Source code
1 : /*
2 : * Copyright (c) 2011-2015: G-CSC, Goethe University Frankfurt
3 : * Author: Andreas Vogel
4 : *
5 : * This file is part of UG4.
6 : *
7 : * UG4 is free software: you can redistribute it and/or modify it under the
8 : * terms of the GNU Lesser General Public License version 3 (as published by the
9 : * Free Software Foundation) with the following additional attribution
10 : * requirements (according to LGPL/GPL v3 §7):
11 : *
12 : * (1) The following notice must be displayed in the Appropriate Legal Notices
13 : * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 : *
15 : * (2) The following notice must be displayed at a prominent place in the
16 : * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 : *
18 : * (3) The following bibliography is recommended for citation and must be
19 : * preserved in all covered files:
20 : * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 : * parallel geometric multigrid solver on hierarchically distributed grids.
22 : * Computing and visualization in science 16, 4 (2013), 151-164"
23 : * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 : * flexible software system for simulating pde based models on high performance
25 : * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 : *
27 : * This program is distributed in the hope that it will be useful,
28 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 : * GNU Lesser General Public License for more details.
31 : */
32 :
33 :
34 : #ifndef UG_BASE_LIB_ALGEBRA_ORDERING_STRATEGIES_ALGORITHMS_NATIVE_CUTHILL_MCKEE_H
35 : #define UG_BASE_LIB_ALGEBRA_ORDERING_STRATEGIES_ALGORITHMS_NATIVE_CUTHILL_MCKEE_H
36 :
37 : #include <vector>
38 :
39 : #include "IOrderingAlgorithm.h"
40 : #include "util.h"
41 :
42 : //debug
43 : #include "common/error.h"
44 : #include "common/log.h"
45 :
46 : namespace ug{
47 :
48 : /// returns an array describing the needed index mapping for Cuthill-McKee ordering
49 : /**
50 : * This function computes an index mapping that transforms an index-graph by a
51 : * Cuthill-McKee ordering. For each index, a vector of all adjacent indices
52 : * must be passed.
53 : *
54 : * There are two intended ways of this function to work, depending on the flag bPreserveConsec:
55 : * If set to true (default), the function expects vvNeighbor to contain adjacency information
56 : * sorted by associated geometric object, i.e.:
57 : * Geometric object 0
58 : * DoF 0
59 : * DoF 1
60 : * DoF 2
61 : * ...
62 : * Geometric object 1
63 : * DoF 0
64 : * DoF 1
65 : * DoF 2
66 : * ...
67 : * ...
68 : *
69 : * None of the first indices of any geometric object must be unconnected!
70 : * Only the first DoF index of any geometric object must be given neighbor information!
71 : * This is required to guarantee that DoF indices associated to a geometric object stay consecutive.
72 : *
73 : * If set to false, indices without any adjacency information given in vvNeighbour
74 : * will be sorted to the end. Nothing is preserved. This is applicable if vvNeighbour
75 : * contains the final non-zero entries of a sparse matrix to be re-ordered, e.g., as a
76 : * pre-processing step for ILU(-T) pre-conditioning.
77 : *
78 : *
79 : * On exit, the index field vNewIndex is filled with the index mapping:
80 : * newInd = vNewIndex[oldInd]
81 : *
82 : * \param[out] vNewIndex vector returning new index for old index
83 : * \param[in] vvNeighbour vector of adjacent indices for each index
84 : * \param[in] bReverse flag if "reverse Cuthill-McKee" is used
85 : * \param[in] bPreserveConsec flag indicating whether ordering is done for DofDistribution
86 : * \returns flag if ordering was successful
87 : */
88 : void ComputeCuthillMcKeeOrder(std::vector<size_t>& vNewIndex,
89 : std::vector<std::vector<size_t> >& vvNeighbour,
90 : bool bReverse = true,
91 : bool bPreserveConsec = true);
92 :
93 :
94 : template <typename TAlgebra, typename O_t>
95 : class NativeCuthillMcKeeOrdering : public IOrderingAlgorithm<TAlgebra, O_t>
96 : {
97 : public:
98 : typedef typename TAlgebra::matrix_type M_t;
99 : typedef typename TAlgebra::vector_type V_t;
100 : typedef IOrderingAlgorithm<TAlgebra, O_t> baseclass;
101 :
102 0 : NativeCuthillMcKeeOrdering() : m_bReverse(false) {}
103 :
104 : /// clone constructor
105 0 : NativeCuthillMcKeeOrdering( const NativeCuthillMcKeeOrdering<TAlgebra, O_t> &parent )
106 0 : : baseclass(), m_bReverse(parent.m_bReverse){}
107 :
108 0 : SmartPtr<IOrderingAlgorithm<TAlgebra, O_t> > clone()
109 : {
110 0 : return make_sp(new NativeCuthillMcKeeOrdering<TAlgebra, O_t>(*this));
111 : }
112 :
113 0 : void compute(){
114 : std::vector<std::vector<size_t> > neighbors;
115 0 : neighbors.resize(m->num_rows());
116 :
117 0 : for(size_t i=0; i<m->num_rows(); i++)
118 : {
119 0 : for(typename M_t::row_iterator i_it = m->begin_row(i); i_it != m->end_row(i); ++i_it){
120 0 : neighbors[i].push_back(i_it.index());
121 : }
122 : }
123 :
124 0 : ComputeCuthillMcKeeOrder(o, neighbors, m_bReverse, true);
125 :
126 0 : m = NULL;
127 :
128 : #ifdef UG_DEBUG
129 : check();
130 : #endif
131 0 : }
132 :
133 0 : void check(){
134 0 : UG_COND_THROW(!is_permutation(o), name() << "::check: Not a permutation!");
135 0 : }
136 :
137 0 : O_t& ordering(){
138 0 : return o;
139 : }
140 :
141 0 : void init(M_t* A, const V_t&){
142 0 : init(A);
143 0 : }
144 :
145 0 : void init(M_t* A){
146 : //TODO: replace this by UG_DLOG if permutation_util does not depend on this file anymore
147 : #ifdef UG_ENABLE_DEBUG_LOGS
148 : UG_LOG("Using " << name() << "\n");
149 : #endif
150 :
151 0 : m = A;
152 0 : }
153 :
154 0 : void init(M_t*, const V_t&, const O_t&){
155 0 : UG_THROW(name() << "::init: induced subgraph version not implemented yet!");
156 : }
157 :
158 0 : void init(M_t*, const O_t&){
159 0 : UG_THROW(name() << "::init: induced subgraph version not implemented yet!");
160 : }
161 :
162 0 : void set_reverse(bool b){
163 0 : m_bReverse = b;
164 0 : }
165 :
166 0 : virtual const char* name() const {
167 0 : if(m_bReverse){
168 : return "ReverseNativeCuthillMcKeeOrdering (ug4 version)";
169 : }
170 : else{
171 0 : return "NativeCuthillMcKeeOrdering (ug4 version)";
172 : }
173 : }
174 : private:
175 : O_t o;
176 : M_t* m;
177 :
178 : bool m_bReverse;
179 : };
180 :
181 :
182 : }
183 :
184 : #endif
|
