1
2 /*
3 * This file contains the graph handling routines.
4 *
5 * Copyright (C) 2002 Sampo Niskanen, Patric �sterg�rd.
6 * Licensed under the GNU GPL, read the file LICENSE for details.
7 */
8
9
10 #include <stdio.h>
11 #include <ctype.h>
12 #include <string.h>
13 #include "cliquer/graph.h"
14
15
16 static graph_t *graph_read_dimacs_binary(FILE *fp,char *firstline);
17 static graph_t *graph_read_dimacs_ascii(FILE *fp,char *firstline);
18
19
20 /*
21 * graph_new()
22 *
23 * Returns a newly allocated graph with n vertices all with weight 1,
24 * and no edges.
25 */
graph_new(int n)26 graph_t *graph_new(int n) {
27 graph_t *g;
28 int i;
29
30 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
31 ASSERT(n>0);
32
33 g=malloc(sizeof(graph_t));
34 g->n=n;
35 g->edges=malloc(g->n * sizeof(set_t));
36 g->weights=malloc(g->n * sizeof(int));
37 for (i=0; i < g->n; i++) {
38 g->edges[i]=set_new(n);
39 g->weights[i]=1;
40 }
41 return g;
42 }
43
44 /*
45 * graph_free()
46 *
47 * Frees the memory associated with the graph g.
48 */
graph_free(graph_t * g)49 void graph_free(graph_t *g) {
50 int i;
51
52 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
53 ASSERT(g!=NULL);
54 ASSERT(g->n > 0);
55
56 for (i=0; i < g->n; i++) {
57 set_free(g->edges[i]);
58 }
59 free(g->weights);
60 free(g->edges);
61 free(g);
62 return;
63 }
64
65
66 /*
67 * graph_resize()
68 *
69 * Resizes graph g to given size. If size > g->n, the new vertices are
70 * not connected to any others and their weights are set to 1.
71 * If size < g->n, the last g->n - size vertices are removed.
72 */
graph_resize(graph_t * g,int size)73 void graph_resize(graph_t *g, int size) {
74 int i;
75
76 ASSERT(g!=NULL);
77 ASSERT(g->n > 0);
78 ASSERT(size > 0);
79
80 if (g->n == size)
81 return;
82
83 /* Free/alloc extra edge-sets */
84 for (i=size; i < g->n; i++)
85 set_free(g->edges[i]);
86 g->edges=realloc(g->edges, size * sizeof(set_t));
87 for (i=g->n; i < size; i++)
88 g->edges[i]=set_new(size);
89
90 /* Resize original sets */
91 for (i=0; i < MIN(g->n,size); i++) {
92 g->edges[i]=set_resize(g->edges[i],size);
93 }
94
95 /* Weights */
96 g->weights=realloc(g->weights,size * sizeof(int));
97 for (i=g->n; i<size; i++)
98 g->weights[i]=1;
99
100 g->n=size;
101 return;
102 }
103
104 /*
105 * graph_crop()
106 *
107 * Resizes the graph so as to remove all highest-valued isolated vertices.
108 */
graph_crop(graph_t * g)109 void graph_crop(graph_t *g) {
110 int i;
111
112 for (i=g->n-1; i>=1; i--)
113 if (set_size(g->edges[i])>0)
114 break;
115 graph_resize(g,i+1);
116 return;
117 }
118
119
120 /*
121 * graph_weighted()
122 *
123 * Returns TRUE if all vertex weights of graph g are all the same.
124 *
125 * Note: Does NOT require weights to be 1.
126 */
graph_weighted(graph_t * g)127 boolean graph_weighted(graph_t *g) {
128 int i,w;
129
130 w=g->weights[0];
131 for (i=1; i < g->n; i++)
132 if (g->weights[i] != w)
133 return TRUE;
134 return FALSE;
135 }
136
137 /*
138 * graph_edge_count()
139 *
140 * Returns the number of edges in graph g.
141 */
graph_edge_count(graph_t * g)142 int graph_edge_count(graph_t *g) {
143 int i;
144 int count=0;
145
146 for (i=0; i < g->n; i++) {
147 count += set_size(g->edges[i]);
148 }
149 return count/2;
150 }
151
152
153 /*
154 * graph_write_dimacs_ascii_file()
155 *
156 * Writes an ASCII dimacs-format file of graph g, with comment, to
157 * given file.
158 *
159 * Returns TRUE if successful, FALSE if an error occurred.
160 */
graph_write_dimacs_ascii_file(graph_t * g,char * comment,char * file)161 boolean graph_write_dimacs_ascii_file(graph_t *g, char *comment, char *file) {
162 FILE *fp;
163
164 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
165 ASSERT(file!=NULL);
166
167 if ((fp=fopen(file,"wb"))==NULL)
168 return FALSE;
169 if (!graph_write_dimacs_ascii(g,comment,fp)) {
170 fclose(fp);
171 return FALSE;
172 }
173 fclose(fp);
174 return TRUE;
175 }
176
177 /*
178 * graph_write_dimacs_ascii()
179 *
180 * Writes an ASCII dimacs-format file of graph g, with comment, to the
181 * file stream fp.
182 *
183 * Returns TRUE if successful, FALSE if an error occurred.
184 */
graph_write_dimacs_ascii(graph_t * g,char * comment,FILE * fp)185 boolean graph_write_dimacs_ascii(graph_t *g, char *comment, FILE *fp) {
186 int i,j;
187
188 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
189 ASSERT(graph_test(g,NULL));
190 ASSERT(fp!=NULL);
191
192 if (comment)
193 fprintf(fp,"c %s\n",comment);
194 fprintf(fp,"p edge %d %d\n",g->n,graph_edge_count(g));
195 for (i=0; i < g->n; i++)
196 if (g->weights[i]!=1)
197 fprintf(fp,"n %d %d\n",i+1,g->weights[i]);
198 for (i=0; i < g->n; i++)
199 for (j=0; j<i; j++)
200 if (GRAPH_IS_EDGE_FAST(g,i,j))
201 fprintf(fp,"e %d %d\n",i+1,j+1);
202 return TRUE;
203 }
204
205 /*
206 * graph_write_dimacs_binary_file()
207 *
208 * Writes a binary dimacs-format file of graph g, with comment, to
209 * given file.
210 *
211 * Returns TRUE if successful, FALSE if an error occurred.
212 */
graph_write_dimacs_binary_file(graph_t * g,char * comment,char * file)213 boolean graph_write_dimacs_binary_file(graph_t *g, char *comment, char *file) {
214 FILE *fp;
215
216 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
217 ASSERT(file!=NULL);
218
219 if ((fp=fopen(file,"wb"))==NULL)
220 return FALSE;
221 if (!graph_write_dimacs_binary(g,comment,fp)) {
222 fclose(fp);
223 return FALSE;
224 }
225 fclose(fp);
226 return TRUE;
227 }
228
229 /*
230 * graph_write_dimacs_binary()
231 *
232 * Writes a binary dimacs-format file of graph g, with comment, to the
233 * file stream fp.
234 *
235 * Returns TRUE if successful, FALSE if an error occurred.
236 */
237
238 #define STR_APPEND(s) \
239 if (headerlength+strlen(s) >= headersize) { \
240 headersize+=1024; \
241 header=realloc(header,headersize); \
242 } \
243 strncat(header,s,1000); \
244 headerlength+=strlen(s);
245
graph_write_dimacs_binary(graph_t * g,char * comment,FILE * fp)246 boolean graph_write_dimacs_binary(graph_t *g, char *comment,FILE *fp) {
247 char *buf;
248 char *header=NULL;
249 int headersize=0;
250 int headerlength=0;
251 int i,j;
252
253 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
254 ASSERT(graph_test(g,NULL));
255 ASSERT(fp!=NULL);
256
257 buf=malloc(MAX(1024,g->n/8+1));
258 header=malloc(1024);
259 header[0]=0;
260 headersize=1024;
261 if (comment) {
262 strcpy(buf,"c ");
263 strncat(buf,comment,1000);
264 strcat(buf,"\n");
265 STR_APPEND(buf);
266 }
267 sprintf(buf,"p edge %d %d\n",g->n,graph_edge_count(g));
268 STR_APPEND(buf);
269 for (i=0; i < g->n; i++) {
270 if (g->weights[i]!=1) {
271 sprintf(buf,"n %d %d\n",i+1,g->weights[i]);
272 STR_APPEND(buf);
273 }
274 }
275
276 fprintf(fp,"%d\n",(int)strlen(header));
277 fprintf(fp,"%s",header);
278 free(header);
279
280 for (i=0; i < g->n; i++) {
281 memset(buf,0,i/8+1);
282 for (j=0; j<i; j++) {
283 if (GRAPH_IS_EDGE_FAST(g,i,j)) {
284 buf[j/8] |= SET_BIT_MASK(7-j%8);
285 }
286 }
287 fwrite(buf,1,i/8+1,fp);
288 }
289 free(buf);
290 return TRUE;
291 }
292
293
294
295 /*
296 * graph_read_dimacs_file()
297 *
298 * Reads a dimacs-format (ASCII or binary) file from the given file.
299 *
300 * Returns a newly allocated graph, or NULL if an error occurred, and an
301 * error message is printed to stderr.
302 */
graph_read_dimacs_file(char * file)303 graph_t *graph_read_dimacs_file(char *file) {
304 FILE *fp;
305 graph_t *g;
306
307 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
308 ASSERT(file!=NULL);
309
310 if ((fp=fopen(file,"rb"))==NULL) {
311 perror(file);
312 return NULL;
313 }
314 g=graph_read_dimacs(fp);
315 fclose(fp);
316 return g;
317 }
318
319
320 /*
321 * graph_read_dimacs()
322 *
323 * Reads a dimacs-format (ASCII or binary) file from the file stream fp.
324 *
325 * Returns a newly allocated graph, or NULL if an error occurred, and an
326 * error message is printed to stderr.
327 */
graph_read_dimacs(FILE * fp)328 graph_t *graph_read_dimacs(FILE *fp) {
329 char buffer[1024];
330 graph_t *g;
331 char tmp[10];
332 int n;
333
334 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
335 ASSERT(fp!=NULL);
336
337 if (fgets(buffer,1023,fp)==NULL) {
338 fprintf(stderr,"Input does not contain any data.\n");
339 return NULL;
340 }
341 if (sscanf(buffer," %d %2s",&n,tmp)!=1) {
342 g=graph_read_dimacs_ascii(fp,buffer);
343 } else {
344 g=graph_read_dimacs_binary(fp,buffer);
345 }
346 return g;
347 }
348
349
350 /*
351 * parse_input()
352 *
353 * Parses the string str for ASCII-format dimacs commands, and modifies
354 * the graph g accordingly.
355 *
356 * Returns TRUE if successful, FALSE if a bad command was encountered.
357 *
358 * Note: Ignores all unknown commands. The 'd', 'v' and 'x' commands
359 * (mainly generator-specific information) are ignored silently,
360 * for all others a warning message is printed to stderr.
361 */
parse_input(char * str,graph_t * g)362 static boolean parse_input(char *str,graph_t *g) {
363 int i,j,w;
364 char tmp[16];
365
366 for (i=0; i<strlen(str); i++) {
367 if (!isspace((int)str[i]))
368 break;
369 }
370 if (i>=strlen(str)) /* blank line */
371 return TRUE;
372 if (str[i+1]!=0 && !isspace(str[i+1])) /* not 1-char field */
373 return FALSE;
374
375 switch (str[i]) {
376 case 'c':
377 return TRUE;
378 case 'p':
379 if (g->n != 0)
380 return FALSE;
381 if (sscanf(str," p %15s %d %d %2s",tmp,&(g->n),&i,tmp)!=3)
382 return FALSE;
383 if (g->n <= 0)
384 return FALSE;
385 g->edges=calloc(g->n,sizeof(set_t));
386 for (i=0; i<g->n; i++)
387 g->edges[i]=set_new(g->n);
388 g->weights=calloc(g->n,sizeof(int));
389 for (i=0; i<g->n; i++)
390 g->weights[i]=1;
391 return TRUE;
392 case 'n':
393 if ((g->n <= 0) || (g->weights == NULL))
394 return FALSE;
395 if (sscanf(str," n %d %d %2s",&i,&w,tmp)!=2)
396 return FALSE;
397 if (i<1 || i>g->n)
398 return FALSE;
399 if (w<=0)
400 return FALSE;
401 g->weights[i-1]=w;
402 return TRUE;
403 case 'e':
404 if ((g->n <= 0) || (g->edges == NULL))
405 return FALSE;
406 if (sscanf(str," e %d %d %2s",&i,&j,tmp)!=2)
407 return FALSE;
408 if (i<1 || j<1 || i>g->n || j>g->n)
409 return FALSE;
410 if (i==j) /* We want antireflexive graphs. */
411 return TRUE;
412 GRAPH_ADD_EDGE(g,i-1,j-1);
413 return TRUE;
414 case 'd':
415 case 'v':
416 case 'x':
417 return TRUE;
418 default:
419 fprintf(stderr,"Warning: ignoring field '%c' in "
420 "input.\n",str[i]);
421 return TRUE;
422 }
423 }
424
425
426 /*
427 * graph_read_dimacs_binary()
428 *
429 * Reads a dimacs-format binary file from file stream fp with the first
430 * line being firstline.
431 *
432 * Returns the newly-allocated graph or NULL if an error occurred.
433 *
434 * TODO: This function leaks memory when reading erroneous files.
435 */
graph_read_dimacs_binary(FILE * fp,char * firstline)436 static graph_t *graph_read_dimacs_binary(FILE *fp,char *firstline) {
437 int length=0;
438 graph_t *g;
439 int i,j;
440 char *buffer;
441 char *start;
442 char *end;
443 char **buf;
444 char tmp[10];
445
446 if (sscanf(firstline," %d %2s",&length,tmp)!=1)
447 return NULL;
448 if (length<=0) {
449 fprintf(stderr,"Malformed preamble: preamble size < 0.\n");
450 return NULL;
451 }
452 buffer=malloc(length+2);
453 if (fread(buffer,1,length,fp)<length) {
454 fprintf(stderr,"Malformed preamble: unexpected "
455 "end of file.\n");
456 free(buffer);
457 return NULL;
458 }
459
460 g=calloc(1,sizeof(graph_t));
461 start=buffer;
462 while (start < buffer+length) {
463 end=strchr(start,'\n');
464 if (end==NULL)
465 end=buffer+length;
466 end[0]=0;
467 if (!parse_input(start,g)) {
468 fprintf(stderr,"Malformed preamble: %s\n",start);
469 free (buffer);
470 return NULL;
471 }
472 start=end+1;
473 }
474
475 free(buffer);
476 if (g->n <= 0) {
477 fprintf(stderr,"Malformed preamble: number of "
478 "vertices <= 0\n");
479 free(g);
480 return NULL;
481 }
482
483 /* Binary part. */
484 buf=calloc(g->n,sizeof(char*));
485 for (i=0; i < g->n; i++) {
486 buf[i]=calloc(g->n,1);
487 if (fread(buf[i],1,i/8+1,fp) < (i/8+1)) {
488 fprintf(stderr,"Unexpected end of file when "
489 "reading graph.\n");
490 return NULL;
491 }
492 }
493
494 for (i=0; i < g->n; i++) {
495 for (j=0; j<i; j++) {
496 if (buf[i][j/8]&(1<<(7-(j%8)))) {
497 GRAPH_ADD_EDGE(g,i,j);
498 }
499 }
500 free(buf[i]);
501 }
502 free(buf);
503
504 return g;
505 }
506
507
508 /*
509 * graph_read_dimacs_ascii()
510 *
511 * Reads a dimacs-format ASCII file from file stream fp with the first
512 * line being firstline.
513 *
514 * Returns the newly-allocated graph or NULL if an error occurred.
515 *
516 * TODO: This function leaks memory when reading erroneous files.
517 */
graph_read_dimacs_ascii(FILE * fp,char * firstline)518 static graph_t *graph_read_dimacs_ascii(FILE *fp, char *firstline) {
519 graph_t *g;
520 char buffer[1024];
521
522 g=calloc(1,sizeof(graph_t));
523
524 if (!parse_input(firstline,g)) {
525 fprintf(stderr,"Malformed input: %s",firstline);
526 free(g);
527 return NULL;
528 }
529 while (fgets(buffer,1023,fp)) {
530 if (!parse_input(buffer,g)) {
531 fprintf(stderr,"Malformed input: %s",buffer);
532 return NULL;
533 }
534 }
535 if (g->n <= 0) {
536 free(g);
537 fprintf(stderr,"Unexpected end of file when reading graph.\n");
538 return NULL;
539 }
540
541 return g;
542 }
543
544
545
546 /*
547 * graph_print()
548 *
549 * Prints a representation of the graph g to stdout (along with any errors
550 * noticed). Mainly useful for debugging purposes and trivial output.
551 *
552 * The output consists of a first line describing the dimensions and then
553 * one line per vertex containing the vertex number (numbered 0,...,n-1),
554 * the vertex weight (if the graph is weighted), "->" and then a list
555 * of all vertices it is adjacent to.
556 */
graph_print(graph_t * g)557 void graph_print(graph_t *g) {
558 int i,j;
559 int asymm=0;
560 int refl=0;
561 int nonpos=0;
562 int extra=0;
563 unsigned int weight=0;
564 boolean weighted;
565
566 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
567
568 if (g==NULL) {
569 printf(" WARNING: Graph pointer is NULL!\n");
570 return;
571 }
572 if (g->n <= 0) {
573 printf(" WARNING: Graph has %d vertices "
574 "(should be positive)!\n",g->n);
575 return;
576 }
577
578 weighted=graph_weighted(g);
579
580 printf("%s graph has %d vertices, %d edges (density %.2f).\n",
581 weighted?"Weighted":((g->weights[0]==1)?
582 "Unweighted":"Semi-weighted"),
583 g->n,graph_edge_count(g),
584 (float)graph_edge_count(g)/((float)(g->n - 1)*(g->n)/2));
585
586 for (i=0; i < g->n; i++) {
587 printf("%2d",i);
588 if (weighted) {
589 printf(" w=%d",g->weights[i]);
590 if (g->weights[i] <= 0) {
591 printf("*NON-POSITIVE*");
592 nonpos++;
593 }
594 }
595 if (weight < INT_MAX)
596 weight+=g->weights[i];
597 printf(" ->");
598 for (j=0; j < g->n; j++) {
599 if (SET_CONTAINS_FAST(g->edges[i],j)) {
600 printf(" %d",j);
601 if (i==j) {
602 printf("*REFLEXIVE*");
603 refl++;
604 }
605 if (!SET_CONTAINS_FAST(g->edges[j],i)) {
606 printf("*ASYMMERTIC*");
607 asymm++;
608 }
609 }
610 }
611 for (j=g->n; j < SET_ARRAY_LENGTH(g->edges[i])*ELEMENTSIZE;
612 j++) {
613 if (SET_CONTAINS_FAST(g->edges[i],j)) {
614 printf(" %d*NON-EXISTENT*",j);
615 extra++;
616 }
617 }
618 printf("\n");
619 }
620
621 if (asymm)
622 printf(" WARNING: Graph contained %d asymmetric edges!\n",
623 asymm);
624 if (refl)
625 printf(" WARNING: Graph contained %d reflexive edges!\n",
626 refl);
627 if (nonpos)
628 printf(" WARNING: Graph contained %d non-positive vertex "
629 "weights!\n",nonpos);
630 if (extra)
631 printf(" WARNING: Graph contained %d edges to "
632 "non-existent vertices!\n",extra);
633 if (weight>=INT_MAX)
634 printf(" WARNING: Total graph weight >= INT_MAX!\n");
635 return;
636 }
637
638
639 /*
640 * graph_test()
641 *
642 * Tests graph g to be valid. Checks that g is non-NULL, the edges are
643 * symmetric and anti-reflexive, and that all vertex weights are positive.
644 * If output is non-NULL, prints a few lines telling the status of the graph
645 * to file descriptor output.
646 *
647 * Returns TRUE if the graph is valid, FALSE otherwise.
648 */
graph_test(graph_t * g,FILE * output)649 boolean graph_test(graph_t *g,FILE *output) {
650 int i,j;
651 int edges=0;
652 int asymm=0;
653 int nonpos=0;
654 int refl=0;
655 int extra=0;
656 unsigned int weight=0;
657 boolean weighted;
658
659 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
660
661 if (g==NULL) {
662 if (output)
663 fprintf(output," WARNING: Graph pointer is NULL!\n");
664 return FALSE;
665 }
666
667 weighted=graph_weighted(g);
668
669 for (i=0; i < g->n; i++) {
670 if (g->edges[i]==NULL) {
671 if (output)
672 fprintf(output," WARNING: Graph edge set "
673 "NULL!\n"
674 " (further warning suppressed)\n");
675 return FALSE;
676 }
677 if (SET_MAX_SIZE(g->edges[i]) < g->n) {
678 if (output)
679 fprintf(output," WARNING: Graph edge set "
680 "too small!\n"
681 " (further warnings suppressed)\n");
682 return FALSE;
683 }
684 for (j=0; j < g->n; j++) {
685 if (SET_CONTAINS_FAST(g->edges[i],j)) {
686 edges++;
687 if (i==j) {
688 refl++;
689 }
690 if (!SET_CONTAINS_FAST(g->edges[j],i)) {
691 asymm++;
692 }
693 }
694 }
695 for (j=g->n; j < SET_ARRAY_LENGTH(g->edges[i])*ELEMENTSIZE;
696 j++) {
697 if (SET_CONTAINS_FAST(g->edges[i],j))
698 extra++;
699 }
700 if (g->weights[i] <= 0)
701 nonpos++;
702 if (weight<INT_MAX)
703 weight += g->weights[i];
704 }
705
706 edges/=2; /* Each is counted twice. */
707
708 if (output) {
709 /* Semi-weighted means all weights are equal, but not 1. */
710 fprintf(output,"%s graph has %d vertices, %d edges "
711 "(density %.2f).\n",
712 weighted?"Weighted":
713 ((g->weights[0]==1)?"Unweighted":"Semi-weighted"),
714 g->n,edges,(float)edges/((float)(g->n - 1)*(g->n)/2));
715
716 if (asymm)
717 fprintf(output," WARNING: Graph contained %d "
718 "asymmetric edges!\n",asymm);
719 if (refl)
720 fprintf(output," WARNING: Graph contained %d "
721 "reflexive edges!\n",refl);
722 if (nonpos)
723 fprintf(output," WARNING: Graph contained %d "
724 "non-positive vertex weights!\n",nonpos);
725 if (extra)
726 fprintf(output," WARNING: Graph contained %d edges "
727 "to non-existent vertices!\n",extra);
728 if (weight>=INT_MAX)
729 fprintf(output," WARNING: Total graph weight >= "
730 "INT_MAX!\n");
731 if (asymm==0 && refl==0 && nonpos==0 && extra==0 &&
732 weight<INT_MAX)
733 fprintf(output,"Graph OK.\n");
734 }
735
736 if (asymm || refl || nonpos || extra || weight>=INT_MAX)
737 return FALSE;
738
739 return TRUE;
740 }
741
742
743 /*
744 * graph_test_regular()
745 *
746 * Returns the vertex degree for regular graphs, or -1 if the graph is
747 * not regular.
748 */
graph_test_regular(graph_t * g)749 int graph_test_regular(graph_t *g) {
750 int i,n;
751
752 n=set_size(g->edges[0]);
753
754 for (i=1; i < g->n; i++) {
755 if (set_size(g->edges[i]) != n)
756 return -1;
757 }
758 return n;
759 }
760
761