Loading [MathJax]/extensions/tex2jax.js
ug4
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
native_cuthill_mckee.h
Go to the documentation of this file.
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
46namespace ug{
47
49
88void ComputeCuthillMcKeeOrder(std::vector<size_t>& vNewIndex,
89 std::vector<std::vector<size_t> >& vvNeighbour,
90 bool bReverse = true,
91 bool bPreserveConsec = true);
92
93
94template <typename TAlgebra, typename O_t>
96{
97public:
98 typedef typename TAlgebra::matrix_type M_t;
99 typedef typename TAlgebra::vector_type V_t;
101
103
107
112
113 void compute(){
114 std::vector<std::vector<size_t> > neighbors;
115 neighbors.resize(m->num_rows());
116
117 for(size_t i=0; i<m->num_rows(); i++)
118 {
119 for(typename M_t::row_iterator i_it = m->begin_row(i); i_it != m->end_row(i); ++i_it){
120 neighbors[i].push_back(i_it.index());
121 }
122 }
123
124 ComputeCuthillMcKeeOrder(o, neighbors, m_bReverse, true);
125
126 m = NULL;
127
128 #ifdef UG_DEBUG
129 check();
130 #endif
131 }
132
133 void check(){
134 UG_COND_THROW(!is_permutation(o), name() << "::check: Not a permutation!");
135 }
136
137 O_t& ordering(){
138 return o;
139 }
140
141 void init(M_t* A, const V_t&){
142 init(A);
143 }
144
145 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 m = A;
152 }
153
154 void init(M_t*, const V_t&, const O_t&){
155 UG_THROW(name() << "::init: induced subgraph version not implemented yet!");
156 }
157
158 void init(M_t*, const O_t&){
159 UG_THROW(name() << "::init: induced subgraph version not implemented yet!");
160 }
161
162 void set_reverse(bool b){
163 m_bReverse = b;
164 }
165
166 virtual const char* name() const {
167 if(m_bReverse){
168 return "ReverseNativeCuthillMcKeeOrdering (ug4 version)";
169 }
170 else{
171 return "NativeCuthillMcKeeOrdering (ug4 version)";
172 }
173 }
174private:
175 O_t o;
177
179};
180
181
182}
183
184#endif
Definition smart_pointer.h:108
Definition IOrderingAlgorithm.h:52
Definition native_cuthill_mckee.h:96
void init(M_t *A, const V_t &)
Definition native_cuthill_mckee.h:141
void check()
Definition native_cuthill_mckee.h:133
virtual const char * name() const
Definition native_cuthill_mckee.h:166
void init(M_t *A)
Definition native_cuthill_mckee.h:145
IOrderingAlgorithm< TAlgebra, O_t > baseclass
Definition native_cuthill_mckee.h:100
M_t * m
Definition native_cuthill_mckee.h:176
void init(M_t *, const O_t &)
Definition native_cuthill_mckee.h:158
void init(M_t *, const V_t &, const O_t &)
Definition native_cuthill_mckee.h:154
void compute()
Definition native_cuthill_mckee.h:113
TAlgebra::vector_type V_t
Definition native_cuthill_mckee.h:99
SmartPtr< IOrderingAlgorithm< TAlgebra, O_t > > clone()
Definition native_cuthill_mckee.h:108
void set_reverse(bool b)
Definition native_cuthill_mckee.h:162
O_t & ordering()
Definition native_cuthill_mckee.h:137
NativeCuthillMcKeeOrdering()
Definition native_cuthill_mckee.h:102
bool m_bReverse
Definition native_cuthill_mckee.h:178
TAlgebra::matrix_type M_t
Definition native_cuthill_mckee.h:98
O_t o
Definition native_cuthill_mckee.h:175
NativeCuthillMcKeeOrdering(const NativeCuthillMcKeeOrdering< TAlgebra, O_t > &parent)
clone constructor
Definition native_cuthill_mckee.h:105
virtual void init()
#define UG_THROW(msg)
Definition error.h:57
#define UG_LOG(msg)
Definition log.h:367
#define UG_COND_THROW(cond, msg)
UG_COND_THROW(cond, msg) : performs a UG_THROW(msg) if cond == true.
Definition error.h:61
the ug namespace
void ComputeCuthillMcKeeOrder(std::vector< size_t > &vNewIndex, std::vector< std::vector< size_t > > &vvConnection, bool bReverse, bool bPreserveConsec)
returns an array describing the needed index mapping for Cuthill-McKee ordering
Definition native_cuthill_mckee.cpp:98
bool is_permutation(O_t &o)
Definition permutation_util.h:135
SmartPtr< T, FreePolicy > make_sp(T *inst)
returns a SmartPtr for the passed raw pointer
Definition smart_pointer.h:836