1 /* PLUGIN file to use with plantri.c
2
3 To use this, compile plantri.c using
4 cc -o plantri_maxd -O4 '-DPLUGIN="maxdeg.c"' plantri.c
5
6 This plug-in deletes those triangulations whose maximum
7 degree is greater than maxdeg, which is normally 6 but can
8 be changed by using the -D switch, for example
9
10 plantri_maxd -D7 14
11
12 makes all triangulations with 14 vertices and maximum degree <= 7.
13
14 This plugin only works for 3-connected planar triangulations
15 and all varieties of quadrangulations.
16
17 For triangulations of maximum degree 6 there is a far more
18 sophisticated program available from the authors.
19 */
20
21 static int maxdeg = 6;
22
23 #define FILTER maxdeg_filter
24 #define PRE_FILTER_SIMPLE maxdeg_prune()
25 #define FIND_EXTENSIONS_QUAD find_extensions_quad_D
26 #define FIND_EXTENSIONS_QUAD_ALL find_extensions_quad_all_D
27 #define FIND_EXTENSIONS_QUAD_MIN3 find_extensions_quad_min3_D
28 #define FIND_EXTENSIONS_QUAD_NF4 find_extensions_quad_nf4_D
29
30 /*******************************************************************/
31
32 /* The following adds the switch D to those normally present.
33 and specifies a subset of the switches as permitted. */
34
35 #define PLUGIN_SWITCHES INTSWITCH('D',maxdeg)
36
37 #undef SWITCHES
38 #define SWITCHES "[-D# -qcm -uagsh -odG -v]"
39 #define HELPMESSAGE \
40 fprintf(stderr,"Specify the allowed maximum degree with -D#.\n")
41 #define PLUGIN_INIT \
42 if ((minconnec != 3 && minconnec >= 0 \
43 || minimumdeg != 3 && minimumdeg >= 0) && !qswitch) \
44 { \
45 fprintf(stderr,">E -c is only allowed with -q\n"); \
46 exit(1); \
47 }
48
49 /*********************************************************************/
50
51 static int
maxdeg_filter(int nbtot,int nbop,int doflip)52 maxdeg_filter(int nbtot, int nbop, int doflip)
53 {
54 register int i;
55
56 for (i = 0; i < nv; ++i)
57 if (degree[i] > maxdeg) return FALSE;
58
59 return TRUE;
60 }
61
62 /*********************************************************************
63 The following is used to prune the search tree at levels below maxnv.
64 Consider the expansion operations E3, E4, E5. The basic ideas are:
65 (1) Only E5 can reduce the degree of a vertex, then only by 1.
66 (2) If there are 3 or more vertices of degree 3, E5 will never be used.
67 (3) Similarly if there are 2 vertices of degree 3 but they don't have
68 two common neighbours.
69 (4) The quantity (2 * #degree-3 + #degree-4) is reduced by at most one
70 by E3 and E4. E5 can reduce it by 2 as long as it becomes 0. */
71
72 static int
commonedge(int a,int b)73 commonedge(int a, int b)
74 /* Test that vertices a,b of degree 3 are at the opposite
75 points of two adjacent faces */
76 {
77 EDGE *e;
78
79 e = firstedge[a];
80 if (e->invers->next->next->end == b) return TRUE;
81 e = e->next;
82 if (e->invers->next->next->end == b) return TRUE;
83 e = e->next;
84 if (e->invers->next->next->end == b) return TRUE;
85 return FALSE;
86 }
87
88 static int
maxdeg_prune()89 maxdeg_prune()
90 {
91 register int i,levs,excess,d3,d4;
92 int d3a,d3b;
93
94 levs = maxnv - nv; /* Number of expansions yet to perform */
95 excess = d3 = d4 = 0;
96
97 for (i = 0; i < nv; ++i)
98 {
99 if (degree[i] == 3)
100 {
101 ++d3;
102 d3a = d3b;
103 d3b = i;
104 }
105 else if (degree[i] == 4)
106 ++d4;
107 else if (degree[i] > maxdeg)
108 excess += degree[i] - maxdeg;
109 }
110
111 if (excess == 0) return TRUE;
112
113 if (d3 > 2) return FALSE;
114 if (d3 == 2 && !commonedge(d3a,d3b)) return FALSE;
115 if (d3 > 0 && excess >= levs) return FALSE;
116
117 i = d3 + d3 + d4;
118 if (i > 0 && excess > levs - i + 2) return FALSE;
119
120 return TRUE;
121 }
122
123 /*************************************************************************/
124
125 static void
126 find_extensions_quad(int,int,EDGE**,int*,EDGE**,int*,EDGE*);
127
128 static void
find_extensions_quad_D(int nbtot,int nbop,EDGE * extP1[],int * nextP1,EDGE * extP3[],int * nextP3,EDGE * lastP1)129 find_extensions_quad_D(int nbtot, int nbop, EDGE *extP1[], int *nextP1,
130 EDGE *extP3[], int *nextP3, EDGE *lastP1)
131 {
132 int i,excess,newP1,newP3;
133 EDGE *e;
134
135 find_extensions_quad(nbtot,nbop,extP1,nextP1,extP3,nextP3,lastP1);
136
137 excess = 0;
138 for (i = 0; i < nv; ++i)
139 if (degree[i] > maxdeg) excess += degree[i] - maxdeg;
140
141 if (excess > maxnv-nv)
142 {
143 *nextP1 = *nextP3 = 0;
144 return ;
145 }
146
147 if (excess == maxnv-nv) *nextP3 = 0;
148
149 newP1 = 0;
150 for (i = 0; i < *nextP1; ++i)
151 {
152 e = extP1[i];
153 if (excess - (degree[e->start]>maxdeg)
154 + (degree[e->prev->end]>=maxdeg)
155 + (degree[e->next->end]>=maxdeg) <= maxnv-nv-1)
156 extP1[newP1++] = e;
157 }
158 *nextP1 = newP1;
159
160 newP3 = 0;
161 for (i = 0; i < *nextP3; ++i)
162 {
163 e = extP3[i];
164 if (excess + (degree[e->start]>=maxdeg)
165 + (degree[e->end]>=maxdeg)
166 + (degree[e->next->end]>=maxdeg)
167 + (degree[e->invers->prev->end]>=maxdeg) <= maxnv-nv-1)
168 extP3[newP3++] = e;
169 }
170 *nextP3 = newP3;
171 }
172
173 static void
174 find_extensions_quad_all(int,int,EDGE**,int*,EDGE**,int*);
175
176 static void
find_extensions_quad_all_D(int nbtot,int nbop,EDGE * extP0[],int * nextP0,EDGE * extP1[],int * nextP1)177 find_extensions_quad_all_D(int nbtot, int nbop, EDGE *extP0[], int *nextP0,
178 EDGE *extP1[], int *nextP1)
179 {
180 int i,excess,newP0,newP1;
181 EDGE *e;
182
183 find_extensions_quad_all(nbtot,nbop,extP0,nextP0,extP1,nextP1);
184
185 excess = 0;
186 for (i = 0; i < nv; ++i)
187 if (degree[i] > maxdeg) excess += degree[i] - maxdeg;
188
189 if (excess > maxnv-nv)
190 {
191 *nextP0 = *nextP1 = 0;
192 return ;
193 }
194
195 if (excess == maxnv-nv) *nextP0 = 0;
196
197 newP1 = 0;
198 for (i = 0; i < *nextP1; ++i)
199 {
200 e = extP1[i];
201 if (excess - (degree[e->start]>maxdeg)
202 + (degree[e->prev->end]>=maxdeg)
203 + (degree[e->next->end]>=maxdeg) <= maxnv-nv-1)
204 extP1[newP1++] = e;
205 }
206 *nextP1 = newP1;
207
208 newP0 = 0;
209 for (i = 0; i < *nextP0; ++i)
210 {
211 e = extP0[i];
212 if (excess + (degree[e->end]>=maxdeg)
213 + (degree[e->next->end]>=maxdeg) <= maxnv-nv-1)
214 extP0[newP0++] = e;
215 }
216 *nextP0 = newP0;
217 }
218
219 static void
220 find_extensions_quad_min3(int,int,EDGE**,int*,EDGE**,int*,EDGE*);
221
222 static void
find_extensions_quad_min3_D(int nbtot,int nbop,EDGE * extP1[],int * nextP1,EDGE * extP3[],int * nextP3,EDGE * lastP1)223 find_extensions_quad_min3_D(int nbtot, int nbop, EDGE *extP1[], int *nextP1,
224 EDGE *extP3[], int *nextP3, EDGE *lastP1)
225 {
226 int i,excess,newP1,newP3;
227 EDGE *e;
228
229 find_extensions_quad_min3(nbtot,nbop,extP1,nextP1,extP3,nextP3,lastP1);
230
231 excess = 0;
232 for (i = 0; i < nv; ++i)
233 if (degree[i] > maxdeg) excess += degree[i] - maxdeg;
234
235 if (excess > maxnv-nv)
236 {
237 *nextP1 = *nextP3 = 0;
238 return ;
239 }
240
241 if (excess == maxnv-nv) *nextP3 = 0;
242
243 newP1 = 0;
244 for (i = 0; i < *nextP1; ++i)
245 {
246 e = extP1[i];
247 if (excess - (degree[e->start]>maxdeg)
248 + (degree[e->prev->end]>=maxdeg)
249 + (degree[e->next->end]>=maxdeg) <= maxnv-nv-1)
250 extP1[newP1++] = e;
251 }
252 *nextP1 = newP1;
253
254 newP3 = 0;
255 for (i = 0; i < *nextP3; ++i)
256 {
257 e = extP3[i];
258 if (excess + (degree[e->start]>=maxdeg)
259 + (degree[e->end]>=maxdeg)
260 + (degree[e->next->end]>=maxdeg)
261 + (degree[e->invers->prev->end]>=maxdeg) <= maxnv-nv-1)
262 extP3[newP3++] = e;
263 }
264 *nextP3 = newP3;
265 }
266
267 static void
268 find_extensions_quad_nf4(int,int,EDGE**,int*,EDGE*);
269
270 static void
find_extensions_quad_nf4_D(int nbtot,int nbop,EDGE * extP1[],int * nextP1,EDGE * lastP1)271 find_extensions_quad_nf4_D(int nbtot, int nbop, EDGE *extP1[], int *nextP1,
272 EDGE *lastP1)
273 {
274 int i,excess,newP1;
275 EDGE *e;
276
277 find_extensions_quad_nf4(nbtot,nbop,extP1,nextP1,lastP1);
278
279 excess = 0;
280 for (i = 0; i < nv; ++i)
281 if (degree[i] > maxdeg) excess += degree[i] - maxdeg;
282
283 if (excess > maxnv-nv)
284 {
285 *nextP1 = 0;
286 return ;
287 }
288
289 newP1 = 0;
290 for (i = 0; i < *nextP1; ++i)
291 {
292 e = extP1[i];
293 if (excess - (degree[e->start]>maxdeg)
294 + (degree[e->prev->end]>=maxdeg)
295 + (degree[e->next->end]>=maxdeg) <= maxnv-nv-1)
296 extP1[newP1++] = e;
297 }
298 *nextP1 = newP1;
299 }
300
301