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