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