CoCalc -- movable_complex.cpp

GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
gap4r8 / pkg / simpcomp / src / movable_complex.cpp
^1035287 views
1
//
2
//  movable_complex.cpp
3
//  Bistellar
4
//
5
//  Created by Alexander Thumm on 07.10.11.
6
//  Copyright 2011 -. All rights reserved.
7
//
8

9
#include "movable_complex.h"
10
#include "face.h"
11
#include "util.h"
12
#include <algorithm>
13
#include <iostream>
14

15
MovableComplex::MovableComplex() : _faces(1, face_list_t(0)), _moves(1, bistellar_move_option_list_t(0)), _dimension(0)
16
{
17
}
18

19
MovableComplex::MovableComplex(const face_list_t & facets, unsigned int dimension) : _faces(dimension+1), _moves(dimension+1), _dimension(dimension)
20
{
21
    
22
    #ifdef Bistellar_debug_output
23
    std::cout << "Creating "<< dimension <<"-dimensional MovableComplex from Facets: ";
24
    list_print(std::cout, facets.begin(), facets.end());
25
    std::cout << std::endl;
26
    #endif
27
    
28
    // init facets
29
    _faces[dimension] = facets;
30
    
31
    // init lower dimensional faces
32
    for (int codimension = 1; codimension < dimension+1; codimension++)
33
    {
34
        if(!_faces[dimension - codimension + 1].empty())
35
        {
36
            for (face_list_t::const_iterator it = _faces[dimension - codimension + 1].begin();
37
             it != _faces[dimension - codimension + 1].end(); it++)
38
            {
39
                for (int i = 0; i < dimension - codimension + 2; i++)
40
                {
41
                    Face * boundaryFace = it->createBoundaryFace(i);
42
                    // only add boundaryFace if it is not already contained in complex
43
                    if (std::find(_faces[dimension - codimension].begin(), _faces[dimension - codimension].end(), *boundaryFace) == _faces[dimension - codimension].end())
44
                    {
45
                        _faces[dimension - codimension].push_back(*boundaryFace);
46
                    }
47
                    
48
                    delete boundaryFace;
49
                }
50
            }
51
        }
52
    }
53
    
54
    // init moves
55
    if (!_faces[dimension].empty())
56
    {
57
        for (face_list_t::const_iterator it = _faces[dimension].begin(); it != _faces[dimension].end(); it++)
58
        {
59
            // add all 0-moves
60
            _moves[0].push_back(std::make_pair(BistellarMove(*it, Face()), true));
61
        }
62
    }
63
    for (int codimension = 1; codimension < dimension+1; codimension++)
64
    {
65
        if (!_faces[dimension-codimension].empty())
66
        {
67
            for (face_list_t::const_iterator it = _faces[dimension-codimension].begin(); it != _faces[dimension-codimension].end(); it++)
68
            {
69
                std::deque< Face > linkFacets;
70
                // copy all Facets that contain (*it) as a subface to linkFacets
71
                if (!_faces[dimension].empty())
72
                {
73
                    for (face_list_t::const_iterator it2 = _faces[dimension].begin(); it2 != _faces[dimension].end(); it2++)
74
                    {
75
                        if (it->isSubfaceOf(*it2))
76
                            linkFacets.push_back(*it2);
77
                    }
78
                }
79
                
80
                if (linkFacets.size() == codimension+1)
81
                {
82
                    // add the move option.
83
                    Face linkFace = Face::linkFace(*it, linkFacets);
84
                    if (linkFace.dimension() <= _dimension)
85
                        _moves[codimension].push_back(std::make_pair(BistellarMove(*it, linkFace), (std::find(_faces[linkFace.dimension()].begin(), _faces[linkFace.dimension()].end(), linkFace) == _faces[linkFace.dimension()].end())));
86
                }
87
            }
88
        }
89
    }
90
    
91
    #ifdef Bistellar_debug_output
92
    for (int i = 0; i < dimension+1; i++)
93
    {
94
        std::cout << i << "-Moves: ";
95
        if (!_moves[i].empty()) list_print(std::cout, _moves[i].begin(), _moves[i].end());
96
        std::cout << std::endl;
97
    }
98
    #endif
99
}
100

101
MovableComplex::MovableComplex(const MovableComplex & cpy)
102
{
103
    _dimension = cpy._dimension;
104
    _faces = cpy._faces;
105
    _moves = cpy._moves;
106
}
107

108
MovableComplex & MovableComplex::operator=(const MovableComplex & cpy)
109
{
110
    if (this == &cpy)
111
        return *this;
112
    
113
    _dimension = cpy._dimension;
114
    _faces = cpy._faces;
115
    _moves = cpy._moves;
116
    
117
    return *this;
118
}
119

