The Original CHomP Software
cubired0.h
Go to the documentation of this file.
1
3
15
16// Copyright (C) 1997-2020 by Pawel Pilarczyk.
17//
18// This file is part of my research software package. This is free software:
19// you can redistribute it and/or modify it under the terms of the GNU
20// General Public License as published by the Free Software Foundation,
21// either version 3 of the License, or (at your option) any later version.
22//
23// This software is distributed in the hope that it will be useful,
24// but WITHOUT ANY WARRANTY; without even the implied warranty of
25// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26// GNU General Public License for more details.
27//
28// You should have received a copy of the GNU General Public License
29// along with this software; see the file "license.txt". If not,
30// please, see <https://www.gnu.org/licenses/>.
31
32// Started in January 2002. Last revision: February 2, 2018.
33
34
35#ifndef _CHOMP_HOMOLOGY_CUBIRED0_H_
36#define _CHOMP_HOMOLOGY_CUBIRED0_H_
37
38#include "chomp/system/config.h"
49#include "chomp/cubes/cube.h"
50#include "chomp/cubes/cell.h"
51#include "chomp/cubes/cubmaps.h"
57
58#include <iostream>
59#include <fstream>
60#include <cstdlib>
61
62namespace chomp {
63namespace homology {
64namespace reduction0 {
65
66
67// --------------------------------------------------
68// ------------------ reduce cubes ------------------
69// --------------------------------------------------
70
83template <class tCube, class tVerify>
86 const hashedset<tCube> &keep, const tVerify &verify,
87 bool quiet = true)
88{
89 // remember the initial number of cubes in both sets
90 int_t prev = cset. size () + other. size ();
91
92 // if the case is trivial, return the answer
93 if (maincset. empty () && cset. empty ())
94 {
95 if (!other. empty ())
96 {
97 hashedset<tCube> empty;
98 other = empty;
99 }
100 return prev;
101 }
102
103 // determine the space dimension
104 int dim = (cset. empty ()) ? maincset [0]. dim () :
105 cset [0]. dim ();
106
107 // compute the maximal number of neighbors of a cube
108 int_t maxneighbors = getmaxneighbors (dim);
109
110 // prepare a bitfield for storing neighborhood configurations
111 // and allocate the buffer if necessary (this is a static variable)
112 static BitField b;
113 static int_t _maxneighbors = 0;
114 static auto_array<unsigned char> buffer;
115 if (maxneighbors != _maxneighbors)
116 {
117 _maxneighbors = maxneighbors;
118 buffer. reset (new unsigned char [(maxneighbors + 7) >> 3]);
119 b. define (buffer. get (), maxneighbors);
120 }
121
122 // prepare a counter for displaying the progress of computations
123 int_t count = 0;
124
125 // repeat scanning cubes until no change can be made
126 while (1)
127 {
128 // remember if any changes were made in this round
129 bool modified (false);
130
131 // scan all the cubs in both sets
132 for (int_t i = 0; i < cset. size () + other. size (); ++ i)
133 {
134 // show the progress indicator
135 ++ count;
136 if (!quiet && !(count % 373))
137 scon << std::setw (10) << count <<
138 "\b\b\b\b\b\b\b\b\b\b";
139
140 // is this cube from the other set?
141 bool is_other (i >= cset. size ());
142
143 // determine the cube corresponding to the index
144 const tCube &c (is_other ?
145 other [i - cset. size ()] : cset [i]);
146
147 // if this cube is to be kept then skip it
148 if (keep. check (c))
149 continue;
150
151 // clean the neighborbits
152 b. clearall (maxneighbors);
153
154 // if this cube belongs to the other set...
155 if (is_other)
156 {
157 // no neighbors need to be remembered
158 hashedset<tCube> *no_neighbors (0);
159
160 // check if this cube can be removed
161 if (!acyclic_rel (c, dim,
162 makesetunion (maincset, cset),
163 other, &b, maxneighbors,
164 no_neighbors, no_neighbors))
165 {
166 continue;
167 }
168
169 // verify if the removal of the cube from A is OK
170 if (!verify (c, other))
171 continue;
172
173 // verify if the removal of the cube from X is OK
174 if (!verify (c, makesetunion (maincset,
175 makesetunion (other, cset))))
176 {
177 continue;
178 }
179
180 // remove the cube from the other set
181 modified = true;
182 if (!quiet)
183 sseq << '0' << c << '\n';
184 other. removenum (i - cset. size ());
185 -- i;
186 }
187
188 // otherwise, if this cube belongs to 'cset'...
189 else
190 {
191 // no neighbors need to be remembered
192 hashedset<tCube> *no_neighbors (0);
193
194 // if the neighborhood of the cube
195 // is not acyclic then skip the cube
196 if (!acyclic (c, dim, makesetunion (maincset,
197 makesetunion (cset, other)),
198 &b, maxneighbors, no_neighbors))
199 {
200 continue;
201 }
202
203 // verify if the removal of the cube from X is OK
204 if (!verify (c, makesetunion (maincset,
205 makesetunion (cset, other))))
206 {
207 continue;
208 }
209
210 // remove the cube from 'cset'
211 modified = true;
212 if (!quiet)
213 sseq << '0' << c << '\n';
214 cset. removenum (i);
215 -- i;
216 }
217 }
218
219 // if the sets were not modified then quit the loop
220 if (!modified)
221 break;
222 }
223
224 // return the number of cubes removed from both sets
225 return prev - cset. size () - other. size ();
226} /* cubreducequiet */
227
228
229// --------------------------------------------------
230// ------------------ expand cubes ------------------
231// --------------------------------------------------
232
238template <class tCube, class tVerify>
240 const tVerify &verify, bool quiet = false)
241{
242 // if the case is trivial, return the answer
243 if (cset. empty () || other. empty ())
244 return 0;
245
246 // remember the initial number of cubes in the main set
247 int_t prev = cset. size ();
248
249 // determine the space dimension
250 int dim = cset [0]. dim ();
251
252 // compute the maximal number of neighbors of a cube
253 int_t maxneighbors = getmaxneighbors (dim);
254
255 // prepare a bitfield and allocate it if necessary
256 static BitField b;
257 static int_t _maxneighbors = 0;
258 static auto_array<unsigned char> buffer;
259 if (maxneighbors != _maxneighbors)
260 {
261 _maxneighbors = maxneighbors;
262 buffer. reset (new unsigned char [(maxneighbors + 7) >> 3]);
263 b. define (buffer. get (), maxneighbors);
264 }
265
266 // prepare a counter for displaying the progress of computations
267 int_t count = 0;
268
269 // repeat scanning cubes until no change can be made
270 while (1)
271 {
272 // remember if any changes were made in this round
273 bool modified (false);
274
275 // go through the main set, and move cubes to the other set
276 // if this doesn't change the homology
277 for (int_t i = 0; i < cset. size (); ++ i)
278 {
279 // show progress indicator
280 ++ count;
281 if (!quiet && !(count % 373))
282 scon << std::setw (10) << count <<
283 "\b\b\b\b\b\b\b\b\b\b";
284
285 // take a cube from 'cset'
286 const tCube &c = cset [i];
287
288 // clear the neighborbits
289 b. clearall (maxneighbors);
290
291 // if the neighborhood of the cube is not acyclic, skip it
292 if (!acyclic (c, dim, other, &b, maxneighbors))
293 continue;
294
295 // verify if moving this cube to 'other' is allowed
296 if (!verify (c, cset, other))
297 continue;
298
299 // move the cube to the other set
300 modified = true;
301 if (!quiet)
302 sseq << "L\n" << '2' << c << '\n';
303 other. add (c);
304 cset. removenum (i);
305 -- i;
306 }
307
308 // if the sets were not modified then quit the loop
309 if (!modified)
310 break;
311 }
312
313 // return the number of cubes removed from 'cset'
314 return prev - cset. size ();
315} /* cubexpand */
316
317
318} // namespace reduction0
319} // namespace homology
320} // namespace chomp
321
322#endif // _CHOMP_HOMOLOGY_CUBIRED0_H_
323
325
An auto_array template that mimics selected behaviors of the std::auto_ptr template,...
This file contains functions generated using Binary Decision Diagrams for checking the acyclicity of ...
This file contains the definition of a bitfield class which works an array of bits.
This file includes header files with various definitions of cubical cells and defines the standard ty...
This file contains classes and functions related to algebraic chain complexes and chain maps,...
This class defines a bit field that is part of some larger array or that uses an allocated piece of m...
Definition: bitfield.h:73
An auto_array template that mimics selected behaviors of the std::auto_ptr template,...
Definition: autoarray.h:54
This file contains some precompiler definitions which indicate the operating system and/or compiler u...
This file contains procedures for the verification of acyclicity of full cubical sets,...
This file includes header files with various definitions of full cubes and defines the standard types...
This file contains some procedures defined for cubical maps.
This file contains a definition of a general geometric complex which represents a polyhedron.
int int_t
Index type for indexing arrays, counting cubes, etc.
Definition: config.h:115
This file contains the definition of the container "hashedset" which can be used to represent a set o...
This file defines a class "integer" which represents the ring of integers or the field of integers mo...
This file contains the definition of a tabulated set of configurations of full cubical neighborhood u...
int_t cubreducequiet(const hashedset< tCube > &maincset, hashedset< tCube > &cset, hashedset< tCube > &other, const hashedset< tCube > &keep, const tVerify &verify, bool quiet=true)
Reduces a pair of sets of cubes for relative homology computation.
Definition: cubired0.h:84
int_t cubexpand(hashedset< tCube > &cset, hashedset< tCube > &other, const tVerify &verify, bool quiet=false)
Expands the set 'other' towards 'cset' without changing the homology of (cset + other,...
Definition: cubired0.h:239
outputstream sseq
An auxiliary stream which captures sequences of processed data.
bool acyclic(int dim, BitField &b)
Checks whether this cube's nieghbors form an acyclic set.
Definition: cubacycl.h:70
bool acyclic_rel(const tCube &q, int dim, const tSet1 &cset, const tSet2 &other, BitField *b, int_t maxneighbors, hashedset< tCube > *neighbors_main, hashedset< tCube > *neighbors_other)
Verifies whether a cube from the other set can be removed.
Definition: cubacycl.h:183
setunion< set1type, set2type > makesetunion(const set1type &set1, const set2type &set2)
Creates an object which represents the union of two sets.
Definition: setunion.h:225
int_t getmaxneighbors(int dim)
Returns the maximal number of neighbors of a cube: 3^dim - 1.
Definition: neighbor.h:60
outputstream scon
The console output stream to which one should put all the junk that spoils the log file,...
This namespace contains the entire CHomP library interface.
Definition: bitmaps.h:51
This file contains various procedures relating to neighborhoods of cubes in full cubical sets.
This file contains the definition of a point base class which is used for indexing all the points (n-...
This file contains the definition of a set of n-dimensional points with integer coordinates and sever...
This file contains the definition of the container "setunion".
This file contains the definition of a class which stores tabulated configuration of full cubical nei...
This file contains some useful functions related to the text input/output procedures.