1 // Gmsh - Copyright (C) 1997-2021 C. Geuzaine, J.-F. Remacle
2 //
3 // See the LICENSE.txt file in the Gmsh root directory for license information.
4 // Please report all issues on https://gitlab.onelab.info/gmsh/gmsh/issues.
5 //
6 // Contributed by Matti Pellikka <matti.pellikka@gmail.com>.
7
8 #include "CellComplex.h"
9 #include "MElement.h"
10 #include "OS.h"
11
12 double CellComplex::_patience = 10;
13
CellComplex(GModel * model,std::vector<MElement * > & domainElements,std::vector<MElement * > & subdomainElements,std::vector<MElement * > & nondomainElements,std::vector<MElement * > & nonsubdomainElements,std::vector<MElement * > & immuneElements,bool saveOriginalComplex)14 CellComplex::CellComplex(GModel *model, std::vector<MElement *> &domainElements,
15 std::vector<MElement *> &subdomainElements,
16 std::vector<MElement *> &nondomainElements,
17 std::vector<MElement *> &nonsubdomainElements,
18 std::vector<MElement *> &immuneElements,
19 bool saveOriginalComplex)
20 : _model(model), _dim(0), _simplicial(true), _saveorig(saveOriginalComplex),
21 _relative(false)
22 {
23 _smallestCell.second = -1.;
24 _biggestCell.second = -1.;
25 _deleteCount = 0;
26 _createCount = 0;
27 _insertCells(subdomainElements, 1);
28 if(getSize(0) > 0) _relative = true;
29 for(int i = 0; i < 4; i++) _numSubdomainCells[i] = getSize(i);
30
31 _insertCells(domainElements, 0);
32 for(int i = 0; i < 4; i++)
33 _numRelativeCells[i] = getSize(i) - _numSubdomainCells[i];
34
35 _removeCells(nonsubdomainElements, 1);
36 _removeCells(nondomainElements, 0);
37 _immunizeCells(immuneElements);
38 int num = 0;
39 for(int dim = 0; dim < 4; dim++) {
40 if(getSize(dim) != 0) _dim = dim;
41 if(_saveorig) _ocells[dim] = _cells[dim];
42 for(auto cit = firstCell(dim); cit != lastCell(dim); cit++) {
43 Cell *cell = *cit;
44 cell->setNum(++num);
45 cell->increaseGlobalNum();
46 cell->saveCellBoundary();
47 }
48 }
49
50 _reduced = false;
51
52 Msg::Debug("Cells in domain:");
53 Msg::Debug(" %d volumes, %d faces, %d edges, and %d vertices",
54 getNumCells(3, 1), getNumCells(2, 1), getNumCells(1, 1),
55 getNumCells(0, 1));
56 Msg::Debug("Cells in subdomain:");
57 Msg::Debug(" %d volumes, %d faces, %d edges, and %d vertices",
58 getNumCells(3, 2), getNumCells(2, 2), getNumCells(1, 2),
59 getNumCells(0, 2));
60 Msg::Debug("Cells in relative domain:");
61 Msg::Debug(" %d volumes, %d faces, %d edges, and %d vertices",
62 getNumCells(3, 0), getNumCells(2, 0), getNumCells(1, 0),
63 getNumCells(0, 0));
64 }
65
_insertCells(std::vector<MElement * > & elements,int domain)66 bool CellComplex::_insertCells(std::vector<MElement *> &elements, int domain)
67 {
68 std::pair<Cell *, double> smallestElement[4];
69 std::pair<Cell *, double> biggestElement[4];
70 for(int i = 0; i < 4; i++) {
71 smallestElement[i].second = -1.;
72 biggestElement[i].second = -1.;
73 }
74 _dim = 0;
75
76 double t1 = Cpu();
77
78 for(std::size_t i = 0; i < elements.size(); i++) {
79 MElement *element = elements.at(i);
80 int dim = element->getDim();
81 int type = element->getType();
82 if(type == TYPE_POLYG || type == TYPE_POLYH) {
83 Msg::Error("Mesh element type %d not implemented in homology solver",
84 type);
85 }
86 if(type == TYPE_QUA || type == TYPE_HEX || type == TYPE_PYR ||
87 type == TYPE_PRI)
88 _simplicial = false;
89 std::pair<Cell *, bool> maybeCell = Cell::createCell(element, domain);
90 if(!maybeCell.second) {
91 delete maybeCell.first;
92 continue;
93 }
94
95 if(_dim < dim) _dim = dim;
96 Cell *cell = maybeCell.first;
97 std::pair<citer, bool> insert = _cells[cell->getDim()].insert(cell);
98 if(!insert.second) {
99 delete cell;
100 cell = *(insert.first);
101 if(domain) cell->setDomain(domain);
102 }
103 else
104 _createCount++;
105
106 if(domain == 0) {
107 double size = fabs(element->getVolume());
108 if(smallestElement[dim].second < 0. || smallestElement[dim].second > size)
109 smallestElement[dim] = std::make_pair(cell, size);
110 if(biggestElement[dim].second < 0. || biggestElement[dim].second < size)
111 biggestElement[dim] = std::make_pair(cell, size);
112 }
113 }
114 _smallestCell = smallestElement[_dim];
115 _biggestCell = biggestElement[_dim];
116
117 for(int dim = 3; dim > 0; dim--) {
118 double t2 = Cpu();
119 if(t2 - t1 > CellComplex::_patience && dim > 1) {
120 if(domain == 0)
121 Msg::Info(" - Creating domain %d-cells", dim);
122 else if(domain == 1)
123 Msg::Info(" - Creating subdomain %d-cells", dim);
124 }
125
126 for(auto cit = firstCell(dim); cit != lastCell(dim); cit++) {
127 Cell *cell = *cit;
128 for(int i = 0; i < cell->getNumBdElements(); i++) {
129 std::pair<Cell *, bool> maybeCell = Cell::createCell(cell, i);
130 if(!maybeCell.second) {
131 delete maybeCell.first;
132 continue;
133 }
134 Cell *newCell = maybeCell.first;
135 std::pair<citer, bool> insert =
136 _cells[newCell->getDim()].insert(newCell);
137 if(!insert.second) {
138 delete newCell;
139 newCell = *(insert.first);
140 if(domain) newCell->setDomain(domain);
141 }
142 else
143 _createCount++;
144 if(domain == 0) {
145 int ori = cell->findBdCellOrientation(newCell, i);
146 cell->addBoundaryCell(ori, newCell, true);
147 if(_smallestCell.first == cell)
148 _smallestCell = std::make_pair(newCell, _smallestCell.second);
149 if(_biggestCell.first == cell)
150 _biggestCell = std::make_pair(newCell, _biggestCell.second);
151 }
152 }
153 }
154 }
155 return true;
156 }
157
_removeCells(std::vector<MElement * > & elements,int domain)158 bool CellComplex::_removeCells(std::vector<MElement *> &elements, int domain)
159 {
160 if(elements.empty()) return true;
161 Msg::Debug("Removing %d elements and their subcells from the cell complex.",
162 (int)elements.size());
163 std::set<Cell *, CellPtrLessThan> removed[4];
164
165 for(std::size_t i = 0; i < elements.size(); i++) {
166 MElement *element = elements.at(i);
167 int type = element->getType();
168 if(type == TYPE_PYR || type == TYPE_PRI || type == TYPE_POLYG ||
169 type == TYPE_POLYH) {
170 Msg::Error("Mesh element type %d not implemented in homology solver",
171 type);
172 return false;
173 }
174 Cell *cell = new Cell(element, domain);
175 int dim = cell->getDim();
176 auto cit = _cells[dim].find(cell);
177 if(cit != lastCell(dim)) {
178 removeCell(*cit);
179 removed[dim].insert(cell);
180 }
181 else
182 delete cell;
183 }
184
185 for(int dim = 3; dim > 0; dim--) {
186 for(auto cit = removed[dim].begin(); cit != removed[dim].end(); cit++) {
187 Cell *cell = *cit;
188 for(int i = 0; i < cell->getNumBdElements(); i++) {
189 Cell *newCell = new Cell(cell, i);
190
191 auto cit2 = _cells[dim - 1].find(newCell);
192 if(cit2 != lastCell(dim - 1)) {
193 removeCell(*cit2);
194 removed[dim - 1].insert(newCell);
195 }
196 else
197 delete newCell;
198 }
199 }
200 }
201 for(int dim = 3; dim >= 0; dim--) {
202 for(auto cit = removed[dim].begin(); cit != removed[dim].end(); cit++) {
203 delete *cit;
204 }
205 }
206 Msg::Debug("Removed %d volumes, %d faces, %d edges, and %d vertices from the "
207 "cell complex",
208 (int)removed[3].size(), (int)removed[2].size(),
209 (int)removed[1].size(), (int)removed[0].size());
210 return true;
211 }
212
_immunizeCells(std::vector<MElement * > & elements)213 bool CellComplex::_immunizeCells(std::vector<MElement *> &elements)
214 {
215 for(std::size_t i = 0; i < elements.size(); i++) {
216 MElement *element = elements.at(i);
217 Cell *cell = new Cell(element, 0);
218 int dim = cell->getDim();
219 auto cit = _cells[dim].find(cell);
220 if(cit != lastCell(dim)) (*cit)->setImmune(true);
221 delete cell;
222 }
223 return true;
224 }
225
~CellComplex()226 CellComplex::~CellComplex()
227 {
228 for(int i = 0; i < 4; i++) {
229 for(auto cit = _cells[i].begin(); cit != _cells[i].end(); cit++) {
230 Cell *cell = *cit;
231 delete cell;
232 _deleteCount++;
233 }
234 }
235
236 for(std::size_t i = 0; i < _removedcells.size(); i++) {
237 delete _removedcells.at(i);
238 _deleteCount++;
239 }
240
241 Msg::Debug("Total number of cells created: %d", _createCount);
242 Msg::Debug("Total number of cells deleted: %d", _deleteCount);
243 }
244
insertCell(Cell * cell)245 void CellComplex::insertCell(Cell *cell)
246 {
247 std::pair<citer, bool> insertInfo = _cells[cell->getDim()].insert(cell);
248 if(!insertInfo.second) {
249 Msg::Debug("Cell not inserted");
250 Cell *oldCell = (*insertInfo.first);
251 cell->printCell();
252 oldCell->printCell();
253 }
254 }
255
removeCell(Cell * cell,bool other,bool del)256 void CellComplex::removeCell(Cell *cell, bool other, bool del)
257 {
258 std::map<Cell *, short int, CellPtrLessThan> coboundary;
259 cell->getCoboundary(coboundary);
260 std::map<Cell *, short int, CellPtrLessThan> boundary;
261 cell->getBoundary(boundary);
262
263 for(auto it = coboundary.begin(); it != coboundary.end(); it++) {
264 Cell *cbdCell = (*it).first;
265 cbdCell->removeBoundaryCell(cell, other);
266 }
267
268 for(auto it = boundary.begin(); it != boundary.end(); it++) {
269 Cell *bdCell = (*it).first;
270 bdCell->removeCoboundaryCell(cell, other);
271 }
272
273 int dim = cell->getDim();
274 int erased = _cells[dim].erase(cell);
275 if(relative()) {
276 if(cell->inSubdomain())
277 _numSubdomainCells[dim] -= 1;
278 else
279 _numRelativeCells[dim] -= 1;
280 }
281 if(!erased)
282 Msg::Debug("Tried to remove a cell from the cell complex \n");
283 else if(!del)
284 _removedcells.push_back(cell);
285 }
286
enqueueCells(std::map<Cell *,short int,CellPtrLessThan> & cells,std::queue<Cell * > & Q,std::set<Cell *,CellPtrLessThan> & Qset)287 void CellComplex::enqueueCells(
288 std::map<Cell *, short int, CellPtrLessThan> &cells, std::queue<Cell *> &Q,
289 std::set<Cell *, CellPtrLessThan> &Qset)
290 {
291 for(auto cit = cells.begin(); cit != cells.end(); cit++) {
292 Cell *cell = (*cit).first;
293 auto it = Qset.find(cell);
294 if(it == Qset.end()) {
295 Qset.insert(cell);
296 Q.push(cell);
297 }
298 }
299 }
300
coreduction(Cell * startCell,int omit,std::vector<Cell * > & omittedCells)301 int CellComplex::coreduction(Cell *startCell, int omit,
302 std::vector<Cell *> &omittedCells)
303 {
304 int coreductions = 0;
305
306 std::queue<Cell *> Q;
307 std::set<Cell *, CellPtrLessThan> Qset;
308
309 Q.push(startCell);
310 Qset.insert(startCell);
311
312 std::map<Cell *, short int, CellPtrLessThan> bd_s;
313 std::map<Cell *, short int, CellPtrLessThan> cbd_c;
314
315 Cell *s;
316 while(!Q.empty()) {
317 s = Q.front();
318 Q.pop();
319 Qset.erase(s);
320 if(s->getBoundarySize() == 1 &&
321 inSameDomain(s, s->firstBoundary()->first) && !s->getImmune() &&
322 !s->firstBoundary()->first->getImmune() &&
323 abs(s->firstBoundary()->second.get()) < 2) {
324 s->getBoundary(bd_s);
325 removeCell(s);
326 bd_s.begin()->first->getCoboundary(cbd_c);
327 enqueueCells(cbd_c, Q, Qset);
328 removeCell(bd_s.begin()->first);
329 if(bd_s.begin()->first->getDim() == omit) {
330 omittedCells.push_back(bd_s.begin()->first);
331 }
332 coreductions++;
333 }
334 else if(s->getBoundarySize() == 0) {
335 s->getCoboundary(cbd_c);
336 enqueueCells(cbd_c, Q, Qset);
337 }
338 }
339 _reduced = true;
340 return coreductions;
341 }
342
reduction(int dim,int omit,std::vector<Cell * > & omittedCells)343 int CellComplex::reduction(int dim, int omit, std::vector<Cell *> &omittedCells)
344 {
345 if(dim < 1 || dim > 3) return 0;
346
347 int numCells[4];
348 for(int i = 0; i < 4; i++) numCells[i] = getSize(i);
349
350 int count = 0;
351
352 bool reduced = true;
353 while(reduced) {
354 reduced = false;
355 auto cit = firstCell(dim - 1);
356 while(cit != lastCell(dim - 1)) {
357 Cell *cell = *cit;
358 if(cell->getCoboundarySize() == 1 &&
359 inSameDomain(cell, cell->firstCoboundary()->first) &&
360 !cell->getImmune() && !cell->firstCoboundary()->first->getImmune() &&
361 !cell->firstCoboundary()->first->getImmune() &&
362 abs(cell->firstCoboundary()->second.get()) < 2) {
363 cit++;
364 if(dim == omit) {
365 omittedCells.push_back(cell->firstCoboundary()->first);
366 }
367 removeCell(cell->firstCoboundary()->first);
368 removeCell(cell);
369 count++;
370 reduced = true;
371 }
372
373 if(getSize(dim) == 0 || getSize(dim - 1) == 0) break;
374 if(cit != lastCell(dim - 1)) cit++;
375 }
376 }
377 _reduced = true;
378 Msg::Debug("Cell complex %d-reduction removed %dv, %df, %de, %dn", dim,
379 numCells[3] - getSize(3), numCells[2] - getSize(2),
380 numCells[1] - getSize(1), numCells[0] - getSize(0));
381 return count;
382 }
383
coreduction(int dim,int omit,std::vector<Cell * > & omittedCells)384 int CellComplex::coreduction(int dim, int omit,
385 std::vector<Cell *> &omittedCells)
386 {
387 if(dim < 1 || dim > 3) return 0;
388
389 int numCells[4];
390 for(int i = 0; i < 4; i++) numCells[i] = getSize(i);
391
392 int count = 0;
393
394 bool reduced = true;
395 while(reduced) {
396 reduced = false;
397 auto cit = firstCell(dim);
398 while(cit != lastCell(dim)) {
399 Cell *cell = *cit;
400 if(cell->getBoundarySize() == 1 &&
401 inSameDomain(cell, cell->firstBoundary()->first) &&
402 !cell->getImmune() && !cell->firstBoundary()->first->getImmune() &&
403 abs(cell->firstBoundary()->second.get()) < 2) {
404 ++cit;
405 if(dim - 1 == omit) {
406 omittedCells.push_back(cell->firstBoundary()->first);
407 }
408 removeCell(cell->firstBoundary()->first);
409 removeCell(cell);
410 count++;
411 reduced = true;
412 }
413
414 if(getSize(dim) == 0 || getSize(dim - 1) == 0) break;
415 if(cit != lastCell(dim)) cit++;
416 }
417 }
418 _reduced = true;
419 Msg::Debug("Cell complex %d-coreduction removed %dv, %df, %de, %dn", dim,
420 numCells[3] - getSize(3), numCells[2] - getSize(2),
421 numCells[1] - getSize(1), numCells[0] - getSize(0));
422 return count;
423 }
424
getSize(int dim,bool orig)425 int CellComplex::getSize(int dim, bool orig)
426 {
427 if(dim == -1) {
428 std::size_t size = 0;
429 if(!orig)
430 for(int i = 0; i < 4; i++) size += _cells[i].size();
431 else
432 for(int i = 0; i < 4; i++) size += _ocells[i].size();
433 return size;
434 }
435 if(!orig)
436 return _cells[dim].size();
437 else
438 return _ocells[dim].size();
439 }
440
getDomain(Cell * cell,std::string & str)441 int CellComplex::getDomain(Cell *cell, std::string &str)
442 {
443 int domain = 0;
444 if(cell->inSubdomain()) {
445 str = "subdomain";
446 domain = 2;
447 }
448 if(!cell->inSubdomain()) {
449 if(relative()) {
450 str = "relative domain";
451 domain = 0;
452 }
453 else {
454 str = "domain";
455 domain = 1;
456 }
457 }
458 return domain;
459 }
460
_omitCell(Cell * cell,bool dual)461 Cell *CellComplex::_omitCell(Cell *cell, bool dual)
462 {
463 Msg::Debug("Omitting %d-cell from the cell complex", cell->getDim());
464 removeCell(cell, false);
465 std::vector<Cell *> omittedCells;
466 omittedCells.push_back(cell);
467 int count = 0;
468
469 int numCells[4];
470 for(int i = 0; i < 4; i++) numCells[i] = getSize(i);
471
472 if(!dual) {
473 for(int j = 3; j > 0; j--)
474 count += reduction(j, cell->getDim(), omittedCells);
475 }
476 else {
477 count += coreduction(cell, cell->getDim(), omittedCells);
478 for(int j = 1; j <= getDim(); j++)
479 count += coreduction(j, cell->getDim(), omittedCells);
480 }
481
482 CombinedCell *newcell = new CombinedCell(omittedCells);
483 _createCount++;
484
485 std::string domainstr = "";
486 int domain = getDomain(cell, domainstr);
487
488 Msg::Debug("Cell complex %d-omit removed %dv, %df, %de, %dn", cell->getDim(),
489 numCells[3] - getSize(3), numCells[2] - getSize(2),
490 numCells[1] - getSize(1), numCells[0] - getSize(0));
491 Msg::Debug(" - number of %d-cells left in %s: %d", cell->getDim(),
492 domainstr.c_str(), getNumCells(cell->getDim(), domain));
493
494 return newcell;
495 }
496
reduceComplex(int combine,bool omit,bool homseq)497 int CellComplex::reduceComplex(int combine, bool omit, bool homseq)
498 {
499 if(!getSize(0)) return 0;
500
501 double t1 = Cpu();
502 int count = 0;
503 if(relative() && !homseq) removeSubdomain();
504 std::vector<Cell *> empty;
505 for(int i = 3; i > 0; i--) count = count + reduction(i, -1, empty);
506
507 if(omit && !homseq) {
508 std::vector<Cell *> newCells;
509
510 while(getSize(getDim()) != 0) {
511 auto cit = firstCell(getDim());
512 Cell *cell = *cit;
513
514 newCells.push_back(_omitCell(cell, false));
515 }
516
517 for(std::size_t i = 0; i < newCells.size(); i++) {
518 insertCell(newCells.at(i));
519 }
520 }
521
522 double t2 = Cpu();
523 if(t2 - t1 > CellComplex::_patience) {
524 Msg::Info(" - %d volumes, %d faces, %d edges, and %d vertices", getSize(3),
525 getSize(2), getSize(1), getSize(0));
526 }
527
528 if(combine > 0) this->combine(3);
529
530 if(combine > 2)
531 for(int i = 3; i > 0; i--) reduction(i, -1, empty);
532 else if(combine > 1)
533 reduction(2, -1, empty);
534
535 if(combine > 0) this->combine(2);
536
537 if(combine > 2)
538 for(int i = 3; i > 0; i--) reduction(i, -1, empty);
539 else if(combine > 1)
540 reduction(1, -1, empty);
541
542 if(combine > 0) this->combine(1);
543
544 if(combine > 2)
545 for(int i = 3; i > 0; i--) reduction(i, -1, empty);
546 else if(combine > 1)
547 reduction(0, -1, empty);
548
549 _reduced = true;
550 return count;
551 }
552
removeSubdomain()553 void CellComplex::removeSubdomain()
554 {
555 std::vector<Cell *> toRemove;
556 for(int i = 0; i < 4; i++) {
557 for(auto cit = firstCell(i); cit != lastCell(i); ++cit) {
558 Cell *cell = *cit;
559 if(cell->inSubdomain()) toRemove.push_back(cell);
560 }
561 }
562 for(std::size_t i = 0; i < toRemove.size(); i++) removeCell(toRemove[i]);
563 _reduced = true;
564 }
565
removeCells(int dim)566 void CellComplex::removeCells(int dim)
567 {
568 if(dim < 0 || dim > 3) return;
569 std::vector<Cell *> toRemove;
570 for(auto cit = firstCell(dim); cit != lastCell(dim); ++cit) {
571 toRemove.push_back(*cit);
572 }
573 for(std::size_t i = 0; i < toRemove.size(); i++) removeCell(toRemove[i]);
574 _reduced = true;
575 }
576
coreduceComplex(int combine,bool omit,int heuristic)577 int CellComplex::coreduceComplex(int combine, bool omit, int heuristic)
578 {
579 if(!getSize(0)) return 0;
580
581 double t1 = Cpu();
582
583 int count = 0;
584 if(relative()) removeSubdomain();
585 std::vector<Cell *> empty;
586 for(int dim = 0; dim < 4; dim++) {
587 auto cit = firstCell(dim);
588 while(cit != lastCell(dim)) {
589 Cell *cell = *cit;
590 int count = +coreduction(cell, -1, empty);
591 if(count != 0) break;
592 cit++;
593 }
594 }
595
596 for(int j = 1; j <= getDim(); j++) count += coreduction(j, -1, empty);
597
598 if(omit) {
599 std::vector<Cell *> newCells;
600 while(getSize(0) != 0) {
601 auto cit = firstCell(0);
602 Cell *cell = *cit;
603
604 if(heuristic == -1 && _smallestCell.second != 0. &&
605 hasCell(_smallestCell.first)) {
606 Msg::Debug("Omitted a cell in the smallest mesh element with volume %g",
607 _smallestCell.second);
608 cell = _smallestCell.first;
609 }
610 else if(heuristic == 1 && _biggestCell.second != 0. &&
611 hasCell(_biggestCell.first)) {
612 Msg::Debug("Omitted a cell in the biggest mesh element with volume %g",
613 _biggestCell.second);
614 cell = _biggestCell.first;
615 }
616
617 newCells.push_back(_omitCell(cell, true));
618 }
619 for(std::size_t i = 0; i < newCells.size(); i++) {
620 insertCell(newCells.at(i));
621 }
622 }
623
624 double t2 = Cpu();
625 if(t2 - t1 > CellComplex::_patience) {
626 Msg::Info(" - %d volumes, %d faces, %d edges, and %d vertices", getSize(3),
627 getSize(2), getSize(1), getSize(0));
628 }
629
630 if(combine > 0) this->cocombine(0);
631
632 if(combine > 2)
633 for(int i = 1; i < 4; i++) coreduction(i, -1, empty);
634 else if(combine > 1)
635 coreduction(1, -1, empty);
636
637 if(combine > 0) this->cocombine(1);
638
639 if(combine > 2)
640 for(int i = 1; i < 4; i++) coreduction(i, -1, empty);
641 else if(combine > 1)
642 coreduction(2, -1, empty);
643
644 if(combine > 0) this->cocombine(2);
645
646 if(combine > 2)
647 for(int i = 1; i < 4; i++) coreduction(i, -1, empty);
648 else if(combine > 1)
649 coreduction(3, -1, empty);
650
651 coherent();
652
653 _reduced = true;
654 return count;
655 }
656
bettiReduceComplex()657 void CellComplex::bettiReduceComplex()
658 {
659 reduceComplex(3, true);
660 for(int i = 1; i <= 3; i++) cocombine(i - 1);
661 return;
662 }
663
combine(int dim)664 int CellComplex::combine(int dim)
665 {
666 if(dim < 1 || dim > 3) return 0;
667
668 int numCells[4];
669 for(int i = 0; i < 4; i++) numCells[i] = getSize(i);
670
671 double t1 = Cpu();
672
673 std::queue<Cell *> Q;
674 std::set<Cell *, CellPtrLessThan> Qset;
675 std::map<Cell *, short int, CellPtrLessThan> bd_c;
676 int count = 0;
677
678 for(auto cit = firstCell(dim); cit != lastCell(dim); cit++) {
679 double t2 = Cpu();
680 if(t2 - t1 > CellComplex::_patience) {
681 t1 = Cpu();
682 Msg::Info(" - %d volumes, %d faces, %d edges, and %d vertices",
683 getSize(3), getSize(2), getSize(1), getSize(0));
684 }
685
686 Cell *cell = *cit;
687 cell->getBoundary(bd_c);
688 enqueueCells(bd_c, Q, Qset);
689
690 while(Q.size() != 0) {
691 Cell *s = Q.front();
692 Q.pop();
693
694 if(s->getCoboundarySize() == 2 && !s->getImmune()) {
695 auto it = s->firstCoboundary();
696 int or1 = it->second.get();
697 Cell *c1 = it->first;
698 it++;
699 while(it->second.get() == 0) it++;
700 int or2 = it->second.get();
701 Cell *c2 = it->first;
702
703 if(!(*c1 == *c2) && abs(or1) == abs(or2) && inSameDomain(s, c1) &&
704 inSameDomain(s, c2) && c1->getImmune() == c2->getImmune()) {
705 removeCell(s, true, false);
706
707 c1->getBoundary(bd_c);
708 enqueueCells(bd_c, Q, Qset);
709 c2->getBoundary(bd_c);
710 enqueueCells(bd_c, Q, Qset);
711
712 CombinedCell *newCell = new CombinedCell(c1, c2, (or1 != or2));
713 _createCount++;
714 removeCell(c1, true, c1->isCombined());
715 removeCell(c2, true, c2->isCombined());
716 insertCell(newCell);
717
718 cit = firstCell(dim);
719 count++;
720
721 if(c1->isCombined()) {
722 delete c1;
723 _deleteCount++;
724 }
725 if(c2->isCombined()) {
726 delete c2;
727 _deleteCount++;
728 }
729 }
730 }
731 Qset.erase(s);
732 }
733 }
734
735 Msg::Debug("Cell complex %d-combine removed %dv, %df, %de, %dn", dim,
736 numCells[3] - getSize(3), numCells[2] - getSize(2),
737 numCells[1] - getSize(1), numCells[0] - getSize(0));
738 _reduced = true;
739 return count;
740 }
741
cocombine(int dim)742 int CellComplex::cocombine(int dim)
743 {
744 if(dim < 0 || dim > 2) return 0;
745
746 int numCells[4];
747 for(int i = 0; i < 4; i++) numCells[i] = getSize(i);
748
749 double t1 = Cpu();
750
751 std::queue<Cell *> Q;
752 std::set<Cell *, CellPtrLessThan> Qset;
753 std::map<Cell *, short int, CellPtrLessThan> cbd_c;
754 int count = 0;
755
756 for(auto cit = firstCell(dim); cit != lastCell(dim); cit++) {
757 double t2 = Cpu();
758 if(t2 - t1 > CellComplex::_patience) {
759 t1 = Cpu();
760 Msg::Info(" - %d volumes, %d faces, %d edges, and %d vertices",
761 getSize(3), getSize(2), getSize(1), getSize(0));
762 }
763
764 Cell *cell = *cit;
765
766 cell->getCoboundary(cbd_c);
767 enqueueCells(cbd_c, Q, Qset);
768
769 while(Q.size() != 0) {
770 Cell *s = Q.front();
771 Q.pop();
772 if(s->getBoundarySize() == 2) {
773 auto it = s->firstBoundary();
774 int or1 = it->second.get();
775 Cell *c1 = it->first;
776 it++;
777 while(it->second.get() == 0) it++;
778 int or2 = it->second.get();
779 Cell *c2 = it->first;
780
781 if(!(*c1 == *c2) && abs(or1) == abs(or2) && inSameDomain(s, c1) &&
782 inSameDomain(s, c2) && c1->getImmune() == c2->getImmune()) {
783 removeCell(s, true, false);
784
785 c1->getCoboundary(cbd_c);
786 enqueueCells(cbd_c, Q, Qset);
787 c2->getCoboundary(cbd_c);
788 enqueueCells(cbd_c, Q, Qset);
789
790 CombinedCell *newCell = new CombinedCell(c1, c2, (or1 != or2), true);
791 _createCount++;
792 removeCell(c1, true, c1->isCombined());
793 removeCell(c2, true, c2->isCombined());
794 insertCell(newCell);
795
796 cit = firstCell(dim);
797 count++;
798
799 if(c1->isCombined()) {
800 delete c1;
801 _deleteCount++;
802 }
803 if(c2->isCombined()) {
804 delete c2;
805 _deleteCount++;
806 }
807 }
808 }
809 Qset.erase(s);
810 }
811 }
812
813 Msg::Debug("Cell complex %d-cocombine removed %dv, %df, %de, %dn", dim,
814 numCells[3] - getSize(3), numCells[2] - getSize(2),
815 numCells[1] - getSize(1), numCells[0] - getSize(0));
816 _reduced = true;
817 return count;
818 }
819
coherent()820 bool CellComplex::coherent()
821 {
822 bool coherent = true;
823 for(int i = 0; i < 4; i++) {
824 for(auto cit = firstCell(i); cit != lastCell(i); cit++) {
825 Cell *cell = *cit;
826 std::map<Cell *, short int, CellPtrLessThan> boundary;
827 cell->getBoundary(boundary);
828 for(auto it = boundary.begin(); it != boundary.end(); it++) {
829 Cell *bdCell = (*it).first;
830 int ori = (*it).second;
831 auto cit = _cells[bdCell->getDim()].find(bdCell);
832 if(cit == lastCell(bdCell->getDim())) {
833 Msg::Debug("Boundary cell not in cell complex! Boundary removed");
834 cell->removeBoundaryCell(bdCell, false);
835 coherent = false;
836 }
837 if(!bdCell->hasCoboundary(cell)) {
838 Msg::Debug("Incoherent boundary/coboundary pair! Fixed");
839 bdCell->addCoboundaryCell(ori, cell, false);
840 coherent = false;
841 }
842 }
843 std::map<Cell *, short int, CellPtrLessThan> coboundary;
844 cell->getCoboundary(coboundary);
845 for(auto it = coboundary.begin(); it != coboundary.end(); it++) {
846 Cell *cbdCell = (*it).first;
847 int ori = (*it).second;
848 auto cit = _cells[cbdCell->getDim()].find(cbdCell);
849 if(cit == lastCell(cbdCell->getDim())) {
850 Msg::Debug("Coboundary cell not in cell complex! Coboundary removed");
851 cell->removeCoboundaryCell(cbdCell, false);
852 coherent = false;
853 }
854 if(!cbdCell->hasBoundary(cell)) {
855 Msg::Debug("Incoherent coboundary/boundary pair! Fixed");
856 cbdCell->addBoundaryCell(ori, cell, false);
857 coherent = false;
858 }
859 }
860 }
861 }
862 return coherent;
863 }
864
hasCell(Cell * cell,bool orig)865 bool CellComplex::hasCell(Cell *cell, bool orig)
866 {
867 citer cit;
868 if(!orig)
869 cit = _cells[cell->getDim()].find(cell);
870 else
871 cit = _ocells[cell->getDim()].find(cell);
872 if(cit == lastCell(cell->getDim(), orig))
873 return false;
874 else
875 return true;
876 }
877
getCells(std::set<Cell *,CellPtrLessThan> & cells,int dim,int domain)878 void CellComplex::getCells(std::set<Cell *, CellPtrLessThan> &cells, int dim,
879 int domain)
880 {
881 cells.clear();
882 for(auto cit = firstCell(dim); cit != lastCell(dim); cit++) {
883 Cell *cell = *cit;
884 if((domain == 0 && !cell->inSubdomain()) || domain == 1 ||
885 (domain == 2 && cell->inSubdomain())) {
886 cells.insert(cell);
887 }
888 }
889 }
890
getNumCells(int dim,int domain)891 int CellComplex::getNumCells(int dim, int domain)
892 {
893 if(domain == 0)
894 return _numRelativeCells[dim];
895 else if(domain == 1)
896 return getSize(dim);
897 else if(domain == 2)
898 return _numSubdomainCells[dim];
899 return 0;
900 }
901
getACell(int dim,int domain)902 Cell *CellComplex::getACell(int dim, int domain)
903 {
904 int num = getNumCells(dim, domain);
905 if(num < 0) Msg::Debug("Domain cell counts not in sync.");
906
907 if(num <= 0) {
908 if(domain == 0)
909 Msg::Warning("%d cells in relative domain", num);
910 else if(domain == 1)
911 Msg::Warning("%d cells in domain", num);
912 else if(domain == 2)
913 Msg::Warning("%d cells in subdomain", num);
914 return nullptr;
915 }
916
917 for(auto cit = firstCell(dim); cit != lastCell(dim); cit++) {
918 Cell *cell = *cit;
919 if((domain == 1) || (domain == 0 && !cell->inSubdomain()) ||
920 (domain == 2 && cell->inSubdomain()))
921 return cell;
922 }
923 Msg::Debug("Domain cell counts not in sync.");
924 return nullptr;
925 }
926
restoreComplex()927 bool CellComplex::restoreComplex()
928 {
929 if(_saveorig) {
930 for(std::size_t i = 0; i < _removedcells.size(); i++) {
931 Cell *cell = _removedcells.at(i);
932 if(cell->isCombined()) {
933 delete cell;
934 _deleteCount++;
935 }
936 }
937 _removedcells.clear();
938
939 for(int i = 0; i < 4; i++) {
940 for(auto cit = _cells[i].begin(); cit != _cells[i].end(); cit++) {
941 Cell *cell = *cit;
942 if(cell->isCombined()) {
943 delete cell;
944 _deleteCount++;
945 }
946 }
947
948 _cells[i] = _ocells[i];
949 for(auto cit = firstCell(i); cit != lastCell(i); cit++) {
950 Cell *cell = *cit;
951 cell->restoreCellBoundary();
952 if(relative()) {
953 if(cell->inSubdomain())
954 _numSubdomainCells[i] += 1;
955 else
956 _numRelativeCells[i] += 1;
957 }
958 }
959 }
960
961 Msg::Info("Restored Cell Complex:");
962 Msg::Info("%d volumes, %d faces, %d edges, and %d vertices", getSize(3),
963 getSize(2), getSize(1), getSize(0));
964 _reduced = false;
965 return true;
966 }
967 else {
968 Msg::Error("Cannot restore cell complex");
969 return false;
970 }
971 }
972
printComplex(int dim)973 void CellComplex::printComplex(int dim)
974 {
975 if(getSize(dim) == 0) Msg::Info("Cell complex dimension %d is empty", dim);
976 for(auto cit = firstCell(dim); cit != lastCell(dim); cit++) {
977 Cell *cell = *cit;
978 cell->printCell();
979 cell->printBoundary();
980 cell->printCoboundary();
981 printf("--- \n");
982 }
983 }
984
saveComplex(const std::string & filename)985 int CellComplex::saveComplex(const std::string &filename)
986 {
987 /*FILE *fp = Fopen (filename.c_str(), "w");
988 if(!fp){
989 printf("\nUnable to open file '%s' \n", filename.c_str());
990 return 0;
991 }
992 printf("\nWriting file '%s'...\n", filename.c_str());
993
994 fprintf(fp, "$Cells\n");
995 fprintf(fp, "%d\n", getSize(0)+getSize(1)+getSize(2)+getSize(3));
996 for(int dim = 0; dim < 4; dim++){
997 for(citer cit = firstCell(dim); cit != lastCell(dim); cit++){
998 Cell* cell = *cit;
999 fprintf(fp, "%d %d %d %d %lu", cell->getNum(), cell->getType(),
1000 1, cell->getDomain(), cell->getNumVertices());
1001 for(std::size_t i = 0; i < cell->getNumVertices(); i++){
1002 fprintf(fp, " %d", cell->getVertex(i));
1003 }
1004 fprintf(fp, " %d", cell->getBoundarySize());
1005 for(Cell::biter bit = cell->firstBoundary();
1006 bit != cell->lastBoundary(); bit++){
1007 fprintf(fp, " %d %d", bit->first->getNum(), bit->second);
1008 }
1009 fprintf(fp, " %d", cell->getCoboundarySize());
1010 for(Cell::biter bit = cell->firstCoboundary();
1011 bit != cell->lastCoboundary(); bit++){
1012 fprintf(fp, " %d %d", bit->first->getNum(), bit->second);
1013 }
1014 fprintf(fp, "\n");
1015 }
1016 }
1017
1018 fclose(fp);
1019
1020 printf("Wrote %d cells to '%s' \n",
1021 getSize(0)+getSize(1)+getSize(2)+getSize(3), filename.c_str());
1022 */
1023 return 1;
1024 }
1025
loadComplex(const std::string & filename)1026 int CellComplex::loadComplex(const std::string &filename)
1027 {
1028 /* FILE *fp = Fopen (filename.c_str(), "r");
1029 if(!fp){
1030 printf("\nUnable to open file '%s' \n", filename.c_str());
1031 return 0;
1032 }
1033
1034 std::map<int, Cell*> numToCell;
1035
1036 char str[256] = "XXX";
1037 while(1) {
1038
1039 while(str[0] != '$'){
1040 if(!fgets(str, sizeof(str), fp) || feof(fp))
1041 break;
1042 }
1043
1044 if(feof(fp))
1045 break;
1046
1047 if(!strncmp(&str[1], "Cells", 5)) {
1048 if(!fgets(str, sizeof(str), fp)) return 0;
1049 int numCells;
1050 sscanf(str, "%d", &numCells);
1051 for(int i = 0; i < numCells; i++) {
1052 int num, type, numTags;
1053 std::vector<int> domain;
1054 int tag;
1055 if(fscanf(fp, "%d %d %d", &num, &type, &numTags) != 3) return 0;
1056 for(int j = 0; j < numTags; j++){
1057 if(fscanf(fp, "%d", &tag) != 1) return 0;
1058 domain.push_back(tag);
1059 }
1060
1061 std::vector<int> vertices;
1062 if(fscanf(fp, "%d", &numTags) != 1) return 0;
1063 for(int j = 0; j < numTags; j++){
1064 if(fscanf(fp, "%d", &tag) != 1) return 0;
1065 vertices.push_back(tag);
1066 }
1067
1068 int dim = 0;
1069 if(type == 1){
1070 if(vertices.size() == 2) dim = 1;
1071 else if(vertices.size() == 3) dim = 2;
1072 else if(vertices.size() == 4) dim = 3;
1073 }
1074
1075 Cell* cell = new Cell(num, dim, type, domain, vertices);
1076 numToCell[num] = cell;
1077
1078
1079 int numCell;
1080 if(fscanf(fp, "%d", &numTags) != 1) return 0;
1081 for(int j = 0; j < numTags; j++){
1082 if(fscanf(fp, "%d %d", &numCell, &tag) != 1) return 0;
1083 }
1084 if(fscanf(fp, "%d", &numTags) != 1) return 0;
1085 for(int j = 0; j < numTags; j++){
1086 if(fscanf(fp, "%d %d", &numCell, &tag) != 1) return 0;
1087 }
1088
1089 }
1090 }
1091
1092 }
1093
1094 fclose(fp);
1095 */
1096 return 1;
1097 }
1098