120
MovableComplex::~MovableComplex()
121
{
122
}
123

124
unsigned int MovableComplex::dimension() const
125
{
126
    return _dimension;
127
}
128

129
unsigned int MovableComplex::f(unsigned int d) const
130
{
131
    if (d <= _dimension)
132
        return static_cast<unsigned int>(_faces[d].size());
133
    
134
    return 0;
135
}
136

137
bool MovableComplex::hasValidMoves(unsigned int codimension) const
138
{
139
    if (!_moves[codimension].empty())
140
    {
141
        for (bistellar_move_option_list_t::const_iterator it = _moves[codimension].begin(); it != _moves[codimension].end(); it++)
142
        {
143
            if(it->second)
144
                return true;
145
        }
146
    }
147

148
    return false;
149
}
150

151
bistellar_move_list_t MovableComplex::validMoves(unsigned int codimension) const
152
{
153
    bistellar_move_list_t validMoves;
154
    if (!_moves[codimension].empty())
155
    {
156
        for (bistellar_move_option_list_t::const_iterator it = _moves[codimension].begin(); it != _moves[codimension].end(); it++)
157
        {
158
            if(it->second)
159
                validMoves.push_back(it->first);
160
        }
161
    }
162
    return validMoves;
163
}
164

165
void MovableComplex::moveComplex(const BistellarMove & move)
166
{
167
    face_list_t::iterator faceIt = std::find(_faces[move.dimension()].begin(), _faces[move.dimension()].end(), move.face());
168
    bistellar_move_option_list_t::iterator moveIt = std::find(_moves[move.codimension()].begin(), _moves[move.codimension()].end(), std::make_pair(move, true));
169
    
170
    if (faceIt != _faces[move.dimension()].end() && moveIt != _moves[move.codimension()].end() && moveIt->second)
171
    {
172
        #ifdef Bistellar_debug_output
173
        std::cout << "Applying " << move << " to complex ";
174
        list_print(std::cout, _faces[_dimension].begin(), _faces[_dimension].end());
175
        std::cout << "." << std::endl;
176
        #endif
177
        if (move.codimension() == 0)
178
        {
179
            // remove face*∂link
180
            _faces[move.dimension()].erase(faceIt);
181
            _moves[move.codimension()].erase(moveIt);
182
            
183
            // add ∂face*link
184
            vertex_t largestVertex = 0;
185
            if (!_faces[0].empty())
186
            {
187
                for (face_list_t::const_iterator it = _faces[0].begin(); it != _faces[0].end(); it++)
188
                {
189
                    if (vertex_t_compare(&largestVertex, &(it->vertex(0))) < 0)
190
                        largestVertex = it->vertex(0);
191
                }
192
            }
193
            largestVertex++;
194
            Face newVertex(&largestVertex, 0);
195
            _faces[0].push_back(newVertex);
196
            
197
            face_list_t listOfSubfaces;
198
            addSubfacesOfFace(move.face(), listOfSubfaces);
199
            face_list_t listOfBoundaryfaces;
200
            addBoundaryfacesOfFace(move.face(), listOfBoundaryfaces);
201
            if (!listOfSubfaces.empty())
202
            {
203
                for (face_list_t::iterator it = listOfSubfaces.begin(); it != listOfSubfaces.end(); it++)
204
                {
205
                    Face newFace = Face::unite(*it, newVertex);
206
                    // add new face to complex
207
                    _faces[newFace.dimension()].push_back(newFace);
208
                    
209
                    // add new move options
210
                    if (newFace.dimension() == this->dimension())
211
                    {
212
                        _moves[0].push_back(std::make_pair(BistellarMove(newFace, Face()), true));
213
                    }
214
                    else
215
                    {
216
                        face_list_t listOfLinkFaces;
217
                        for (face_list_t::iterator it2 = listOfBoundaryfaces.begin(); it2 != listOfBoundaryfaces.end(); it2++)
218
                        {
219
                            if (it->isSubfaceOf(*it2))
220
                                listOfLinkFaces.push_back(*it2);
221
                        }
222
                        if (listOfLinkFaces.size() == this->dimension() - it->dimension() + 1)
223
                        {
224
                            Face linkFace = Face::linkFace(*it, listOfLinkFaces);
225
                            if (linkFace.dimension() <= this->dimension())
226
                                _moves[this->dimension() - it->dimension()].push_back(std::make_pair(BistellarMove(*it, linkFace), false));
227
                        }
228
                    }
229
                }
230
                updateBallBoundary(*this, listOfSubfaces);
231
            }
232
        }
233
        else
234
        {
235
            // remove face*∂link
236
            face_list_t listOfLinkSubfaces;
237
            addSubfacesOfFace(move.link(), listOfLinkSubfaces);
238
            
239
            _faces[move.dimension()].erase(faceIt);
240
            _moves[move.codimension()].erase(moveIt);
241
            if (!listOfLinkSubfaces.empty())
242
            {
243
                for (face_list_t::iterator it = listOfLinkSubfaces.begin(); it != listOfLinkSubfaces.end(); it++)
244
                {
245
                    // remove old faces
246
                    Face oldFace = Face::unite(move.face(), *it);
247
                    face_list_t::iterator oldFaceIt = std::find(_faces[oldFace.dimension()].begin(), _faces[oldFace.dimension()].end(), oldFace);
248
                    if (oldFaceIt != _faces[oldFace.dimension()].end())
249
                        _faces[oldFace.dimension()].erase(oldFaceIt);
250
                    
251
                    // remove old moves
252
                    if (!_moves[this->dimension() - oldFace.dimension()].empty())
253
                    {
254
                        for (bistellar_move_option_list_t::iterator oldMoveIt = _moves[this->dimension() - oldFace.dimension()].begin(); oldMoveIt != _moves[this->dimension() - oldFace.dimension()].end(); oldMoveIt++)
255
                        {
256
                            if (oldMoveIt->first.face() == oldFace)
257
                            {
258
                                _moves[this->dimension() - oldFace.dimension()].erase(oldMoveIt);
259
                                break;
260
                            }
261
                        }
262
                    }
263
                }
264
            }
265
            
266
            // add ∂face*link
267
            face_list_t listOfFaceSubfaces;
268
            addSubfacesOfFace(move.face(), listOfFaceSubfaces);
269
            listOfFaceSubfaces.push_back(Face());
270
            if (!listOfFaceSubfaces.empty())
271
            {
272
                face_list_t listOfNewFacets;
273
                face_list_t listOfBallInteriorFaces;
274
                
275
                // add the new faces                
276
                for (face_list_t::iterator it = listOfFaceSubfaces.begin(); it != listOfFaceSubfaces.end(); it++)
277
                {
278
                    Face newFace = Face::unite(*it, move.link());
279

280
                    if (_faces[newFace.dimension()].empty() || std::find(_faces[newFace.dimension()].begin(), _faces[newFace.dimension()].end(), newFace) == _faces[newFace.dimension()].end())
281
                    {
282
                        _faces[newFace.dimension()].push_back(newFace);
283
                    }
284

285
                    if (newFace.dimension() == this->dimension())
286
                    {
287
                        listOfNewFacets.push_back(newFace);
288
                    }
289
                    else
290
                    {
291
                        listOfBallInteriorFaces.push_back(newFace);
292
                    }
293
                }
294
                
295
                // add the new moves
296
                for (face_list_t::iterator it = listOfFaceSubfaces.begin(); it != listOfFaceSubfaces.end(); it++)
297
                {
298
                    Face newFace = Face::unite(*it, move.link());
299
                    if (newFace.dimension() == this->dimension())
300
                    {
301
                        _moves[0].push_back(std::make_pair(BistellarMove(newFace, Face()),true));
302
                    }
303
                    else
304
                    {
305
                        face_list_t listOfLinkFaces;
306
                        for (face_list_t::iterator it2 = listOfNewFacets.begin(); it2 != listOfNewFacets.end(); it2++)
307
                        {
308
                            if (newFace.isSubfaceOf(*it2))
309
                                listOfLinkFaces.push_back(*it2);
310
                        }
311
                        if (listOfLinkFaces.size() == this->dimension() - newFace.dimension() + 1)
312
                        {
313
                            Face linkFace = Face::linkFace(newFace, listOfLinkFaces);
314
                            if (linkFace.dimension() <= this->dimension())
315
                                _moves[this->dimension() - newFace.dimension()].push_back(std::make_pair(BistellarMove(newFace, linkFace), false));
316
                        }
317
                    }
318
                }
319
                
320
                face_list_t listOfBallBounaryFaces;
321
                if (!listOfNewFacets.empty())
322
                {
323
                    for (face_list_t::iterator it = listOfNewFacets.begin(); it != listOfNewFacets.end(); it++)
324
                    {
325
                        face_list_t listOfNewFacetSubfaces;
326
                        addSubfacesOfFace(*it, listOfNewFacetSubfaces);
327
                        if (!listOfNewFacetSubfaces.empty())
328
                        {
329
                            for (face_list_t::iterator it2 = listOfNewFacetSubfaces.begin(); it2 != listOfNewFacetSubfaces.end(); it2++)
330
                            {
331
                                if ((listOfBallInteriorFaces.empty() || std::find(listOfBallInteriorFaces.begin(), listOfBallInteriorFaces.end(), *it2) == listOfBallInteriorFaces.end())
332
                                    && (listOfBallBounaryFaces.empty() || std::find(listOfBallBounaryFaces.begin(), listOfBallBounaryFaces.end(), *it2) == listOfBallBounaryFaces.end()))
333
                                    listOfBallBounaryFaces.push_back(*it2);
334
                            }
335
                        }
336
                    }
337
                }
338
                
339
                updateBallBoundary(*this, listOfBallBounaryFaces);
340
            }
341
        }
342
        
343
        updateMoveValidity(*this);
344
        
345
        #ifdef Bistellar_debug_output
346
        std::cout << "Resulting complex is ";
347
        list_print(std::cout, _faces[_dimension].begin(), _faces[_dimension].end());
348
        std::cout << "." << std::endl;
349
        for (int i = 0; i < _dimension+1; i++)
350
        {
351
            std::cout << _moves[i].size() << " " << i << "-Moves: ";
352
            if (!_moves[i].empty()) list_print(std::cout, _moves[i].begin(), _moves[i].end());
353
            std::cout << std::endl;
354
        }
355
        #endif
356
    }
357
    else
358
    {
359
        #ifdef Bistellar_debug_output
360
        std::cout << move << " is not a valid move for the complex " << *this << std::endl;
361
        #endif
362
    }
363
}
364

