1 /* complg.c version 2.0; B D McKay, Jun 2015. */
2
3 #define USAGE "complg [-lq] [-a] [-L] [-r|-R] [infile [outfile]]"
4
5 #define HELPTEXT \
6 " Take the complements of a file of graphs.\n\
7 \n\
8 The output file has a header if and only if the input file does.\n\
9 The output format is defined by the header or first graph.\n\
10 \n\
11 -r Only complement if the complement has fewer directed edges.\n\
12 -R Only complement if the complement has fewer directed edges\n\
13 or has the same number of directed edges and is canonically\n\
14 less than the original.\n\
15 -a Also output the input graph (before the complement).\n\
16 -L Complement the loops too. By default, preserve them.\n\
17 -l Canonically label outputs.\n\
18 -q Suppress auxiliary information.\n"
19
20 /*************************************************************************/
21
22 #include "gtools.h"
23
24 /**************************************************************************/
25
26 static void
compl(graph * g,int m,int n,graph * h,boolean comploops)27 compl(graph *g, int m, int n, graph *h, boolean comploops)
28 /* h := complement of g */
29 {
30 int i,j;
31 setword *gi,*hi;
32 #if MAXN
33 set all[MAXM];
34 #else
35 DYNALLSTAT(set,all,all_sz);
36 DYNALLOC1(set,all,all_sz,m,"complg");
37 #endif
38
39 EMPTYSET(all,m);
40 for (i = 0; i < n; ++i) ADDELEMENT(all,i);
41
42 gi = (setword*) g;
43 hi = (setword*) h;
44
45 for (i = 0; i < n; ++i)
46 {
47 for (j = 0; j < m; ++j) hi[j] = gi[j] ^ all[j];
48 if (!comploops) FLIPELEMENT(hi,i);
49 gi += m;
50 hi += m;
51 }
52 }
53
54 /**************************************************************************/
55
56 int
main(int argc,char * argv[])57 main(int argc, char *argv[])
58 {
59 char *infilename,*outfilename;
60 FILE *infile,*outfile;
61 boolean also,dolabel,badargs,restricted,Restricted,quiet;
62 boolean digraph,Lswitch;
63 int j,m,n,argnum;
64 int codetype,outcode;
65 graph *g;
66 size_t ii,ned,nedc,nn,loops,loopsc,gwords;
67 nauty_counter nin;
68 char *arg,sw;
69 static graph *gq;
70 double t;
71 #if MAXN
72 graph gc[MAXN*MAXM],h[MAXN*MAXM],hc[MAXN*MAXM];
73 #else
74 DYNALLSTAT(graph,gc,gc_sz);
75 DYNALLSTAT(graph,h,h_sz);
76 DYNALLSTAT(graph,hc,hc_sz);
77 #endif
78
79 HELP; PUTVERSION;
80
81 infilename = outfilename = NULL;
82 dolabel = badargs = also = FALSE;
83 restricted = Restricted = quiet = Lswitch = FALSE;
84
85 argnum = 0;
86 badargs = FALSE;
87 for (j = 1; !badargs && j < argc; ++j)
88 {
89 arg = argv[j];
90 if (arg[0] == '-' && arg[1] != '\0')
91 {
92 ++arg;
93 while (*arg != '\0')
94 {
95 sw = *arg++;
96 SWBOOLEAN('r',restricted)
97 else SWBOOLEAN('R',Restricted)
98 else SWBOOLEAN('l',dolabel)
99 else SWBOOLEAN('L',Lswitch)
100 else SWBOOLEAN('a',also)
101 else SWBOOLEAN('q',quiet)
102 else badargs = TRUE;
103 }
104 }
105 else
106 {
107 ++argnum;
108 if (argnum == 1) infilename = arg;
109 else if (argnum == 2) outfilename = arg;
110 else badargs = TRUE;
111 }
112 }
113
114 if (badargs)
115 {
116 fprintf(stderr,">E Usage: %s\n",USAGE);
117 GETHELP;
118 exit(1);
119 }
120
121 if (!quiet)
122 {
123 fprintf(stderr,">A complg");
124 if (restricted || Restricted || dolabel || Lswitch || also)
125 fprintf(stderr," -");
126 if (restricted && !Restricted) fprintf(stderr,"r");
127 if (Restricted) fprintf(stderr,"R");
128 if (dolabel) fprintf(stderr,"l");
129 if (Lswitch) fprintf(stderr,"L");
130 if (also) fprintf(stderr,"a");
131 if (argnum > 0) fprintf(stderr," %s",infilename);
132 if (argnum > 1) fprintf(stderr," %s",outfilename);
133 fprintf(stderr,"\n");
134 fflush(stderr);
135 }
136
137 if (infilename && infilename[0] == '-') infilename = NULL;
138 infile = opengraphfile(infilename,&codetype,FALSE,1);
139 if (!infile) exit(1);
140 if (!infilename) infilename = "stdin";
141
142 if (!outfilename || outfilename[0] == '-')
143 {
144 outfilename = "stdout";
145 outfile = stdout;
146 }
147 else if ((outfile = fopen(outfilename,"w")) == NULL)
148 {
149 fprintf(stderr,"Can't open output file %s\n",outfilename);
150 gt_abort(NULL);
151 }
152
153 if (codetype&SPARSE6) outcode = SPARSE6;
154 else if (codetype&DIGRAPH6) outcode = DIGRAPH6;
155 else outcode = GRAPH6;
156
157 if (codetype&HAS_HEADER)
158 {
159 if (outcode == SPARSE6) writeline(outfile,SPARSE6_HEADER);
160 else if (outcode == DIGRAPH6) writeline(outfile,DIGRAPH6_HEADER);
161 else writeline(outfile,GRAPH6_HEADER);
162 }
163
164 nauty_check(WORDSIZE,1,1,NAUTYVERSIONID);
165
166 nin = 0;
167 t = CPUTIME;
168 while (TRUE)
169 {
170 if ((g = readgg(infile,NULL,0,&m,&n,&digraph)) == NULL) break;
171 ++nin;
172 #if !MAXN
173 DYNALLOC2(graph,gc,gc_sz,n,m,"complg");
174 #endif
175
176 if (restricted || Restricted)
177 {
178 ned = loops = 0;
179 gwords = m * (size_t)n;
180 nn = n * (size_t)(n-1);
181 for (ii = 0; ii < gwords; ++ii) ned += POPCOUNT(g[ii]);
182 for (ii = 0; ii < n; ++ii) if (ISELEMENT(g+m*ii,ii)) ++loops;
183 if (Lswitch)
184 {
185 loopsc = n - loops;
186 nedc = nn + n - (ned-loops)/2;
187 }
188 else
189 {
190 loopsc = loops;
191 nedc = nn - (ned-3*loops)/2;
192 }
193
194 if (ned > nedc || (ned == nedc && !Restricted))
195 {
196 compl(g,m,n,gc,Lswitch);
197 if (dolabel)
198 {
199 #if !MAXN
200 DYNALLOC2(graph,hc,hc_sz,n,m,"complg");
201 #endif
202 fcanonise(gc,m,n,hc,NULL,digraph||loopsc>0);
203 gq = hc;
204 }
205 else
206 gq = gc;
207 }
208 else if (ned < nedc)
209 {
210 if (dolabel)
211 {
212 #if !MAXN
213 DYNALLOC2(graph,h,h_sz,n,m,"complg");
214 #endif
215 fcanonise(g,m,n,h,NULL,digraph||loops>0);
216 gq = h;
217 }
218 else
219 gq = g;
220 }
221 else
222 {
223 compl(g,m,n,gc,Lswitch);
224 #if !MAXN
225 DYNALLOC2(graph,h,h_sz,n,m,"complg");
226 DYNALLOC2(graph,hc,hc_sz,n,m,"complg");
227 #endif
228 fcanonise(g,m,n,h,NULL,digraph||loops>0);
229 fcanonise(gc,m,n,hc,NULL,digraph||loopsc>0);
230 for (ii = 0; ii < gwords; ++ii)
231 if (h[ii] != hc[ii]) break;
232 if (ii == gwords || hc[ii] < h[ii])
233 {
234 if (dolabel) gq = hc; else gq = gc;
235 }
236 else
237 {
238 if (dolabel) gq = h; else gq = g;
239 }
240 }
241 }
242 else /* Not restricted */
243 {
244 compl(g,m,n,gc,Lswitch);
245 if (dolabel)
246 {
247 #if !MAXN
248 DYNALLOC2(graph,hc,hc_sz,n,m,"complg");
249 #endif
250 fcanonise(gc,m,n,hc,NULL,digraph||loopsc>0);
251 gq = hc;
252 }
253 else
254 gq = gc;
255 }
256
257 if (also)
258 {
259 if (outcode == SPARSE6) writes6(outfile,g,m,n);
260 else if (outcode == DIGRAPH6) writed6(outfile,g,m,n);
261 else writeg6(outfile,g,m,n);
262 }
263
264 if (outcode == SPARSE6) writes6(outfile,gq,m,n);
265 else if (outcode == DIGRAPH6) writed6(outfile,gq,m,n);
266 else writeg6(outfile,gq,m,n);
267 FREES(g);
268 }
269 t = CPUTIME - t;
270
271 if (!quiet)
272 fprintf(stderr,">Z " COUNTER_FMT
273 " graphs converted from %s to %s in %3.2f sec.\n",
274 nin,infilename,outfilename,t);
275
276 exit(0);
277 }
278