1 /*****************************************************************************
2 * *
3 * Auxiliary procedures for use with nauty 2.2. *
4 * None of these procedures are needed by nauty or by dreadnaut. *
5 * *
6 * Copyright (1984-2002) Brendan McKay. All rights reserved. *
7 * Subject to waivers and disclaimers in nauty.h. *
8 * *
9 * CHANGE HISTORY *
10 * 26-Apr-89 : initial creation for Version 1.5. *
11 * 14-Oct-90 : renamed to version 1.6 (no changes to this file) *
12 * 5-Jun-93 : renamed to version 1.7+ (no changes to this file) *
13 * 18-Aug-93 : renamed to version 1.8 (no changes to this file) *
14 * 17-Sep-93 : renamed to version 1.9 (no changes to this file) *
15 * 24-Jan-00 : renamed to version 2.0 (no changes to this file) *
16 * 16-Nov-00 : made changes listed in nauty.h *
17 * 8-Aug-02 : updated for version 2.2 (dynamic storage) *
18 * *
19 *****************************************************************************/
20
21 #define ONE_WORD_SETS
22 #include "naututil.h" /* which includes "nauty.h" and <stdio.h> */
23 #include "nautaux.h"
24
25 #if MAXM==1
26 #define M 1
27 #else
28 #define M m
29 #endif
30
31 #if !MAXN
32 DYNALLSTAT(set,workset,workset_sz);
33 DYNALLSTAT(permutation,workperm,workperm_sz);
34 #else
35 static set workset[MAXM]; /* used for scratch work */
36 static permutation workperm[MAXN+2];
37 #endif
38
39 /*****************************************************************************
40 * *
41 * ptncode(g,lab,ptn,level,m,n) returns a long integer invariant which *
42 * depends on the (assumed equitable) partition at the stated level, and *
43 * the number of edges betwen the various cells. *
44 * Neither nauty nor dreadnaut use this. *
45 * *
46 * GLOBALS ACCESSED: bit<r>,setinter() *
47 * *
48 *****************************************************************************/
49
50 long
ptncode(graph * g,int * lab,int * ptn,int level,int m,int n)51 ptncode(graph *g, int *lab, int *ptn, int level, int m, int n)
52 {
53 register int i;
54 register long code;
55 int v1,v2,nc,inter,cellend;
56
57 #if !MAXN
58 DYNALLOC1(permutation,workperm,workperm_sz,n+2,"testcanlab");
59 DYNALLOC1(set,workset,workset_sz,m,"testcanlab");
60 #endif
61
62 /* find all cells: put starts in workperm[0..n] */
63
64 i = nc = 0;
65 code = 0;
66
67 while (i < n)
68 {
69 workperm[nc++] = i;
70 code = ((code << 13) ^ (code >> 19)) + i;
71 while (ptn[i] > level)
72 ++i;
73 ++i;
74 }
75 workperm[nc] = n;
76
77 for (v2 = 0; v2 < nc; ++v2)
78 {
79 EMPTYSET(workset,m);
80 for (i = workperm[v2], cellend = workperm[v2+1] - 1;
81 i <= cellend; ++i)
82 ADDELEMENT(workset,lab[i]);
83 for (v1 = 0; v1 < nc; ++v1)
84 {
85 i = workperm[v1];
86 cellend = workperm[v1+1] - 1;
87 inter = setinter(workset,GRAPHROW(g,lab[i],M),M);
88 code = ((code << 13) ^ (code >> 19)) + inter;
89 }
90 }
91
92 return(code);
93 }
94
95 /*****************************************************************************
96 * *
97 * equitable(g,lab,ptn,level,m,n) checks that the partition at the given *
98 * level is equitable. Neither nauty nor dreadnaut use this. *
99 * *
100 * GLOBALS ACCESSED: bit<r>,setinter() *
101 * *
102 *****************************************************************************/
103
104 boolean
equitable(graph * g,int * lab,int * ptn,int level,int m,int n)105 equitable(graph *g, int *lab, int *ptn, int level, int m, int n)
106 {
107 register int i;
108 int v1,v2,nc,inter,cellend;
109 boolean ok;
110
111 /* find all cells: put starts in workperm[0..n] */
112
113 #if !MAXN
114 DYNALLOC1(permutation,workperm,workperm_sz,n+2,"testcanlab");
115 DYNALLOC1(set,workset,workset_sz,m,"testcanlab");
116 #endif
117
118 i = nc = 0;
119
120 while (i < n)
121 {
122 workperm[nc++] = i;
123 while (ptn[i] > level)
124 ++i;
125 ++i;
126 }
127 workperm[nc] = n;
128
129 ok = TRUE;
130 for (v2 = 0; v2 < nc; ++v2)
131 {
132 EMPTYSET(workset,m);
133 for (i = workperm[v2], cellend = workperm[v2+1] - 1;
134 i <= cellend; ++i)
135 ADDELEMENT(workset,lab[i]);
136 for (v1 = 0; v1 < nc; ++v1)
137 {
138 i = workperm[v1];
139 cellend = workperm[v1+1] - 1;
140 if (i == cellend)
141 continue;
142 inter = setinter(workset,GRAPHROW(g,lab[i],M),M);
143 while (++i <= cellend)
144 if (setinter(workset,GRAPHROW(g,lab[i],M),M) != inter)
145 ok = FALSE;
146 }
147 }
148
149 return(ok);
150 }
151
152 /*****************************************************************************
153 * *
154 * component(g,v,c,m,n) determines the set of all vertices that can be *
155 * reached along directed paths starting at vertex v, including v itself. *
156 * This set is returned as c, unless c is null. The size of the set is *
157 * returned as the function value. *
158 * *
159 * GLOBALS ACCESSED: bit<r>,setinter(),nextelement() *
160 * *
161 *****************************************************************************/
162
163 int
component(graph * g,int v,set * cmpt,int m,int n)164 component(graph *g, int v, set *cmpt, int m, int n)
165 {
166 register int i,z;
167 set newverts[MAXM],*gx;
168 int head,tail,x;
169
170 #if !MAXN
171 DYNALLOC1(permutation,workperm,workperm_sz,n+2,"testcanlab");
172 #endif
173
174 EMPTYSET(workset,m);
175 ADDELEMENT(workset,v);
176 head = 0;
177 tail = 1;
178 workperm[head] = v;
179
180 while (head < tail && tail < n)
181 {
182 x = workperm[head++];
183 gx = GRAPHROW(g,x,m);
184 for (i = m; --i >= 0;)
185 {
186 newverts[i] = gx[i] & ~workset[i];
187 workset[i] |= gx[i];
188 }
189 for (z = -1; (z = nextelement(newverts,m,z)) >= 0; )
190 workperm[tail++] = z;
191 }
192
193 if (cmpt != NULL)
194 for (i = m; --i >= 0;) cmpt[i] = workset[i];
195
196 return(tail);
197 }
198
199 /*****************************************************************************
200 * *
201 * nautyaux_check() checks that this file is compiled compatibly with the *
202 * given parameters. If not, call exit(1). *
203 * *
204 *****************************************************************************/
205
206 void
nautyaux_check(int wordsize,int m,int n,int version)207 nautyaux_check(int wordsize, int m, int n, int version)
208 {
209 if (wordsize != WORDSIZE)
210 {
211 fprintf(ERRFILE,"Error: WORDSIZE mismatch in nautyaux.c\n");
212 exit(1);
213 }
214
215 #if MAXN
216 if (m > MAXM)
217 {
218 fprintf(ERRFILE,"Error: MAXM inadequate in nautyaux.c\n");
219 exit(1);
220 }
221
222 if (n > MAXN)
223 {
224 fprintf(ERRFILE,"Error: MAXN inadequate in nautyaux.c\n");
225 exit(1);
226 }
227 #endif
228
229 #ifdef BIGNAUTY
230 if ((version & 1) == 0)
231 {
232 fprintf(ERRFILE,"Error: BIGNAUTY mismatch in nautyaux.c\n");
233 exit(1);
234 }
235 #else
236 if ((version & 1) == 1)
237 {
238 fprintf(ERRFILE,"Error: BIGNAUTY mismatch in nautyaux.c\n");
239 exit(1);
240 }
241 #endif
242
243 if (version < NAUTYREQUIRED)
244 {
245 fprintf(ERRFILE,"Error: nautyaux.c version mismatch\n");
246 exit(1);
247 }
248 }
249
250 /*****************************************************************************
251 * *
252 * nautyaux_freedyn() - free the dynamic memory in this module *
253 * *
254 *****************************************************************************/
255
256 void
naugraph_freedyn(void)257 naugraph_freedyn(void)
258 {
259 #if !MAXN
260 DYNFREE(workset,workset_sz);
261 DYNFREE(workperm,workperm_sz);
262 #endif
263 }
264