365
// used in the implementation of moveComplex
366
void updateBallBoundary(MovableComplex & complex, const face_list_t & ballBoundaryFaces)
367
{
368
    if (!ballBoundaryFaces.empty())
369
    {
370
        for (face_list_t::const_iterator it = ballBoundaryFaces.begin(); it != ballBoundaryFaces.end(); it++)
371
        {
372
            face_list_t linkFacets;
373
            // copy all facets that contain (*it) as a subface to linkFacets
374
            if (!complex._faces[complex._dimension].empty())
375
            {
376
                for (face_list_t::const_iterator it2 = complex._faces[complex._dimension].begin(); it2 != complex._faces[complex._dimension].end(); it2++)
377
                {
378
                    if (it->isSubfaceOf(*it2))
379
                        linkFacets.push_back(*it2);
380
                }
381
            }
382
            
383
            // remove the move option with (*it) as face
384
            if (!complex._moves[complex._dimension - it->dimension()].empty())
385
            {
386
                if (!complex._moves[complex._dimension - it->dimension()].empty())
387
                {
388
                    for (bistellar_move_option_list_t::iterator mIt = complex._moves[complex._dimension - it->dimension()].begin(); mIt != complex._moves[complex._dimension - it->dimension()].end(); mIt++)
389
                    {
390
                        if (mIt->first.face() == *it)
391
                        {
392
                            complex._moves[complex._dimension - it->dimension()].erase(mIt);
393
                            break;
394
                        }
395
                    }
396
                }
397
            }
398
            
399
            
400
            if (linkFacets.size() == complex._dimension - it->dimension() + 1)
401
            {
402
                // add the move option.
403
                Face linkFace = Face::linkFace(*it, linkFacets);
404
                if (linkFace.dimension() <= complex._dimension)
405
                    complex._moves[complex._dimension - it->dimension()].push_back(std::make_pair(BistellarMove(*it, linkFace), (std::find(complex._faces[linkFace.dimension()].begin(), complex._faces[linkFace.dimension()].end(), linkFace) == complex._faces[linkFace.dimension()].end())));
406
            }
407
        }
408
    }
409
}
410
void updateMoveValidity(MovableComplex & complex)
411
{
412
    for (unsigned int i = 1; i < complex._dimension + 1; i++)
413
    {
414
        if (!complex._moves[i].empty())
415
        {
416
            for (bistellar_move_option_list_t::iterator it = complex._moves[i].begin(); it != complex._moves[i].end(); it++)
417
                it->second = (std::find(complex._faces[it->first.link().dimension()].begin(), complex._faces[it->first.link().dimension()].end(), it->first.link()) == complex._faces[it->first.link().dimension()].end());
418
        }
419
    }
420
}
421

422
// serialization methods
423
std::ostream & operator<< (std::ostream & os, const MovableComplex & complex)
424
{
425
    if (!complex._faces[complex._dimension].empty())
426
    {
427
        list_print(os ,complex._faces[complex._dimension].begin(), complex._faces[complex._dimension].end());
428
    }
429
    else
430
    {
431
        os << "[]";
432
    }
433
    return os;
434
}
435
std::istream & operator>> (std::istream & is, MovableComplex & complex)
436
{
437
    std::deque< Face > facets;
438
    list_read(is, facets);
439
    
440
    if (facets.empty())
441
    {
442
        complex = MovableComplex();
443
    }
444
    else
445
    {
446
        complex = MovableComplex(facets, facets.begin()->dimension());
447
    }
448
    
449
    return is;
450
}
451

452
Product

Resources

Company
