The Original CHomP Software
neighbor.h
Go to the documentation of this file.
1
3
14
15// Copyright (C) 1997-2020 by Pawel Pilarczyk.
16//
17// This file is part of my research software package. This is free software:
18// you can redistribute it and/or modify it under the terms of the GNU
19// General Public License as published by the Free Software Foundation,
20// either version 3 of the License, or (at your option) any later version.
21//
22// This software is distributed in the hope that it will be useful,
23// but WITHOUT ANY WARRANTY; without even the implied warranty of
24// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25// GNU General Public License for more details.
26//
27// You should have received a copy of the GNU General Public License
28// along with this software; see the file "license.txt". If not,
29// please, see <https://www.gnu.org/licenses/>.
30
31// Started in January 2002. Last revision: October 25, 2008.
32
33
34#ifndef _CHOMP_CUBES_NEIGHBOR_H_
35#define _CHOMP_CUBES_NEIGHBOR_H_
36
37#include "chomp/system/config.h"
42#include "chomp/cubes/cube.h"
43#include "chomp/cubes/cell.h"
47
48#include <iostream>
49#include <fstream>
50#include <cstdlib>
51
52namespace chomp {
53namespace homology {
54
55// --------------------------------------------------
56// ----------------- max neighbors ------------------
57// --------------------------------------------------
58
60inline int_t getmaxneighbors (int dim)
61{
62 if (dim < 0)
63 return 0;
64 const int maxdim = 17;
65 const int neighbors [maxdim] = {0, 2, 8, 26, 80, 242, 728,
66 2186, 6560, 19682, 59048, 177146, 531440, 1594322,
67 4782968, 14348906, 43046720};
68 if (dim < maxdim)
69 return neighbors [dim];
70 int_t ncount = neighbors [maxdim - 1] + 1;
71 for (int i = maxdim - 1; i < dim; ++ i)
72 ncount *= 3;
73 return (ncount - 1);
74} /* getmaxneighbors */
75
76
77// --------------------------------------------------
78// ----------------- neighbor bits ------------------
79// --------------------------------------------------
80
83template <class tCube>
84int_t neighbor2bit (const tCube &q, const tCube &neighbor)
85{
86 // define the type of coordinates
87 typedef typename tCube::CoordType coordType;
88
89 coordType c0 [tCube::MaxDim];
90 q. coord (c0);
91 coordType c1 [tCube::MaxDim];
92 neighbor. coord (c1);
93 int dim = q. dim ();
94
95 int_t number = 0;
96 const coordType *wrap = tCube::PointBase::getwrapping (dim);
97 for (int i = 0; i < dim; ++ i)
98 {
99 if (i)
100 number *= 3;
101 switch (c1 [i] - c0 [i])
102 {
103 case -1:
104 ++ number;
105 case 1:
106 ++ number;
107 break;
108 case 0:
109 break;
110 default:
111 if (!wrap || !wrap [i])
112 return -1;
113 if ((c1 [i] - c0 [i]) == (wrap [i] - 1))
114 number += 2;
115 else if ((c1 [i] - c0 [i]) == (1 - wrap [i]))
116 ++ number;
117 else
118 return -1;
119 break;
120 }
121 }
122
123 return number - 1;
124} /* neighbor2bit */
125
128template <class tCube>
129int_t neighbor2bit (const tCube &q, const typename tCube::CellType &face)
130{
131 // define the type of coordinates
132 typedef typename tCube::CoordType coordType;
133
134 // determine the space dimension and the coordinates of the input
135 int dim = q. dim ();
136 coordType coord [tCube::MaxDim];
137 q. coord (coord);
138 coordType cLeft [tCube::MaxDim];
139 face. leftcoord (cLeft);
140 coordType cRight [tCube::MaxDim];
141 face. rightcoord (cRight);
142
143 // compute the number of the neighbor based on the coordinates
144 int_t number = 0;
145 for (int i = 0; i < dim; ++ i)
146 {
147 if (i)
148 number *= 3;
149 // if the neighbor is shifted upwards
150 if (cLeft [i] != coord [i])
151 number += 1;
152 // if the neighbor is shifted downwards
153 else if (cRight [i] == cLeft [i])
154 number += 2;
155 // otherwise the neighbor is at the same level
156 }
157
158 return number - 1;
159} /* neighbor2bit */
160
164template <class tCube>
165tCube bit2neighbor (const tCube &q, int_t number, bool unconditional = false)
166{
167 // define the type of coordinates
168 typedef typename tCube::CoordType coordType;
169
170 coordType c0 [tCube::MaxDim];
171 q. coord (c0);
172 coordType c1 [tCube::MaxDim];
173 int dim = q. dim ();
174
175 ++ number;
176 for (int i = dim - 1; i >= 0; -- i)
177 {
178 switch (number % 3)
179 {
180 case 2:
181 c1 [i] = c0 [i] - 1;
182 break;
183 case 1:
184 c1 [i] = c0 [i] + 1;
185 break;
186 case 0:
187 c1 [i] = c0 [i];
188 break;
189 default:
190 throw "Erratic neighbor.";
191 }
192 number /= 3;
193 }
194
195 if (unconditional || tCube::PointBase::check (c1, dim))
196 return tCube (c1, dim);
197 else
198 return q;
199} /* bit2neighbor */
200
201
202// --------------------------------------------------
203// ----------------- get neighbors ------------------
204// --------------------------------------------------
205
210template <class tCube, class tCubeSet1, class tCubeSet2>
211int_t getneighbors_scan (const tCube &q, BitField *bits,
212 const tCubeSet1 &theset, tCubeSet2 *neighbors, int_t limit)
213{
214 // prepare a counter for the number of neighbors
215 int_t count = 0;
216
217 // go through all the elements in the set
218 for (int_t i = 0; i < theset. size (); ++ i)
219 {
220 // if this is the current cube, ignore it
221 if (theset [i] == q)
222 continue;
223
224 // determine the number of this neighbor
225 int_t number = neighbor2bit (q, theset [i]);
226
227 // if not neighbor, ignore it
228 if (number < 0)
229 continue;
230
231 // set the corresponding bit in the bit field
232 if (bits)
233 bits -> set (number);
234
235 // add the cube to the set of neighbors
236 if (neighbors)
237 neighbors -> add (theset [i]);
238
239 // increase the counter
240 ++ count;
241
242 // if this is enough then finish
243 if (limit && (count >= limit))
244 return count;
245 }
246
247 return count;
248} /* getneighbors_scan */
249
254template <class tCube, class tCubeSet1, class tCubeSet2>
255int_t getneighbors_generate (const tCube &q, BitField *bits,
256 const tCubeSet1 &theset, tCubeSet2 *neighbors, int_t limit)
257{
258 // determine the upper bound for the number of neighbors
259 int_t maxneighbors = getmaxneighbors (q. dim ());
260
261 // prepare a counter for the number of neighbors
262 int_t count = 0;
263
264 // go through all possible neighbor numbers
265 for (int_t number = 0; number < maxneighbors; ++ number)
266 {
267 // create a neighbor cube
268 tCube neighbor = bit2neighbor (q, number);
269
270 // if the neighbor doesn't exist, ignore it
271 if (neighbor == q)
272 continue;
273
274 // if this cube is not in the set, ignore it
275 if (!theset. check (neighbor))
276 continue;
277
278 // set the appropriate bit in the bit field
279 if (bits)
280 bits -> set (number);
281
282 // add the cube to the set of neighbors
283 if (neighbors)
284 neighbors -> add (neighbor);
285
286 // increase the counter
287 ++ count;
288
289 // if this is enough then finish
290 if (limit && (count >= limit))
291 return count;
292 }
293
294 return count;
295} /* getneighbors_generate */
296
301template <class tCube, class tCubeSet1, class tCubeSet2>
302int_t getneighbors (const tCube &q, BitField *bits,
303 const tCubeSet1 &theset, tCubeSet2 *neighbors, int_t limit)
304{
305 // if the answer is trivial, return it
306 if (theset. empty ())
307 return 0;
308
309 // if the set is small
310 if (theset. size () < getmaxneighbors (q. dim ()))
311 {
312 return getneighbors_scan (q, bits, theset, neighbors, limit);
313 }
314 else
315 {
316 return getneighbors_generate (q, bits, theset, neighbors,
317 limit);
318 }
319} /* getneighbors */
320
325template <class tCube, class tCubeSet>
326int_t getneighbors (const tCube &q, BitField *bits,
327 const tCubeSet &theset, int_t limit)
328{
330 return getneighbors (q, bits, theset, none, limit);
331} /* getneighbors */
332
333
334// --------------------------------------------------
335// ----------------- add neighbors ------------------
336// --------------------------------------------------
337
341template <class tCube, class tCubeSet>
342int_t addneighbors (const tCube &q, const BitField &bits, tCubeSet &set,
343 const tCubeSet &notthese)
344{
345 int_t maxneighbors = getmaxneighbors (q. dim ());
346
347 int_t count = 0;
348 int_t number = bits. find (0, maxneighbors);
349 while (number >= 0)
350 {
351 tCube neighbor = bit2neighbor (q, number);
352 if (!notthese. check (neighbor))
353 set. add (neighbor);
354 number = bits. find (number + 1, maxneighbors);
355 ++ count;
356 }
357
358 return count;
359} /* addneighbors */
360
363template <class tCube, class tCubeSet>
364int_t addneighbors (const tCube &q, const BitField &bits, tCubeSet &set,
365 bool unconditional = false)
366{
367 int_t maxneighbors = getmaxneighbors (q. dim ());
368 int_t count = 0;
369
370 int_t number = bits. find (0, maxneighbors);
371 while (number >= 0)
372 {
373 tCube neighbor = bit2neighbor (q, number, unconditional);
374 set. add (neighbor);
375 number = bits. find (number + 1, maxneighbors);
376 ++ count;
377 }
378
379 return count;
380} /* addneighbors */
381
385template <class tCube, class tCell>
386int_t addneighbors (const tCube &q, const BitField &bits,
387 gcomplex<tCell,integer> &c, bool unconditional = false)
388{
389 // define the type of coordinates
390 typedef typename tCube::CoordType coordType;
391
392 // determine the space dimension
393 int dim = q. dim ();
394
395 // compute the maximal number of neighbors
396 int_t maxneighbors = getmaxneighbors (dim);
397
398 // extract the coordinates of the central cube
399 coordType coord [tCube::MaxDim];
400 q. coord (coord);
401
402 // prepare arrays for the coordinates of boundary cells
403 coordType cLeft [tCube::MaxDim];
404 coordType cRight [tCube::MaxDim];
405
406 // prepare a counter of boundary cells
407 int_t count = 0;
408
409 // find the first neighbor number
410 int_t number = bits. find (0, maxneighbors);
411
412 // process all the neighbor numbers
413 while (number >= 0)
414 {
415 // prepare the coordinates of the boundary cell
416 int_t n = number + 1;
417 for (int i = dim - 1; i >= 0; -- i)
418 {
419 switch (n % 3)
420 {
421 case 2:
422 cLeft [i] = coord [i];
423 cRight [i] = coord [i];
424 break;
425 case 1:
426 cLeft [i] = coord [i] + 1;
427 cRight [i] = coord [i] + 1;
428 break;
429 case 0:
430 cLeft [i] = coord [i];
431 cRight [i] = coord [i] + 1;
432 break;
433 }
434 n /= 3;
435 }
436
437 // add the cell to the complex of boundary cells
438 c. add (tCell (cLeft, cRight, dim));
439
440 // increase the counter of boundary cells
441 ++ count;
442
443 // take the next neighbor number
444 number = bits. find (number + 1, maxneighbors);
445 }
446
447 return count;
448} /* addneighbors */
449
450
451} // namespace homology
452} // namespace chomp
453
454#endif // _CHOMP_CUBES_NEIGHBOR_H_
455
457
This file contains functions generated using Binary Decision Diagrams for checking the acyclicity of ...
This file includes header files with various definitions of cubical cells and defines the standard ty...
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
The class that defines a geometric complex - a set of cells (cubes, simplices, etc).
Definition: gcomplex.h:85
This is a template for a set of objects of the given type.
Definition: hashsets.h:185
This class can be used for iterating point's neighbors.
Definition: pointset.h:1450
This file contains some precompiler definitions which indicate the operating system and/or compiler u...
This file includes header files with various definitions of full cubes and defines the standard types...
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 contains the definition of a tabulated set of configurations of full cubical neighborhood u...
tCube bit2neighbor(const tCube &q, int_t number, bool unconditional=false)
Creates the neighbor of the given cube with the specified number.
Definition: neighbor.h:165
int_t neighbor2bit(const tCube &q, const tCube &neighbor)
Returns the number of the neighbor bit for the given neighbor of 'q' or -1 if not a neighbor or the s...
Definition: neighbor.h:84
int_t getneighbors(const tCube &q, BitField *bits, const tCubeSet1 &theset, tCubeSet2 *neighbors, int_t limit)
Gets neighbors of the given cube from the given set and indicates them in the bit field provided.
Definition: neighbor.h:302
int_t getneighbors_scan(const tCube &q, BitField *bits, const tCubeSet1 &theset, tCubeSet2 *neighbors, int_t limit)
Gets neighbors of the given cube from the given set and indicates them in the bit field provided.
Definition: neighbor.h:211
int_t getmaxneighbors(int dim)
Returns the maximal number of neighbors of a cube: 3^dim - 1.
Definition: neighbor.h:60
void addneighbors(const int &c, const SetT &s, QueueT &q)
Adds the neighbors of the cube 'c' in the set 's' to the set 'q'.
Definition: bincube.h:1048
int_t getneighbors_generate(const tCube &q, BitField *bits, const tCubeSet1 &theset, tCubeSet2 *neighbors, int_t limit)
Gets neighbors of the given cube from the given set and indicates them in the bit field provided.
Definition: neighbor.h:255
This namespace contains the entire CHomP library interface.
Definition: bitmaps.h:51
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 a class which stores tabulated configuration of full cubical nei...
This file contains some useful functions related to the text input/output procedures.