Debian Codegraph @

dune/istl/paamg/test/graphtest.cc

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5 // start with including some headers
6 #include <iostream> // for input/output to shell
7
8 #include <dune/istl/paamg/graph.hh>
9 #include <dune/istl/paamg/dependency.hh>
10 #include <dune/istl/paamg/aggregates.hh>
11 #include <dune/istl/istlexception.hh>
12 #include <dune/istl/bcrsmatrix.hh>
13 #include <dune/common/fmatrix.hh>
14 #include <dune/common/typetraits.hh>
15 #include <dune/istl/io.hh>
16
17 int testEdgeDepends(const Dune::Amg::EdgeProperties& flags)
18 {
19 int ret=0;
20
21 if(!flags.depends()) {
22 std::cerr << "Depends does not return true after setDepends! "<<__FILE__
23 <<":"<<__LINE__<<std::endl;
24 ret++;
25 }
26
27 if(flags.influences()) {
28 std::cerr << "Influences should not return true after setDepends! "<<__FILE__
29 <<":"<<__LINE__<<std::endl;
30 ret++;
31 }
32
33 if(!flags.isStrong()) {
34 std::cerr <<"Should be strong after setDepends! "<<__FILE__
35 <<":"<<__LINE__<<std::endl;
36 ret++;
37 }
38
39 if(!flags.isOneWay()) {
40 std::cerr <<"Should be oneWay after setDepends! "<<__FILE__
41 <<":"<<__LINE__<<std::endl;
42 ret++;
43 }
44
45 if(flags.isTwoWay()) {
46 std::cerr <<"Should not be twoWay after setDepends! "<<__FILE__
47 <<":"<<__LINE__<<std::endl;
48 ret++;
49 }
50 return ret;
51 }
52
53 int testEdgeInfluences(const Dune::Amg::EdgeProperties& flags)
54 {
55 int ret=0;
56
57 if(!flags.influences()) {
58 std::cerr << "Influences does not return true after setInfluences! "<<__FILE__
59 <<":"<<__LINE__<<std::endl;
60 ret++;
61 }
62
63 if(!flags.isStrong()) {
64 std::cerr <<"Should be strong after setDepends and setInfluences! "<<__FILE__
65 <<":"<<__LINE__<<std::endl;
66 ret++;
67 }
68
69 if(flags.isOneWay()) {
70 std::cerr <<"Should not be oneWay after setDepends and setInfluences! "<<__FILE__
71 <<":"<<__LINE__<<std::endl;
72 ret++;
73 }
74
75 if(flags.isTwoWay()) {
76 std::cerr <<"Should not be twoWay after setInfluences! "<<__FILE__
77 <<":"<<__LINE__<<std::endl;
78 ret++;
79 }
80 return ret;
81
82 }
83
84 int testEdgeTwoWay(const Dune::Amg::EdgeProperties& flags)
85 {
86 int ret=0;
87
88 if(!flags.depends()) {
89 std::cerr << "Depends does not return true after setDepends! "<<__FILE__
90 <<":"<<__LINE__<<std::endl;
91 ret++;
92 }
93
94 if(!flags.influences()) {
95 std::cerr << "Influences does not return true after setDepends! "<<__FILE__
96 <<":"<<__LINE__<<std::endl;
97 ret++;
98 }
99
100 if(!flags.isStrong()) {
101 std::cerr <<"Should be strong after setDepends and setInfluences! "<<__FILE__
102 <<":"<<__LINE__<<std::endl;
103 ret++;
104 }
105
106 if(flags.isOneWay()) {
107 std::cerr <<"Should not be oneWay after setDepends and setInfluences! "<<__FILE__
108 <<":"<<__LINE__<<std::endl;
109 ret++;
110 }
111
112
113 if(!flags.isTwoWay()) {
114 std::cerr <<"Should be twoWay after setDepends and setInfluences! "<<__FILE__
115 <<":"<<__LINE__<<std::endl;
116 ret++;
117 }
118 return ret;
119
120 }
121
122 int testEdgeReset(const Dune::Amg::EdgeProperties& flags)
123 {
124 int ret=0;
125 if(flags.depends()) {
126 std::cerr << "Depend bit should be cleared after initialization or reset! "<<__FILE__
127 <<":"<<__LINE__<<std::endl;
128 ret++;
129 }
130
131 if(flags.influences()) {
132 std::cerr << "Influence bit should be cleared after initialization or reset! "<<__FILE__
133 <<":"<<__LINE__<<std::endl;
134 ret++;
135 }
136
137
138 if(flags.isTwoWay()) {
139 std::cerr << "Should not be twoWay after initialization or reset! "<<__FILE__
140 <<":"<<__LINE__<<std::endl;
141 ret++;
142 }
143
144 if(flags.isOneWay()) {
145 std::cerr << "Should not be oneWay after initialization or reset! "<<__FILE__
146 <<":"<<__LINE__<<std::endl;
147 ret++;
148 }
149
150 if(flags.isStrong()) {
151 std::cerr << "Should not be strong after initialization reset! "<<__FILE__
152 <<":"<<__LINE__<<std::endl;
153 ret++;
154 }
155
156 if(ret>0)
157 std::cerr<<"Flags: "<<flags;
158
159 return ret;
160
161 }
162
163 int testVertexReset(Dune::Amg::VertexProperties& flags)
164 {
165 int ret=0;
166
167 if(flags.front()) {
168 std::cerr<<"Front flag should not be set if reset!"<<__FILE__ ":"<<__LINE__
169 <<std::endl;
170 ret++;
171 }
172
173 if(flags.visited()) {
174 std::cerr<<"Visited flag should not be set if reset!"<<__FILE__ ":"<<__LINE__
175 <<std::endl;
176 ret++;
177 }
178
179 if(flags.isolated()) {
180 std::cerr<<"Isolated flag should not be set if reset!"<<__FILE__ ":"<<__LINE__
181 <<std::endl;
182 ret++;
183 }
184
185 return ret;
186
187 }
188
189 int testVertex()
190 {
191 int ret=0;
192
193 Dune::Amg::VertexProperties flags;
194
195 ret+=testVertexReset(flags);
196
197 flags.setIsolated();
198
199 if(!flags.isolated()) {
200 std::cerr<<"Isolated flag should be set after setIsolated!"<<__FILE__ ":"<<__LINE__
201 <<std::endl;
202 ret++;
203 }
204
205 flags.resetIsolated();
206 ret+=testVertexReset(flags);
207
208 flags.setFront();
209
210 if(!flags.front()) {
211 std::cerr<<"Front flag should be set after setFront!"<<__FILE__ ":"<<__LINE__
212 <<std::endl;
213 ret++;
214 }
215
216 flags.resetFront();
217 ret+=testVertexReset(flags);
218
219 flags.setVisited();
220
221 if(!flags.visited()) {
222 std::cerr<<"Visited flag should be set after setVisited!"<<__FILE__ ":"<<__LINE__
223 <<std::endl;
224 ret++;
225 }
226
227 flags.resetVisited();
228
229 ret+=testVertexReset(flags);
230 /*
231 flags.setExcluded();
232
233 if(!flags.excluded()){
234 std::cerr<<"Excluded flag should be set after setExcluded!"<<__FILE__":"<<__LINE__
235 <<std::endl;
236 ret++;
237 }
238
239 flags.resetExcluded();
240 */
241 ret+=testVertexReset(flags);
242
243 return ret;
244
245 }
246
247 int testEdge()
248 {
249 int ret=0;
250
251 Dune::Amg::EdgeProperties flags;
252
253 ret += testEdgeReset(flags);
254
255 flags.setDepends();
256
257 ret += testEdgeDepends(flags);
258
259 flags.resetDepends();
260
261 flags.setInfluences();
262
263 ret += testEdgeInfluences(flags);
264
265 flags.resetInfluences();
266
267 ret += testEdgeReset(flags);
268
269 flags.setInfluences();
270 flags.setDepends();
271
272 testEdgeTwoWay(flags);
273
274 flags.resetDepends();
275 flags.resetInfluences();
276
277 flags.setDepends();
278 flags.setInfluences();
279
280
281 flags.resetDepends();
282 flags.resetInfluences();
283
284 ret += testEdgeReset(flags);
285
286 return ret;
287
288 }
289
290 template<int N, class M>
291 void setupSparsityPattern(M& A)
292 {
293 for (typename M::CreateIterator i = A.createbegin(); i != A.createend(); ++i) {
294 int x = i.index()%N; // x coordinate in the 2d field
295 int y = i.index()/N; // y coordinate in the 2d field
296
297 if(y>0)
298 // insert lower neighbour
299 i.insert(i.index()-N);
300 if(x>0)
301 // insert left neighbour
302 i.insert(i.index()-1);
303
304 // insert diagonal value
305 i.insert(i.index());
306
307 if(x<N-1)
308 //insert right neighbour
309 i.insert(i.index()+1);
310 if(y<N-1)
311 // insert upper neighbour
312 i.insert(i.index()+N);
313 }
314 }
315
316 template<int N, class M>
317 void setupAnisotropic(M& A, double eps)
318 {
319 typename M::block_type diagonal = 0, bone=0, beps=0;
320 for(typename M::block_type::RowIterator b = diagonal.begin(); b != diagonal.end(); ++b)
321 b->operator[](b.index())=2.0+2.0*eps;
322
323
324 for(typename M::block_type::RowIterator b=bone.begin(); b != bone.end(); ++b)
325 b->operator[](b.index())=-1.0;
326
327 for(typename M::block_type::RowIterator b=beps.begin(); b != beps.end(); ++b)
328 b->operator[](b.index())=-eps;
329
330 for (typename M::RowIterator i = A.begin(); i != A.end(); ++i) {
331 int x = i.index()%N; // x coordinate in the 2d field
332 int y = i.index()/N; // y coordinate in the 2d field
333
334 i->operator[](i.index())=diagonal;
335
336 if(y>0)
337 i->operator[](i.index()-N)=beps;
338
339 if(y<N-1)
340 i->operator[](i.index()+N)=beps;
341
342 if(x>0)
343 i->operator[](i.index()-1)=bone;
344
345 if(x < N-1)
346 i->operator[](i.index()+1)=bone;
347 }
348 }
349
350 template<class N, class G>
351 void printWeightedGraph(G& graph, std::ostream& os, const N& norm=N())
352 {
353 typedef typename std::remove_const<G>::type Mutable;
354 typedef typename std::conditional<std::is_same<G,Mutable>::value,
355 typename G::VertexIterator,
356 typename G::ConstVertexIterator>::type VertexIterator;
357
358 typedef typename std::conditional<std::is_same<G,Mutable>::value,
359 typename G::EdgeIterator,
360 typename G::ConstEdgeIterator>::type EdgeIterator;
361 for(VertexIterator vertex = graph.begin(); vertex!=graph.end(); ++vertex) {
362 const EdgeIterator endEdge = vertex.end();
363 os<<"Edges starting from Vertex "<<*vertex<<" (weight="<<norm(vertex.weight());
364 os<<") to vertices ";
365
366 for(EdgeIterator edge = vertex.begin(); edge != endEdge; ++edge)
367 os<<edge.target()<<" (weight="<<edge.weight()<<"), ";
368 os<<std::endl;
369 }
370 }
371
372 template<class G>
373 void printPropertiesGraph(G& graph, std::ostream& os)
374 {
375 typedef typename std::remove_const<G>::type Mutable;
376 typedef typename std::conditional<std::is_same<G,Mutable>::value,
377 typename G::VertexIterator,
378 typename G::ConstVertexIterator>::type VertexIterator;
379
380 typedef typename std::conditional<std::is_same<G,Mutable>::value,
381 typename G::EdgeIterator,
382 typename G::ConstEdgeIterator>::type EdgeIterator;
383 for(VertexIterator vertex = graph.begin(); vertex!=graph.end(); ++vertex) {
384 const EdgeIterator endEdge = vertex.end();
385 os<<"Edges starting from Vertex "<<*vertex<<" to vertices (";
386 os<<vertex.properties()<<") ";
387
388 for(EdgeIterator edge = vertex.begin(); edge != endEdge; ++edge)
389 os<<edge.target()<<" ("<<edge.properties()<<"), ";
390 os<<std::endl;
391 }
392 }
393
394 template<class G>
395 void printGraph(G& graph, std::ostream& os)
396 {
397 typedef typename std::remove_const<G>::type Mutable;
398 typedef typename std::conditional<std::is_same<G,Mutable>::value,
399 typename G::VertexIterator,
400 typename G::ConstVertexIterator>::type VertexIterator;
401
402 typedef typename std::conditional<std::is_same<G,Mutable>::value,
403 typename G::EdgeIterator,
404 typename G::ConstEdgeIterator>::type EdgeIterator;
405 for(VertexIterator vertex = graph.begin(); vertex!=graph.end(); ++vertex) {
406 const EdgeIterator endEdge = vertex.end();
407 os<<"Edges starting from Vertex "<<*vertex<<" to vertices ";
408
409 for(EdgeIterator edge = vertex.begin(); edge != endEdge; ++edge)
410 os<<edge.target()<<", ";
411 os<<std::endl;
412 }
413 }
414
415
416 void testGraph ()
417 {
418 const int N=8;
419
420 typedef Dune::FieldMatrix<double,1,1> ScalarDouble;
421 typedef Dune::BCRSMatrix<ScalarDouble> BCRSMat;
422
423 double diagonal=4, offdiagonal=-1;
424
425 BCRSMat laplacian2d(N*N,N*N,N*N*5,BCRSMat::row_wise);
426
427 setupSparsityPattern<N>(laplacian2d);
428
429 laplacian2d = offdiagonal;
430
431 // Set the diagonal values
432 for (BCRSMat::RowIterator i=laplacian2d.begin(); i!=laplacian2d.end(); ++i)
433 i->operator[](i.index())=diagonal;
434
435 //Dune::printmatrix(std::cout,laplacian2d,"2d Laplacian","row",9,1);
436
437 typedef Dune::Amg::MatrixGraph<BCRSMat> MatrixGraph;
438
439 MatrixGraph mg(laplacian2d);
440
441 using Dune::Amg::FirstDiagonal;
442 printWeightedGraph(mg,std::cout,FirstDiagonal());
443 printWeightedGraph(static_cast<const MatrixGraph&>(mg),
444 std::cout,FirstDiagonal());
445
446 std::vector<bool> excluded(N*N, false);
447
448 for(int i=0; i < N; i++) {
449 excluded[i]=excluded[(N-1)*N+i]=true;
450 excluded[i*N]=excluded[i*N+N-1]=true;
451 }
452
453
454 typedef Dune::Amg::SubGraph<Dune::Amg::MatrixGraph<BCRSMat>,std::vector<bool> > SubGraph;
455 SubGraph sub(mg, excluded);
456
457 for(std::vector<bool>::iterator iter=excluded.begin(); iter != excluded.end(); ++iter)
458 std::cout<<*iter<<" ";
459
460 std::cout<<std::endl<<"SubGraph:"<<std::endl;
461
462 printGraph(sub, std::cout);
463
464 typedef Dune::Amg::PropertiesGraph<MatrixGraph,
465 Dune::Amg::VertexProperties,
466 Dune::Amg::EdgeProperties> PropertiesGraph;
467
468 std::cout<<std::endl<<"PropertiesGraph: ";
469 PropertiesGraph pgraph(mg);
470
471 std::cout<<" noVertices="<<pgraph.noVertices()<<std::endl; //" noEdges=";
472 //std::cout<<pgraph.noEdges()<<std:endl
473
474 printPropertiesGraph(pgraph, std::cout);
475 //printPropertiesGraph(static_cast<const PropertiesGraph&>(pgraph), std::cout);
476
477 using Dune::Amg::SymmetricDependency;
478 using Dune::Amg::SymmetricCriterion;
479
480 //SymmetricCriterion<BCRSGraph, FirstDiagonal> crit;
481 SymmetricCriterion<BCRSMat,FirstDiagonal> crit;
482
483 Dune::Amg::AggregatesMap<PropertiesGraph::VertexDescriptor> aggregatesMap(pgraph.maxVertex()+1);
484 aggregatesMap.buildAggregates(laplacian2d, pgraph, crit, false);
485 Dune::Amg::printAggregates2d(aggregatesMap, N, N, std::cout);
486
487 }
488
489
490 void testAggregate()
491 {
492
493 typedef Dune::FieldMatrix<double,1,1> ScalarDouble;
494 typedef Dune::BCRSMatrix<ScalarDouble> BCRSMat;
495 const int N=20;
496
497 BCRSMat mat(N*N,N*N,N*N*5,BCRSMat::row_wise);
498
499 setupSparsityPattern<N>(mat);
500 setupAnisotropic<N>(mat, .001);
501
502 typedef Dune::Amg::MatrixGraph<BCRSMat> BCRSGraph;
503 typedef Dune::Amg::SubGraph<BCRSGraph,std::vector<bool> > SubGraph;
504 typedef Dune::Amg::PropertiesGraph<BCRSGraph,Dune::Amg::VertexProperties,Dune::Amg::EdgeProperties> PropertiesGraph;
505 typedef Dune::Amg::PropertiesGraph<SubGraph,Dune::Amg::VertexProperties,Dune::Amg::EdgeProperties,Dune::IdentityMap,SubGraph::EdgeIndexMap> SPropertiesGraph;
506
507 BCRSGraph graph(mat);
508 PropertiesGraph pgraph(graph);
509
510 std::vector<bool> excluded(N*N, false);
511
512 for(int i=0; i < N; i++) {
513 excluded[i]=excluded[(N-1)*N+i]=true;
514 excluded[i*N]=excluded[i*N+N-1]=true;
515 }
516
517 SubGraph sgraph(graph, excluded);
518 SPropertiesGraph spgraph(sgraph, Dune::IdentityMap(), sgraph.getEdgeIndexMap());
519
520
521 using Dune::Amg::FirstDiagonal;
522 using Dune::Amg::SymmetricDependency;
523 using Dune::Amg::SymmetricCriterion;
524
525 //SymmetricCriterion<BCRSGraph, FirstDiagonal<typename BCRSMat::block_type> > crit;
526 SymmetricCriterion<BCRSMat, FirstDiagonal> crit;
527
528
529 Dune::Amg::AggregatesMap<PropertiesGraph::VertexDescriptor> aggregatesMap(pgraph.maxVertex()+1);
530
531 aggregatesMap.buildAggregates(mat, pgraph, crit, false);
532
533 Dune::Amg::printAggregates2d(aggregatesMap, N, N, std::cout);
534
535 std::cout<<"Excluded!"<<std::endl;
536
537 Dune::Amg::AggregatesMap<SPropertiesGraph::VertexDescriptor> saggregatesMap(pgraph.maxVertex()+1);
538 saggregatesMap.buildAggregates(mat, spgraph, crit, false);
539 Dune::Amg::printAggregates2d(saggregatesMap, N, N, std::cout);
540
541
542
543 }
544
545 int main (int argc , char ** argv)
546 {
547 try {
548 testGraph();
549 testAggregate();
550 exit(testEdge());
551 }
552 catch(std::exception& e)
553 {
554 std::cout << "ERROR: " << e.what() << std::endl;
555 return 1;
556 }
557 catch (...)
558 {
559 std::cerr << "unknown exception caught" << std::endl;
560 exit(1);
561 }
562
563 return 0;
564 }