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
|
/**************************************************************************
* *
* 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 split/nsigisomorphism.h
* \brief Deals with full and partial isomorphisms of splitting surface
* signatures.
*/
#ifndef __NSIGISOMORPHISM_H
#ifndef __DOXYGEN
#define __NSIGISOMORPHISM_H
#endif
#include "regina-core.h"
#include "split/nsignature.h"
namespace regina {
/**
* \weakgroup split
* @{
*/
/**
* Represents a partial isomorphism between two splitting surface
* signatures. See class NSignature for details on splitting surface
* signatures.
*
* The two signatures related by this partial isomorphism must have the
* same cycle structure, i.e., the same number of cycle groups and the
* same cycle length and number of cycles within each cycle group.
*
* The partial isomorphism maps symbols to symbols and cycles to cycles,
* with the option of rotating some cycles and/or reversing all cycles in
* the process.
* Cycles within the <i>k</i>th cycle group of the source signature
* must map to cycles within the <i>k</i>th cycle group of the
* destination signature.
*
* A \e partial isomorphism is only required to map the cycles
* and symbols found in the first <i>g</i> cycle groups of the
* source isomorphism (for some <i>g</i>). If only a subset of symbols
* are mapped, that subset must be symbols 0,1,...,<i>k</i> for some <i>k</i>.
*
* \ifacespython Not present.
*/
class REGINA_API NSigPartialIsomorphism {
private:
unsigned nLabels;
/**< The number of symbols whose images are defined. */
unsigned nCycles;
/**< The number of cycles whose images are defined. */
unsigned* labelImage;
/**< Stores the image of each symbol. */
unsigned* cyclePreImage;
/**< Stores the preimage of each cycle. */
unsigned* cycleStart;
/**< Allows a cycle to be rotated: <tt>cycleStart[k]</tt> is
the position in original cycle \a k where the image
cycle begins. */
int dir;
/**< Positive if all cycles keep their original direction,
negative if all cycles are reversed. */
public:
/**
* Creates a new partial isomorphism that maps no cycles or
* symbols. This empty isomorphism is designed to be extended
* at some later point.
*
* @param newDir positive if this isomorphism specifies that all
* cycles are reversed, or negative if this isomorphism specifies
* that all cycles keep their original direction.
*/
NSigPartialIsomorphism(int newDir);
/**
* Creates a new partial isomorphism that is a clone of the given
* partial isomorphism.
*
* @param iso the partial isomorphism to clone.
*/
NSigPartialIsomorphism(const NSigPartialIsomorphism& iso);
/**
* Destroys this partial isomorphism.
*/
~NSigPartialIsomorphism();
/**
* Rearranges the cycle images so that this isomorphism when
* applied to the given signature produces a new signature that
* is in canonical form.
*
* The result of this routine is dependent upon the symbol map
* defined by this isomorphism (this symbol map will not be changed).
*
* @param sig the signature to which this isomorphism will be applied.
* @param fromCycleGroup the first cycle group whose images may
* be rearranged. If it is already known that the cycle images for
* the first \a k cycle groups are correct, \a k should be passed
* in this parameter. This parameter should not exceed the
* number of cycle groups whose cycles are mapped by this partial
* isomorphism.
*/
void makeCanonical(const NSignature& sig, unsigned fromCycleGroup = 0);
/**
* Lexicographically compares the results of applying this and
* the given isomorphism to the given signature.
*
* Comparisons are done on a cycle-by-cycle basis; comparisons
* within a cycle are done as described by NSignature::cycleCmp().
* Comparison will not proceed beyond the cycles mapped by this
* partial isomorphism.
*
* \pre the given partial isomorphism maps at least as many
* cycles and symbols as this partial isomorphism.
*
* @param sig the signature to which both this and the given
* isomorphism will be applied.
* @param other the isomorphism to compare with this isomorphism.
* @param fromCycleGroup the first cycle group whose images should
* be examined. If it is already known that the cycle images for
* the first \a k cycle groups are identical under both
* isomorphisms, \a k should be passed in this parameter.
* This parameter should not exceed the number of cycle groups
* whose cycles are mapped by this partial isomorphism.
*
* @return -1, 1 or 0 if the image of the given signature under
* this isomorphism is lexicographically less than, greater than
* or equal to its image under the given isomorphism respectively.
*/
int compareWith(const NSignature& sig,
const NSigPartialIsomorphism* other,
unsigned fromCycleGroup = 0) const;
private:
/**
* Creates a new partial isomorphism that is an extension of the
* given partial isomorphism.
*
* The portion of the new isomorphism matching the given isomorphism
* will be initialised; the remainder of the new isomorphism will
* remain uninitialised.
*
* @param base the partial isomorphism to be extended.
* @param newLabels the number of symbols that the new
* isomorphism will map; this must be at least as large as the
* number of symbols mapped by the given isomorphism.
* @param newCycles the number of cycles that the new
* isomorphism will map; this must be at least as large as the
* number of cycles mapped by the given isomorphism.
*/
NSigPartialIsomorphism(const NSigPartialIsomorphism& base,
unsigned newLabels, unsigned newCycles);
/**
* A comparison function for use with the Standard Template
* Library.
*
* This function determines whether the image of one cycle is
* less than the image of another under the given fixed isomorphism
* when applied to the given fixed signature. Cycle comparison is
* done using NSignature::cycleCmp().
*
* It is irrelevant which cycle is mapped to appear before the other
* in the sequence of cycles belonging to the image signature.
*/
struct ShorterCycle {
const NSignature& sig;
/**< The signature containing the cycles to examine. */
const NSigPartialIsomorphism& iso;
/**< The isomorphism to apply to the cycles before they
are compared. */
/**
* Creates a new comparison function.
*
* @param newSig the signature containing the cycles that
* this function will examine.
* @param newIso the partial isomorphism to apply to the cycles
* before they are compared.
*/
ShorterCycle(const NSignature& newSig,
const NSigPartialIsomorphism& newIso);
/**
* Determines whether the image of one cycle is
* lexicographically less than the image of another.
* See the class notes for further details on how this
* comparison is done.
*
* @param cycle1 the index of the first cycle to examine;
* this must be less than the total number of cycles mapped
* by the isomorphism concerned and less than the total number
* of cycles in the signature concerned.
* @param cycle2 the index of the second cycle to examine;
* this must be less than the total number of cycles mapped
* by the isomorphism concerned and less than the total number
* of cycles in the signature concerned.
* @return \c true if and only if the image of the first
* cycle is less than the image of the second cycle.
*/
bool operator () (unsigned cycle1, unsigned cycle2) const;
};
friend struct NSigPartialIsomorphism::ShorterCycle;
friend class regina::NSigCensus;
};
/*@}*/
// Inline functions for NSigPartialIsomorphism
inline NSigPartialIsomorphism::NSigPartialIsomorphism(int newDir) : nLabels(0),
nCycles(0), labelImage(0), cyclePreImage(0), cycleStart(0),
dir(newDir) {
}
inline NSigPartialIsomorphism::~NSigPartialIsomorphism() {
if (labelImage) delete[] labelImage;
if (cyclePreImage) delete[] cyclePreImage;
if (cycleStart) delete[] cycleStart;
}
inline NSigPartialIsomorphism::ShorterCycle::ShorterCycle(
const NSignature& newSig, const NSigPartialIsomorphism& newIso) :
sig(newSig), iso(newIso) {
}
inline bool NSigPartialIsomorphism::ShorterCycle::operator ()
(unsigned cycle1, unsigned cycle2) const {
return (NSignature::cycleCmp(sig, cycle1, iso.cycleStart[cycle1],
iso.dir, iso.labelImage, sig, cycle2, iso.cycleStart[cycle2],
iso.dir, iso.labelImage) < 0);
}
} // namespace regina
#endif
|
