Loading [MathJax]/extensions/tex2jax.js
ug4
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
new_graph.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2012: G-CSC, Goethe University Frankfurt
3 * Author: Martin Rupp
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
45#ifndef __H__UG__LIB_DISC__AMG_SOLVER__graph_H__
46#define __H__UG__LIB_DISC__AMG_SOLVER__graph_H__
47
48#include <fstream>
49#include <algorithm> // for lower_bound
50#include <vector>
51
52#include "common/assert.h"
53#include "common/log.h"
54
56
57// consecutive memory version
58// first tests with amg (1025x1025 9pt): 1138ms graph creation with old code, 333ms with new => 3x speed improvement
59// old_graph is build with std::vector<std::vector< > >, new_graph uses consecutive memory,
60// drawbacks at the moment:
61// - construction only from 0 to n, so when you set row 3, you may not change item 1
62// amg can work with that, but perhaps we will use some pRowStart/pRowEnd mechanism like in ug::SparseMatrix
63// - fixed amout of connections
64// i will change that, memory will be copied like in std::vector/reserve
65namespace ug{
68class cgraph
69{
70public:
71 typedef const size_t * const_row_iterator;
72 typedef size_t * row_iterator;
73public:
77 {
78#ifdef FORCE_CREATION
80#endif
81 }
82
84 {
85 resize(n);
86 }
87
88 void resize(size_t n)
89 {
90 consmem.resize(10*n, 0);
92 cons.resize(n+1, NULL);
94 }
95
99 {
100 }
101
103 size_t num_connections(size_t node) const
104 {
105 size_check(node);
106 if(cons[node+1] == NULL) return 0;
107 return cons[node+1]-cons[node];
108 }
109
110 bool is_isolated(size_t i) const
111 {
112 size_check(i);
113 if(cons[i+1] == NULL) return false;
114 return num_connections(i)==0 ||
115 (num_connections(i)==1 && cons[i][0] == i);
116 }
117
119 /*bool has_connection(size_t from, size_t to)
120 {
121 size_check(from, to);
122
123 }*/
124
125 void init(size_t i)
126 {
127 int j;
128 for(j=i; j>0; j--)
129 {
130 if(cons[j] != NULL)
131 break;
132 }
133
134 if(j == 0)
135 {
136 cons[0] = &consmem[0];
137 cons[1] = &consmem[0];
138 j = 1;
139 }
140
141 while(j<=i && cons[j+1] == NULL)
142 {
143 cons[j+1] = cons[j];
144 j++;
145 }
146 }
148 void set_connection(size_t from, size_t to)
149 {
150 size_check(from, to);
151
152 UG_ASSERT(from == size()-1 || cons[from+2] == NULL, "only from back to front! ( from is " << from
153 << ", cons[from+2] = " << cons[from+2] << "\n");
154
155 if(cons[from+1]==NULL)
156 init(from);
157 UG_ASSERT(cons[from+1]!=NULL, "??? (from = " << from << ", size = " << size());
158
162 cons[from+1][0] = to;
163 cons[from+1]++;
164 }
165
166
167
169 {
170 size_check(row);
171 if(cons[row+1] == NULL) return NULL;
172 return cons[row];
173 }
174
176 {
177 size_check(row);
178 return cons[row+1];
179 }
180
182 {
183 size_check(row);
184 if(cons[row+1] == NULL) return NULL;
185 return cons[row];
186 }
187
188 const_row_iterator end_row(size_t row) const
189 {
190 size_check(row);
191 return cons[row+1];
192 }
193
205
216
218 {
219 stdvector<size_t> rowSize(other.size());
220 for(size_t i=0; i<other.size(); i++) rowSize[i] = 0;
221
222 for(size_t i=0; i<other.size(); i++)
223 {
224 for(const_row_iterator it = other.begin_row(i); it != other.end_row(i); ++it)
225 rowSize[(*it)]++;
227 rowSize[i] += other.num_connections(i);
228 }
230 size_t *p = &consmem[0];
231 cons.resize(other.size()+1);
232 for(size_t i=0; i<other.size(); i++)
233 {
234 cons[i] = p;
235 p += rowSize[i];
236 rowSize[i] = 0;
237 }
238 cons[other.size()] = p;
239
240 for(size_t i=0; i < other.size(); i++)
241 for(const_row_iterator it = other.begin_row(i); it != other.end_row(i); ++it)
242 {
243 size_t from = (*it);
244 size_t to = i;
245 cons[from][rowSize[from]++] = to;
246 cons[to][rowSize[to]++] = from;
247 UG_ASSERT(cons[from]+rowSize[from] <= cons[from+1], "");
248 }
250 }
251
253 void set_as_transpose_of(const cgraph &other)
254 {
255 stdvector<size_t> rowSize(other.size());
256 for(size_t i=0; i<other.size(); i++) rowSize[i] = 0;
257
258 for(size_t i=0; i<other.size(); i++)
259 {
260 for(const_row_iterator it = other.begin_row(i); it != other.end_row(i); ++it)
261 rowSize[(*it)]++;
263 }
265 size_t *p = &consmem[0];
266 cons.resize(other.size()+1);
267 for(size_t i=0; i<other.size(); i++)
268 {
269 cons[i] = p;
270 p += rowSize[i];
271 rowSize[i] = 0;
272 }
273 cons[other.size()] = p;
274
275 for(size_t i=0; i < other.size(); i++)
276 for(const_row_iterator it = other.begin_row(i); it != other.end_row(i); ++it)
277 {
278 size_t from = (*it);
279 size_t to = i;
280 cons[from][rowSize[from]++] = to;
281 UG_ASSERT(cons[from]+rowSize[from] <= cons[from+1], "");
282 }
284 }
285
286
287 size_t size() const { return cons.size()-1; }
288
289private:
291 {
292 size_t *pOld = &consmem[0];
293 consmem.resize((consmem.size()+1)*2);
294 size_t *pNew = &consmem[0];
295 if(pOld != pNew)
296 {
297 for(size_t i=0; i<consmem; i++)
298 {
299 if(cons[i] == NULL) continue;
300 cons[i] -= pOld;
301 cons[i] += pNew;
302 }
303 }
304 }
305
306 inline void size_check(size_t i) const
307 {
308 UG_ASSERT(i < size(), "graph contains " << size() << " nodes, but trying to access node " << i);
309 }
310 inline void size_check(size_t i, size_t j) const
311 {
312 UG_ASSERT(i < size() && j<size(),
313 "graph contains " << size() << " nodes, but trying to access nodes " << i << " and " << j);
314 }
315public:
316 void print() const
317 {
318 cout << "============= graph ================ " << endl;
319 for(size_t i=0; i < size(); i++)
320 {
321 cout << i << ": ";
322 for(row_iterator it=begin_row(i); it != end_row(i); ++it)
323 cout << (*it) << " ";
324 cout << endl;
325 }
326 }
327
328
329protected:
334};
335
336
337} // namespace ug
338
339#endif // __H__UG__LIB_DISC__AMG_SOLVER__GRAPH_H__
parameterString p
Definition new_graph.h:69
row_iterator begin_row(size_t row)
Definition new_graph.h:168
stdvector< size_t * > cons
Definition new_graph.h:330
row_iterator end_row(size_t row)
Definition new_graph.h:175
void set_as_transpose_of(const cgraph &other)
creates this graph as the transpose of other
Definition new_graph.h:253
size_t size() const
Definition new_graph.h:287
size_t iMaxTotalNrOfConnections
Definition new_graph.h:333
~cgraph()
Definition new_graph.h:98
cgraph()
Definition new_graph.h:76
void print() const
Definition new_graph.h:316
size_t num_connections(size_t node) const
returns nr of nodes the node "node" is connected to.
Definition new_graph.h:103
stdvector< size_t > consmem
Definition new_graph.h:331
const size_t * const_row_iterator
Definition new_graph.h:71
void increase_maxtotalnrofconnections()
Definition new_graph.h:290
void size_check(size_t i) const
Definition new_graph.h:306
size_t * row_iterator
Definition new_graph.h:72
const_row_iterator end_row(size_t row) const
Definition new_graph.h:188
void transpose()
tranpose this graph (by using create_as_tranpose of)
Definition new_graph.h:195
void symmetricize()
Definition new_graph.h:206
void resize(size_t n)
Definition new_graph.h:88
bool is_isolated(size_t i) const
Definition new_graph.h:110
cgraph(size_t n)
Definition new_graph.h:83
void size_check(size_t i, size_t j) const
Definition new_graph.h:310
const_row_iterator begin_row(size_t row) const
Definition new_graph.h:181
void init(size_t i)
returns true if graph has connection from "from" to "to", otherwise false
Definition new_graph.h:125
size_t iTotalNrOfConnections
Definition new_graph.h:332
void create_as_symmetricized(const cgraph &other)
Definition new_graph.h:217
void set_connection(size_t from, size_t to)
set a connection from "from" to "to" if not already there
Definition new_graph.h:148
Definition stl_debug.h:45
#define FORCE_CREATION
Definition algebra_misc.h:46
virtual void init()
#define UG_ASSERT(expr, msg)
Definition assert.h:70
the ug namespace