1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
|
/**************************************************************************
* *
* Regina - A Normal Surface Theory Calculator *
* Computational Engine *
* *
* Copyright (c) 1999-2011, Ben Burton *
* For further details contact Ben Burton (bab@debian.org). *
* *
* This program is free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License as *
* published by the Free Software Foundation; either version 2 of the *
* License, or (at your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, but *
* WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
* General Public License for more details. *
* *
* You should have received a copy of the GNU General Public *
* License along with this program; if not, write to the Free *
* Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, *
* MA 02110-1301, USA. *
* *
**************************************************************************/
/* end stub */
/*! \file census/ncensus.h
* \brief Deals with forming a census of all 3-manifold triangulations
* of a given size.
*/
#ifndef __NCENSUS_H
#ifndef __DOXYGEN
#define __NCENSUS_H
#endif
#include "regina-core.h"
#include "census/nfacepairing.h"
#include "utilities/nbooleans.h"
namespace regina {
class NGluingPerms;
class NGluingPermSearcher;
class NPacket;
class NProgressManager;
class NProgressMessage;
class NTriangulation;
/**
* \addtogroup census Census of Triangulations
* Census building for 3-manifold triangulations.
* @{
*/
/**
* A legacy typedef that is identical to NCensus::AcceptTriangulation.
* See NCensus::AcceptTriangulation for further details.
*
* \deprecated This global typedef is now deprecated. Please use the
* identical class typedef NCensus::AcceptTriangulation instead.
*/
typedef bool (*AcceptTriangulation)(NTriangulation*, void*);
/**
* A utility class used to form a complete census of 3-manifold
* triangulations satisfying certain constraints.
*
* \testpart
*/
class REGINA_API NCensus {
public:
static const int PURGE_NON_MINIMAL;
/**< Indicates that non-minimal triangulations may be ignored. */
static const int PURGE_NON_PRIME;
/**< Indicates that any triangulation that is not prime (i.e.,
can be written as a non-trivial connected sum) and any
bounded triangulation that is reducible over a disc may be
ignored. */
static const int PURGE_NON_MINIMAL_PRIME;
/**< Indicates that any triangulation that is not prime (i.e.,
can be written as a non-trivial connected sum), any
bounded triangulation that is reducible over a disc and
any triangulation that is non-minimal may be ignored.
Note that this is simply a combination of the constants
\a PURGE_NON_MINIMAL and \a PURGE_NON_PRIME. */
static const int PURGE_P2_REDUCIBLE;
/**< Indicates that any triangulation containing an embedded
two-sided projective plane may be ignored. */
/**
* A routine used to determine whether a particular triangulation
* should be included in a census. Routines of this type are used by
* NCensus::formCensus().
*
* The first parameter passed should be a triangulation currently
* under consideration.
* The second parameter may contain arbitrary data as passed to
* NCensus::formCensus().
*
* The return value should be \c true if the triangulation passed
* should be included in the census, or \c false otherwise.
*/
typedef bool (*AcceptTriangulation)(NTriangulation*, void*);
private:
NPacket* parent;
/**< The argument passed to formCensus(). */
NBoolSet finiteness;
/**< The argument passed to formCensus(). */
NBoolSet orientability;
/**< The argument passed to formCensus(). */
int whichPurge;
/**< The argument passed to formCensus(). */
AcceptTriangulation sieve;
/**< The arbitrary constraint function to run triangulations
through. */
void* sieveArgs;
/**< The second argument to pass to function \a sieve. */
NProgressMessage* progress;
/**< Reports the current state of progress of the census
generation. This will be 0 if progress reporting is
not required. */
unsigned long whichSoln;
/**< The number of the solution we are up to. */
public:
/**
* Fills the given packet with all triangulations in a census of
* 3-manifold triangulations satisfying the given constraints.
* Each triangulation in the census will appear as a child of the
* given packet.
*
* This routine will conduct a census of all valid triangulations
* containing a given number of tetrahedra. All such triangulations
* are included in the census up to combinatorial isomorphism; given
* any isomorphism class, exactly one representative will appear in
* the census.
*
* The census can be optionally restricted to only include
* triangulations satisfying further constraints (such as
* orientability and finiteness); see the individual parameter
* descriptions for further details. In particular, parameter
* \a sieve can be used to impose arbitrary restrictions that are
* not hard-coded into this class.
*
* Note that if constraints may be imposed using the hard-coded
* parameters (such as orientability and finiteness), it is
* generally better to do this than to use the arbitrary
* constraint parameter \a sieve. Hard-coded parameters will be
* tested earlier, and some (such as orientability) can be
* incorporated directly into the census algorithm to give a vast
* performance increase.
*
* Parameter \a whichPurge may be used to further avoid constructing
* triangulations satisfying particular constraints (such as
* non-minimality). This can significantly speed up the census.
* In this case however not all such triangulations will be
* avoided, but it is guaranteed that every triangulation that
* does \e not satisfy the constraints defined by \a whichPurge
* will be produced.
*
* Only valid triangulations will be produced; see
* NTriangulation::isValid() for further details.
*
* Note that this routine should only be used if the census
* contains a small enough total number of triangulations to
* avoid any memory disasters.
*
* If a progress manager is passed, the calculation will run in a new
* thread and this routine will return immediately. Otherwise
* the calculation will run in the current thread and this
* routine will only return once the census is complete.
*
* \ifacespython Parameters \a sieve, \a sieveArgs and \a manager
* are not present (and will be treated as 0).
*
* @param parent the packet beneath which members of the census will
* be placed.
* @param nTetrahedra the number of tetrahedra in each triangulation
* in the census.
* @param finiteness determines whether to include finite and/or ideal
* triangulations. The set should contain \c true if finite (non-ideal)
* triangulations are to be included, and should contain \c false if
* ideal triangulations are to be included.
* @param orientability determines whether to include orientable
* and/or non-orientable triangulations. The set should contain \c true
* if orientable triangulations are to be included, and should contain
* \c false if non-orientable triangulations are to be included.
* @param boundary determines whether to include triangulations with
* and/or without boundary faces. The set should contain \c true
* if triangulations with boundary faces are to be included, and
* should contain \c false if triangulations with only internal
* faces are to be included.
* @param nBdryFaces specifies the precise number of boundary faces
* that should be present in the triangulations produced. If this
* parameter is negative, it is ignored and no additional restriction
* is imposed. See the documentation for routine
* NFacePairing::findAllPairings() for details regarding this
* parameter and how it interacts with parameter \a boundary.
* @param whichPurge specifies which triangulations we may further
* avoid constructing (see the function notes above for details).
* This should be a bitwise OR of purge constants defined in this
* class, or 0 if no additional pruning should take place.
* If a variety of purge constants are bitwise ORed together, a
* triangulation satisfying \e any of these constraints may be
* avoided. Note that not all such triangulations will be
* avoided, but enough are avoided that the performance increase
* is noticeable.
* @param sieve an additional constraint function that may be
* used to exclude certain triangulations from the census. If
* this parameter is non-zero, each triangulation produced (after
* passing all other criteria) will be passed through this
* function. If this function returns \c true then the triangulation
* will be included in the census; otherwise it will not.
* When this function is called, the first (triangulation)
* argument will be a triangulation under consideration for
* inclusion in the census. The second argument will be
* parameter \a sieveArgs as passed to formCensus().
* Parameter \a sieve may be passed as \c null (in which case no
* additional constraint function will be used).
* @param sieveArgs the pointer to pass as the final parameter
* for the function \a sieve which will be called upon each
* triangulation found. If \a sieve is \c null then \a sieveArgs
* will be ignored.
* @param manager a progress manager via which progess will be reported,
* or 0 if no progress reporting is required. If non-zero,
* \a manager must point to a progress manager for which
* NProgressManager::isStarted() is still \c false.
* @return the number of triangulations produced in the census, or 0 if
* a progress manager was passed.
*/
static unsigned long formCensus(NPacket* parent, unsigned nTetrahedra,
NBoolSet finiteness, NBoolSet orientability, NBoolSet boundary,
int nBdryFaces, int whichPurge, AcceptTriangulation sieve = 0,
void* sieveArgs = 0, NProgressManager* manager = 0);
/**
* Fills the given packet with all triangulations in a partial census
* of 3-manifold triangulations satisfying the given constraints.
* Each triangulation in the partial census will appear as a child of
* the given packet.
*
* This routine will conduct a census of all valid triangulations
* that are modelled by the given tetrahedron face pairing.
* All such triangulations are included in the census up to
* combinatorial isomorphism; given any isomorphism class, exactly
* one representative will appear in the census.
*
* The census can be optionally restricted to only include
* triangulations satisfying further constraints (such as
* orientability and finiteness); see the individual parameter
* descriptions for further details. In particular, parameter
* \a sieve can be used to impose arbitrary restrictions that are
* not hard-coded into this class.
*
* Note that if constraints may be imposed using the hard-coded
* parameters (such as orientability and finiteness), it is
* generally better to do this than to use the arbitrary
* constraint parameter \a sieve. Hard-coded parameters will be
* tested earlier, and some (such as orientability) can be
* incorporated directly into the census algorithm to give a vast
* performance increase.
*
* Parameter \a whichPurge may be used to further avoid constructing
* triangulations satisfying particular constraints (such as
* non-minimality). The use of this parameter, combined with
* parameters \a finiteness and \a orientability, can significantly
* speed up the census. For some combinations of these
* parameters entirely different algorithms are used.
*
* Note however that not all triangulations described by
* parameter \a whichPurge will be avoided. It is guaranteed
* however that every triangulation that does \e not satisfy the
* constraints defined by \a whichPurge will be produced.
*
* Only valid triangulations will be produced; see
* NTriangulation::isValid() for further details.
*
* Note that this routine should only be used if the partial census
* contains a small enough total number of triangulations to
* avoid any memory disasters.
*
* The partial census will run in the current thread. This
* routine will only return once the partial census is complete.
*
* \pre The given face pairing is connected, i.e., it is possible
* to reach any tetrahedron from any other tetrahedron via a
* series of matched face pairs.
* \pre The given face pairing is in canonical form as described
* by NFacePairing::isCanonical(). Note that all face pairings
* constructed by NFacePairing::findAllPairings() are of this form.
*
* \ifacespython Parameters \a sieve and \a sieveArgs
* are not present (and will be treated as 0).
*
* @param pairing the tetrahedron face pairing that
* triangulations in this partial census must be modelled by.
* @param parent the packet beneath which members of the partial
* census will be placed.
* @param finiteness determines whether to include finite and/or ideal
* triangulations. The set should contain \c true if finite (non-ideal)
* triangulations are to be included, and should contain \c false if
* ideal triangulations are to be included.
* @param orientability determines whether to include orientable
* and/or non-orientable triangulations. The set should contain \c true
* if orientable triangulations are to be included, and should contain
* \c false if non-orientable triangulations are to be included.
* @param whichPurge specifies which triangulations we may further
* avoid constructing (see the function notes above for details).
* This should be a bitwise OR of purge constants defined in this
* class, or 0 if no additional pruning should take place.
* If a variety of purge constants are bitwise ORed together, a
* triangulation satisfying \e any of these constraints may be
* avoided. Note that not all such triangulations will be
* avoided, but enough are avoided that the performance increase
* is noticeable.
* @param sieve an additional constraint function that may be
* used to exclude certain triangulations from the census. If
* this parameter is non-zero, each triangulation produced (after
* passing all other criteria) will be passed through this
* function. If this function returns \c true then the triangulation
* will be included in the census; otherwise it will not.
* When this function is called, the first (triangulation)
* argument will be a triangulation under consideration for
* inclusion in the census. The second argument will be
* parameter \a sieveArgs as passed to formPartialCensus().
* Parameter \a sieve may be passed as \c null (in which case no
* additional constraint function will be used).
* @param sieveArgs the pointer to pass as the final parameter
* for the function \a sieve which will be called upon each
* triangulation found. If \a sieve is \c null then \a sieveArgs
* will be ignored.
* @return the number of triangulations produced in the partial census.
*/
static unsigned long formPartialCensus(const NFacePairing* pairing,
NPacket* parent, NBoolSet finiteness, NBoolSet orientability,
int whichPurge, AcceptTriangulation sieve = 0, void* sieveArgs = 0);
/**
* Determines whether the given triangulation even has a chance
* at being minimal. This routine can be passed as parameter
* \a sieve to routine NCensus::formCensus() to exclude obviously
* non-minimal triangulations from a census.
*
* A variety of tests will be performed; these tests are subject
* to change between Regina releases. Currently this routine
* counts vertices and also tries to simplify the triangulation using
* NTriangulation::simplifyToLocalMinimum().
*
* Currently this routine is only useful for triangulations whose
* faces are all internal; if the given triangulation has
* boundary faces then this routine will simply return \c true.
*
* \ifacespython Parameter \a ignore is not present.
*
* @param tri the triangulation to examine.
* @param ignore a parameter that is ignored.
* @return \c false if the given triangulation is known to be
* non-minimal, or \c true if minimality of the given
* triangulation has not been determined.
*/
static bool mightBeMinimal(NTriangulation* tri, void* ignore = 0);
private:
/**
* Creates a new structure to hold the given information.
* All parameters not explained are taken directly from
* formCensus().
*
* @param newProgress the object with which to report progress
* for the census generation, or 0 if progress reporting is not
* required.
*/
NCensus(NPacket* newParent, const NBoolSet& newFiniteness,
const NBoolSet& newOrientability, int newWhichPurge,
AcceptTriangulation newSieve, void* newSieveArgs,
NProgressMessage* newProgress);
/**
* Called when a particular tetrahedron face pairing has been
* found. This routine hooks up the face pairing generation with
* the gluing permutation generation.
*
* @param pairing the face pairing that has been found.
* @param autos the set of all automorphisms of the given face
* pairing.
* @param census the census currently being generated;
* this must really be of class NCensus.
*/
static void foundFacePairing(const NFacePairing* pairing,
const NFacePairingIsoList* autos, void* census);
/**
* Called when a particular set of gluing permutations has been
* found. This routine generates the corresponding triangulation
* and decides whether it really belongs in the census.
*
* \pre The given set of gluing permutations is complete, i.e.,
* it is not just a partially-complete search state. Partial
* searches are formed by calling NGluingPermSearcher::runSearch()
* with a non-negative depth argument.
*
* @param perms the gluing permutation set that has been found.
* @param census the census currently being generated;
* this must really be of class NCensus.
*/
static void foundGluingPerms(const NGluingPermSearcher* perms,
void* census);
};
/*@}*/
} // namespace regina
#endif
|
