-
Notifications
You must be signed in to change notification settings - Fork 9
/
Copy pathnautaux.c
252 lines (219 loc) · 8.67 KB
/
nautaux.c
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
/*****************************************************************************
* *
* Auxiliary procedures for use with nauty 2.5. *
* None of these procedures are needed by nauty or by dreadnaut. *
* *
* Copyright (1984-2013) Brendan McKay. All rights reserved. *
* Subject to waivers and disclaimers in nauty.h. *
* *
* CHANGE HISTORY *
* 26-Apr-89 : initial creation for Version 1.5. *
* 14-Oct-90 : renamed to version 1.6 (no changes to this file) *
* 5-Jun-93 : renamed to version 1.7+ (no changes to this file) *
* 18-Aug-93 : renamed to version 1.8 (no changes to this file) *
* 17-Sep-93 : renamed to version 1.9 (no changes to this file) *
* 24-Jan-00 : renamed to version 2.0 (no changes to this file) *
* 16-Nov-00 : made changes listed in nauty.h *
* 8-Aug-02 : updated for version 2.2 (dynamic storage) *
* 3-Nov-04 : fixed names of nautaux_freedyn() and nautaux_check() *
* 10-Dec-06 : removed BIGNAUTY *
* 10-Nov-09 : removed types permutation and shortish *
* 15-Jan-12 : add TLS_ATTR attributes *
* *
*****************************************************************************/
#define ONE_WORD_SETS
#include "naututil.h" /* which includes "nauty.h" and <stdio.h> */
#include "nautaux.h"
#if MAXM==1
#define M 1
#else
#define M m
#endif
#if !MAXN
DYNALLSTAT(set,workset,workset_sz);
DYNALLSTAT(int,workperm,workperm_sz);
#else
static TLS_ATTR set workset[MAXM]; /* used for scratch work */
static TLS_ATTR int workperm[MAXN+2];
#endif
/*****************************************************************************
* *
* ptncode(g,lab,ptn,level,m,n) returns a long integer invariant which *
* depends on the (assumed equitable) partition at the stated level, and *
* the number of edges betwen the various cells. *
* Neither nauty nor dreadnaut use this. *
* *
* GLOBALS ACCESSED: bit<r>,setinter() *
* *
*****************************************************************************/
long
ptncode(graph *g, int *lab, int *ptn, int level, int m, int n)
{
int i;
long code;
int v1,v2,nc,inter,cellend;
#if !MAXN
DYNALLOC1(int,workperm,workperm_sz,n+2,"testcanlab");
DYNALLOC1(set,workset,workset_sz,m,"testcanlab");
#endif
/* find all cells: put starts in workperm[0..n] */
i = nc = 0;
code = 0;
while (i < n)
{
workperm[nc++] = i;
code = ((code << 13) ^ (code >> 19)) + i;
while (ptn[i] > level) ++i;
++i;
}
workperm[nc] = n;
for (v2 = 0; v2 < nc; ++v2)
{
EMPTYSET(workset,m);
for (i = workperm[v2], cellend = workperm[v2+1] - 1;
i <= cellend; ++i)
ADDELEMENT(workset,lab[i]);
for (v1 = 0; v1 < nc; ++v1)
{
i = workperm[v1];
cellend = workperm[v1+1] - 1;
inter = setinter(workset,GRAPHROW(g,lab[i],M),M);
code = ((code << 13) ^ (code >> 19)) + inter;
}
}
return code;
}
/*****************************************************************************
* *
* equitable(g,lab,ptn,level,m,n) checks that the partition at the given *
* level is equitable. Neither nauty nor dreadnaut use this. *
* *
* GLOBALS ACCESSED: bit<r>,setinter() *
* *
*****************************************************************************/
boolean
equitable(graph *g, int *lab, int *ptn, int level, int m, int n)
{
int i;
int v1,v2,nc,inter,cellend;
boolean ok;
/* find all cells: put starts in workperm[0..n] */
#if !MAXN
DYNALLOC1(int,workperm,workperm_sz,n+2,"testcanlab");
DYNALLOC1(set,workset,workset_sz,m,"testcanlab");
#endif
i = nc = 0;
while (i < n)
{
workperm[nc++] = i;
while (ptn[i] > level)
++i;
++i;
}
workperm[nc] = n;
ok = TRUE;
for (v2 = 0; v2 < nc && ok; ++v2)
{
EMPTYSET(workset,m);
for (i = workperm[v2], cellend = workperm[v2+1] - 1;
i <= cellend; ++i)
ADDELEMENT(workset,lab[i]);
for (v1 = 0; v1 < nc; ++v1)
{
i = workperm[v1];
cellend = workperm[v1+1] - 1;
if (i == cellend)
continue;
inter = setinter(workset,GRAPHROW(g,lab[i],M),M);
while (++i <= cellend)
if (setinter(workset,GRAPHROW(g,lab[i],M),M) != inter)
ok = FALSE;
}
}
return ok;
}
/*****************************************************************************
* *
* component(g,v,c,m,n) determines the set of all vertices that can be *
* reached along directed paths starting at vertex v, including v itself. *
* This set is returned as c, unless c is null. The size of the set is *
* returned as the function value. *
* *
* GLOBALS ACCESSED: bit<r>,setinter(),nextelement() *
* *
*****************************************************************************/
int
component(graph *g, int v, set *cmpt, int m, int n)
{
int i,z;
set newverts[MAXM],*gx;
int head,tail,x;
#if !MAXN
DYNALLOC1(int,workperm,workperm_sz,n+2,"testcanlab");
#endif
EMPTYSET(workset,m);
ADDELEMENT(workset,v);
head = 0;
tail = 1;
workperm[head] = v;
while (head < tail && tail < n)
{
x = workperm[head++];
gx = GRAPHROW(g,x,m);
for (i = m; --i >= 0;)
{
newverts[i] = gx[i] & ~workset[i];
workset[i] |= gx[i];
}
for (z = -1; (z = nextelement(newverts,m,z)) >= 0; )
workperm[tail++] = z;
}
if (cmpt != NULL)
for (i = m; --i >= 0;) cmpt[i] = workset[i];
return tail;
}
/*****************************************************************************
* *
* nautaux_check() checks that this file is compiled compatibly with the *
* given parameters. If not, call exit(1). *
* *
*****************************************************************************/
void
nautaux_check(int wordsize, int m, int n, int version)
{
if (wordsize != WORDSIZE)
{
fprintf(ERRFILE,"Error: WORDSIZE mismatch in nautaux.c\n");
exit(1);
}
#if MAXN
if (m > MAXM)
{
fprintf(ERRFILE,"Error: MAXM inadequate in nautaux.c\n");
exit(1);
}
if (n > MAXN)
{
fprintf(ERRFILE,"Error: MAXN inadequate in nautaux.c\n");
exit(1);
}
#endif
if (version < NAUTYREQUIRED)
{
fprintf(ERRFILE,"Error: nautaux.c version mismatch\n");
exit(1);
}
}
/*****************************************************************************
* *
* nautaux_freedyn() - free the dynamic memory in this module *
* *
*****************************************************************************/
void
nautaux_freedyn(void)
{
#if !MAXN
DYNFREE(workset,workset_sz);
DYNFREE(workperm,workperm_sz);
#endif
}