1 /* checks6.c; May 2005 */
2
3 #define USAGE "checks6 [-p#:#w] [infile [outfile]]"
4
5 #define HELPTEXT \
6 " Check a file of graphs, optionally write corrected version\n\
7 \n\
8 -p# -p#:# \n\
9 Specify range of input lines (first is 1)\n\
10 \n\
11 -w Write corrected graphs (default is not to write)\n\
12 A header is written if there is one in the input.\n"
13
14 /***********************************************************************/
15
16 #include "gtools.h"
17
18 /***********************************************************************/
19
20 static boolean
seemsbad(char * s)21 seemsbad(char *s)
22 /* Check graph string for apparent problem, if so, correct it */
23 {
24 int i,j,k,m,n;
25 char *p,x,pq;
26 set *gj;
27 long ii;
28 int r,rr,topbit,nb,lastj;
29 graph g[16];
30
31 if (s[0] != ':') return FALSE; /* not sparse6 */
32
33 n = graphsize(s);
34 if (n != 2 && n != 4 && n != 8 && n != 16) return FALSE;
35 m = 1;
36
37 stringtograph(s,g,m);
38 if (g[n-1] != bit[n-1]) return FALSE;
39 if (g[n-2] == 0) return FALSE;
40
41 g[n-1] = 0;
42 p = s+2;
43
44 for (i = n-1, nb = 0; i != 0 ; i >>= 1, ++nb) {}
45 topbit = 1 << (nb-1);
46 k = 6;
47 x = 0;
48
49 lastj = 0;
50 for (j = 0; j < n; ++j)
51 {
52 gj = GRAPHROW(g,j,m);
53 for (i = 0; i <= j; ++i)
54 {
55 if (ISELEMENT(gj,i))
56 {
57 if (j == lastj)
58 {
59 x <<= 1;
60 if (--k == 0)
61 {
62 p++;
63 k = 6;
64 x = 0;
65 }
66 }
67 else
68 {
69 x = (x << 1) | 1;
70 if (--k == 0)
71 {
72 p++;
73 k = 6;
74 x = 0;
75 }
76 if (j > lastj+1)
77 {
78 for (r = 0, rr = j; r < nb; ++r, rr <<= 1)
79 {
80 if (rr & topbit) x = (x << 1) | 1;
81 else x <<= 1;
82 if (--k == 0)
83 {
84 p++;
85 k = 6;
86 x = 0;
87 }
88 }
89 x <<= 1;
90 if (--k == 0)
91 {
92 p++;
93 k = 6;
94 x = 0;
95 }
96 }
97 lastj = j;
98 }
99 for (r = 0, rr = i; r < nb; ++r, rr <<= 1)
100 {
101 if (rr & topbit) x = (x << 1) | 1;
102 else x <<= 1;
103 if (--k == 0)
104 {
105 p++;
106 k = 6;
107 x = 0;
108 }
109 }
110 }
111 }
112 }
113
114 if (k != 6)
115 {
116 if (k >= nb+1 && lastj == n-2 && n == (1<<nb))
117 {
118 *p++ = BIAS6 + ((x << k) | ((1 << (k-1)) - 1));
119 return TRUE;
120 }
121 else
122 return FALSE;
123 }
124 }
125
126 /***********************************************************************/
127
main(argc,argv)128 main(argc,argv)
129 int argc;
130 char *argv[];
131 {
132 int m,n,codetype;
133 char *infilename,*outfilename;
134 FILE *infile,*outfile;
135 int outcode;
136 long nin,nerr;
137 int argnum,j;
138 char *arg,sw,*s;
139 boolean pswitch;
140 boolean wswitch;
141 boolean badargs;
142 long pval1,pval2,maxin;
143
144 HELP;
145
146 wswitch = pswitch = FALSE;
147 infilename = outfilename = NULL;
148
149 argnum = 0;
150 badargs = FALSE;
151 for (j = 1; !badargs && j < argc; ++j)
152 {
153 arg = argv[j];
154 if (arg[0] == '-' && arg[1] != '\0')
155 {
156 ++arg;
157 while (*arg != '\0')
158 {
159 sw = *arg++;
160 SWBOOLEAN('w',wswitch)
161 else SWRANGE('p',":-",pswitch,pval1,pval2,"checks6 -p")
162 else badargs = TRUE;
163 }
164 }
165 else
166 {
167 ++argnum;
168 if (argnum == 1) infilename = arg;
169 else if (argnum == 2) outfilename = arg;
170 else badargs = TRUE;
171 }
172 }
173
174 if (badargs || argnum > 2)
175 {
176 fprintf(stderr,">E Usage: %s\n",USAGE);
177 GETHELP;
178 exit(1);
179 }
180
181 if (infilename && infilename[0] == '-') infilename = NULL;
182 infile = opengraphfile(infilename,&codetype,FALSE,
183 pswitch ? pval1 : 1);
184 if (!infile) exit(1);
185 if (!infilename) infilename = "stdin";
186
187 if (!outfilename || outfilename[0] == '-')
188 {
189 outfilename = "stdout";
190 outfile = stdout;
191 }
192 else if ((outfile = fopen(outfilename,"w")) == NULL)
193 {
194 fprintf(stderr,"Can't open output file %s\n",outfilename);
195 gt_abort(NULL);
196 }
197
198 if (codetype&SPARSE6) outcode = SPARSE6;
199 else outcode = GRAPH6;
200
201 if (wswitch && (codetype&HAS_HEADER))
202 {
203 if (outcode == SPARSE6) writeline(outfile,SPARSE6_HEADER);
204 else writeline(outfile,GRAPH6_HEADER);
205 }
206
207 nerr = nin = 0;
208 if (!pswitch || pval2 == NOLIMIT)
209 maxin = NOLIMIT;
210 else if (pval1 < 1) maxin = pval2;
211 else maxin = pval2 - pval1 + 1;
212 while (nin < maxin || maxin == NOLIMIT)
213 {
214 if ((s = getline(infile)) == NULL) break;
215 ++nin;
216
217 if (seemsbad(s)) ++nerr;
218 if (wswitch) writeline(outfile,s);
219 }
220
221 fprintf(stderr,">Z %ld graphs read",nin);
222 if (nerr > 0) fprintf(stderr,"; %ld probable errors",nerr);
223 else fprintf(stderr,"; NO PROBLEMS");
224 if (wswitch) fprintf(stderr,"; %ld graphs written",nin);
225 fprintf(stderr,"\n");
226
227 exit(0);
228 }
229