1 /* assembleg.c version 1.1; B D McKay, Sep 2018. */
2
3 #define USAGE "assembleg -n#|-n#:# [-i#|i#:#] [-L] [-q] [infile [outfile]]"
4
5 #define HELPTEXT \
6 " Assemble input graphs as components of output graphs.\n\
7 \n\
8 The output file has no header.\n\
9 If the input has any directed graphs, all outputs are directed.\n\
10 Otherwise, the output format is determined by the header\n\
11 or first input.\n\
12 The input graphs had better all fit into memory at once,\n\
13 unless -L is given, in which case only the graphs of at\n\
14 most half the output size are stored at once.\n\
15 The output graphs will be non-isomorphic if the input\n\
16 graphs are connected and non-isomorphic.\n\
17 \n\
18 -n# -n#:# Give range of output sizes (compulsory)\n\
19 -i# -i#:# Give range of input sizes to use\n\
20 -L Assume all input graphs strictly larger than maxn/2\n\
21 vertices follow any smaller graphs in the input,\n\
22 where maxn is the largest size specified by -n.\n\
23 This can greatly reduce memory consumption.\n\
24 -c Also write graphs consisting of a single input\n\
25 -q Suppress auxiliary information.\n"
26
27 /*************************************************************************/
28
29 #include "gtools.h"
30
31 static int ninputs; /* Number of inputs */
32 static unsigned long nout; /* Number of outputs */
33 typedef graph *graphptr;
34 static graphptr *gin; /* Their contents */
35 static int *size; /* Their sizes */
36 static int outcode;
37
38 /**************************************************************************/
39
40 static void
insertg(graph * g,int ng,graph * h,int nh,int n)41 insertg(graph *g, int ng, graph *h, int nh, int n)
42 /* Insert nh-vertex graph starting at vertex ng in graph g.
43 n is the total size available.
44 It is assumed that g is empty apart from 0..ng-1. */
45 {
46 int i,j,m,mh;
47 set *gi,*hi;
48
49 m = SETWORDSNEEDED(n);
50 mh = SETWORDSNEEDED(nh);
51
52 for (i = 0, hi = h, gi = g + ng*m; i < nh;
53 ++i, hi += mh, gi += m)
54 {
55 for (j = -1; (j = nextelement(hi,mh,j)) >= 0; )
56 ADDELEMENT(gi,ng+j);
57 }
58 }
59
60 static void
removeg(graph * g,int ng,int nh,int n)61 removeg(graph *g, int ng, int nh, int n)
62 /* Remove a subgraph that was in position ng..ng+nh-1. */
63 {
64 set *gi;
65 int i,j,m;
66
67 m = SETWORDSNEEDED(n);
68
69 for (i = ng, gi = g + ng*m; i < ng+nh; ++i, gi += m)
70 {
71 for (j = ng; j < ng+nh; ++j)
72 DELELEMENT(gi,j);
73 }
74 }
75
76 /**************************************************************************/
77
78 #define SORT_NAME sortbysize
79 #define SORT_OF_SORT 2
80 #define SORT_TYPE1 int
81 #define SORT_TYPE2 graphptr
82 #include "sorttemplates.c"
83
84 static void
readinputs(FILE * f,int imin,int imax)85 readinputs(FILE *f, int imin, int imax)
86 /* Read inputs and sort by size */
87 {
88 size_t tablesize;
89 graph *g;
90 int m,n;
91 boolean digraph;
92
93 if ((gin = malloc(sizeof(graphptr)*10000)) == NULL ||
94 (size = malloc(sizeof(int)*10000)) == NULL)
95 gt_abort(">E malloc failed in readinputs()\n");
96 tablesize = 10000;
97
98 ninputs = 0;
99
100 while (TRUE)
101 {
102 if ((g = readgg(f,NULL,0,&m,&n,&digraph)) == NULL) break;
103 if (digraph) outcode = DIGRAPH6;
104 if (n < imin || n > imax) continue;
105
106 if (ninputs == tablesize)
107 {
108 tablesize += 10000;
109 if ((gin = realloc(gin,sizeof(graphptr)*tablesize)) == NULL ||
110 (size = realloc(size,sizeof(int)*tablesize)) == NULL)
111 gt_abort(">E realloc failed in readinputs()\n");
112 }
113
114 gin[ninputs] = g;
115 size[ninputs] = n;
116 ++ninputs;
117 }
118
119 if (ninputs < 0 || ninputs > tablesize)
120 gt_abort(">E Some overflow problem in readinputs()\n");
121
122 sortbysize(size,gin,ninputs);
123 }
124
125 static void
readsomeinputs(FILE * f,int imin,int imax,int maxsize,graph ** g,int * n)126 readsomeinputs(FILE *f, int imin, int imax, int maxsize,
127 graph **g, int *n)
128 /* Read inputs and sort by size. Stop when either EOF or a
129 graph bigger than maxsize is read. */
130 {
131 size_t tablesize;
132 int m;
133 boolean digraph;
134
135 if ((gin = malloc(sizeof(graphptr)*10000)) == NULL ||
136 (size = malloc(sizeof(int)*10000)) == NULL)
137 gt_abort(">E malloc failed in readsomeinputs()\n");
138 tablesize = 10000;
139
140 ninputs = 0;
141
142 while (TRUE)
143 {
144 if ((*g = readgg(f,NULL,0,&m,n,&digraph)) == NULL) break;
145 if (digraph) outcode = DIGRAPH6;
146 if (*n > maxsize) break;
147
148 if (*n < imin || *n > imax) continue;
149
150 if (ninputs == tablesize)
151 {
152 tablesize += 10000;
153 if ((gin = realloc(gin,sizeof(graphptr)*tablesize)) == NULL ||
154 (size = realloc(size,sizeof(int)*tablesize)) == NULL)
155 gt_abort(">E realloc failed in readsomeinputs()\n");
156 }
157
158 gin[ninputs] = *g;
159 size[ninputs] = *n;
160 ++ninputs;
161 }
162
163 if (ninputs < 0 || ninputs > tablesize)
164 gt_abort(">E Some overflow problem in readinputs()\n");
165
166 sortbysize(size,gin,ninputs);
167 }
168
169 /**************************************************************************/
170
171 static void
assemble(graph * g,int nmin,int nmax,int sofar,int lastpos,boolean writeconn,FILE * outfile)172 assemble(graph *g, int nmin, int nmax, int sofar, int lastpos,
173 boolean writeconn, FILE *outfile)
174 /* Recursively add one more graph.
175 sofar = how many vertices so far. */
176 {
177 int pos,newsize;
178
179 for (pos = lastpos; pos < ninputs; ++pos)
180 {
181 newsize = sofar + size[pos];
182 if (newsize > nmax) break;
183
184 insertg(g,sofar,gin[pos],size[pos],nmax);
185 if (newsize >= nmin && (sofar > 0 || writeconn))
186 {
187 if (outcode == DIGRAPH6)
188 writed6(outfile,g,SETWORDSNEEDED(nmax),newsize);
189 else if (outcode == GRAPH6)
190 writeg6(outfile,g,SETWORDSNEEDED(nmax),newsize);
191 else
192 writes6(outfile,g,SETWORDSNEEDED(nmax),newsize);
193 ++nout;
194 }
195 assemble(g,nmin,nmax,newsize,pos,writeconn,outfile);
196 removeg(g,sofar,size[pos],nmax);
197 }
198 }
199
200 /**************************************************************************/
201
202 int
main(int argc,char * argv[])203 main(int argc, char *argv[])
204 {
205 char *infilename,*outfilename;
206 FILE *infile,*outfile;
207 boolean badargs,quiet;
208 boolean nswitch,cswitch,iswitch,Lswitch;
209 boolean digraph;
210 int j,m,n,argnum;
211 int codetype;
212 graph *gread,*gout;
213 nauty_counter nin;
214 char *arg,sw;
215 double t;
216 long nmin,nmax,mmax,imin,imax;
217
218 HELP; PUTVERSION;
219
220 infilename = outfilename = NULL;
221 badargs = FALSE;
222 iswitch = nswitch = cswitch = quiet = Lswitch = FALSE;
223
224 argnum = 0;
225 badargs = FALSE;
226 for (j = 1; !badargs && j < argc; ++j)
227 {
228 arg = argv[j];
229 if (arg[0] == '-' && arg[1] != '\0')
230 {
231 ++arg;
232 while (*arg != '\0')
233 {
234 sw = *arg++;
235 SWBOOLEAN('q',quiet)
236 else SWBOOLEAN('c',cswitch)
237 else SWBOOLEAN('L',Lswitch)
238 else SWRANGE('n',":-",nswitch,nmin,nmax,"assembleg -n")
239 else SWRANGE('i',":-",iswitch,imin,imax,"assembleg -i")
240 else badargs = TRUE;
241 }
242 }
243 else
244 {
245 ++argnum;
246 if (argnum == 1) infilename = arg;
247 else if (argnum == 2) outfilename = arg;
248 else badargs = TRUE;
249 }
250 }
251
252 if (!nswitch) gt_abort(">E assembleg: -n is compulsory\n");
253
254 if (badargs)
255 {
256 fprintf(stderr,">E Usage: %s\n",USAGE);
257 GETHELP;
258 exit(1);
259 }
260
261 if (nmin <= 0) nmin = 1;
262 if (nmin > NAUTY_INFINITY-2) nmin = NAUTY_INFINITY-2;
263
264 if (!quiet)
265 {
266 fprintf(stderr,">A assembleg -");
267 if (nmin == nmax) fprintf(stderr,"n%ld",nmin);
268 else fprintf(stderr,"n%ld:%ld",nmin,nmax);
269 if (iswitch)
270 {
271 if (imin == imax) fprintf(stderr,"i%ld",imin);
272 else fprintf(stderr,"i%ld:%ld",imin,imax);
273 }
274 if (cswitch) fprintf(stderr,"c");
275 if (Lswitch) fprintf(stderr,"L");
276 if (argnum > 0) fprintf(stderr," %s",infilename);
277 if (argnum > 1) fprintf(stderr," %s",outfilename);
278 fprintf(stderr,"\n");
279 fflush(stderr);
280 }
281
282 if (!iswitch || imin <= 0) imin = 1;
283 if (!iswitch || imax > nmax) imax = nmax;
284 if (!cswitch && imax == nmax) --imax;
285
286 if (infilename && infilename[0] == '-') infilename = NULL;
287 infile = opengraphfile(infilename,&codetype,FALSE,1);
288 if (!infile) exit(1);
289 if (!infilename) infilename = "stdin";
290
291 if (!outfilename || outfilename[0] == '-')
292 {
293 outfilename = "stdout";
294 outfile = stdout;
295 }
296 else if ((outfile = fopen(outfilename,"w")) == NULL)
297 {
298 fprintf(stderr,"Can't open output file %s\n",outfilename);
299 gt_abort(NULL);
300 }
301
302 if (codetype&SPARSE6) outcode = SPARSE6;
303 else if (codetype&DIGRAPH6) outcode = DIGRAPH6;
304 else outcode = GRAPH6;
305
306 gtools_check(WORDSIZE,1,1,NAUTYVERSIONID);
307
308 t = CPUTIME;
309
310 mmax = SETWORDSNEEDED(nmax);
311
312 if ((gout = malloc(mmax*sizeof(graph)*nmax)) == NULL)
313 gt_abort(">E assembleg: malloc() failed in main()\n");
314
315
316 nout = 0;
317
318 if (Lswitch)
319 {
320 readsomeinputs(infile,(int)imin,(int)imax,(int)nmax/2,&gread,&n);
321
322 EMPTYSET(gout,m*(size_t)nmax);
323 assemble(gout,(int)nmin,(int)nmax,0,0,cswitch,outfile);
324
325 while (gread)
326 {
327 if (n >= imin && n <= imax)
328 {
329 EMPTYSET(gout,mmax*(size_t)nmax);
330 insertg(gout,0,gread,n,(int)nmax);
331
332 if (n >= nmin && n <= nmax && cswitch)
333 {
334 if (outcode == DIGRAPH6)
335 writed6(outfile,gout,mmax,n);
336 else if (outcode == GRAPH6)
337 writeg6(outfile,gout,mmax,n);
338 else
339 writes6(outfile,gout,mmax,n);
340 ++nout;
341 }
342
343 assemble(gout,(int)nmin,(int)nmax,n,0,cswitch,outfile);
344 }
345 FREES(gread);
346
347 if ((gread = readgg(infile,NULL,0,&m,&n,&digraph)) == NULL) break;
348 if (digraph) outcode = DIGRAPH6;
349 if (n <= nmax/2) gt_abort(">E assembleg -L : inputs in bad order\n");
350 }
351 }
352 else
353 {
354 readinputs(infile,(int)imin,(int)imax);
355
356 EMPTYSET(gout,m*(size_t)nmax);
357 assemble(gout,(int)nmin,(int)nmax,0,0,cswitch,outfile);
358 }
359
360 t = CPUTIME - t;
361
362 if (!quiet)
363 fprintf(stderr,">Z %d graphs read from %s; " COUNTER_FMT
364 " graphs written to %s in %3.2f sec.\n",
365 ninputs,infilename,nout,outfilename,t);
366
367 exit(0);
368 }
369