1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3
4 /*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14
15 /*
16 * Written by Stephen North
17 * Updated by Emden Gansner
18 */
19
20 #include "config.h"
21
22 #include <ctype.h>
23 #include <stdlib.h>
24 #include "cgraph.h"
25
26 #define N_NEW(n,t) (t*)calloc((n),sizeof(t))
27 #define NEW(t) (t*)malloc(sizeof(t))
28
29 typedef struct {
30 Agrec_t h;
31 char cc_subg; /* true iff subgraph corresponds to a component */
32 } Agraphinfo_t;
33
34 typedef struct {
35 Agrec_t h;
36 char mark;
37 Agobj_t* ptr;
38 } Agnodeinfo_t;
39
40 #define GD_cc_subg(g) (((Agraphinfo_t*)(g->base.data))->cc_subg)
41 #define ND_mark(n) (((Agnodeinfo_t*)(n->base.data))->mark)
42 #define ND_ptr(n) (((Agnodeinfo_t*)(n->base.data))->ptr)
43 #define ND_dn(n) ((Agnode_t*)ND_ptr(n))
44 #define ND_clust(n) ((Agraph_t*)ND_ptr(n))
45 #define agfindnode(G,N) (agnode(G, N, 0))
46
47 #include <getopt.h>
48
49 #ifdef HAVE_UNISTD_H
50 #include <unistd.h>
51 #endif
52 #include <string.h>
53 #include "ingraphs.h"
54
55 /* internals of libgraph */
56 #define TAG_NODE 1
57
58 #define INTERNAL 0 /* Basically means all components need to be
59 * generated before output
60 */
61 #define EXTERNAL 1
62 #define SILENT 2
63 #define EXTRACT 3
64
65 #define BY_INDEX 1
66 #define BY_SIZE 2
67
68 char* Cmd;
69 char **Files;
70 int verbose;
71 int printMode = INTERNAL;
72 int useClusters = 0;
73 int doEdges = 1; /* induce edges */
74 int doAll = 1; /* induce subgraphs */
75 char *suffix = 0;
76 char *outfile = 0;
77 char *path = 0;
78 int sufcnt = 0;
79 int sorted = 0;
80 int sortIndex = 0;
81 int sortFinal;
82 int x_index = -1;
83 int x_final = -1; /* require 0 <= x_index <= x_final or x_final= -1 */
84 int x_mode;
85 char *x_node;
86
87 static char *useString =
88 "Usage: ccomps [-svenCx?] [-X[#%]s[-f]] [-o<out template>] <files>\n\
89 -s - silent\n\
90 -x - external\n\
91 -X - extract component\n\
92 -C - use clusters\n\
93 -e - do not induce edges\n\
94 -n - do not induce subgraphs\n\
95 -v - verbose\n\
96 -o - output file template\n\
97 -z - sort by size, largest first\n\
98 -? - print usage\n\
99 If no files are specified, stdin is used\n";
100
usage(int v)101 static void usage(int v)
102 {
103 printf("%s",useString);
104 exit(v);
105 }
106
split(char * name)107 static void split(char *name)
108 {
109 char *sfx = 0;
110 int size;
111
112 sfx = strrchr(name, '.');
113 if (sfx) {
114 suffix = sfx + 1;
115 size = sfx - name;
116 path = (char *) malloc(size + 1);
117 strncpy(path, name, size);
118 *(path + size) = '\0';
119 } else {
120 path = name;
121 }
122 }
123
124 /* isCluster:
125 * Return true if graph is a cluster
126 */
isCluster(Agraph_t * g)127 static int isCluster(Agraph_t * g)
128 {
129 return (strncmp(agnameof(g), "cluster", 7) == 0);
130 }
131
init(int argc,char * argv[])132 static void init(int argc, char *argv[])
133 {
134 int c;
135 char* endp;
136
137 Cmd = argv[0];
138 opterr = 0;
139 while ((c = getopt(argc, argv, ":zo:xCX:nesv")) != -1) {
140 switch (c) {
141 case 'o':
142 outfile = optarg;
143 split(outfile);
144 break;
145 case 'C':
146 useClusters = 1;
147 break;
148 case 'e':
149 doEdges = 0;
150 break;
151 case 'n':
152 doAll = 0;
153 break;
154 case 'x':
155 printMode = EXTERNAL;
156 break;
157 case 's':
158 printMode = SILENT;
159 break;
160 case 'X':
161 if ((*optarg == '#') || (*optarg == '%')) {
162 char *p = optarg + 1;
163 if (*optarg == '#') x_mode = BY_INDEX;
164 else x_mode = BY_SIZE;
165 if (isdigit(*p)) {
166 x_index = (int)strtol (p, &endp, 10);
167 printMode = EXTRACT;
168 if (*endp == '-') {
169 p = endp + 1;
170 if (isdigit(*p)) {
171 x_final = atoi (p);
172 if (x_final < x_index) {
173 printMode = INTERNAL;
174 fprintf(stderr,
175 "ccomps: final index %d < start index %d in -X%s flag - ignored\n",
176 x_final, x_index, optarg);
177 }
178 }
179 else if (*p) {
180 printMode = INTERNAL;
181 fprintf(stderr,
182 "ccomps: number expected in -X%s flag - ignored\n",
183 optarg);
184 }
185 }
186 else
187 x_final = x_index;
188 } else
189 fprintf(stderr,
190 "ccomps: number expected in -X%s flag - ignored\n",
191 optarg);
192 } else {
193 x_node = optarg;
194 printMode = EXTRACT;
195 }
196 break;
197 case 'v':
198 verbose = 1;
199 break;
200 case 'z':
201 sorted = 1;
202 break;
203 case ':':
204 fprintf(stderr,
205 "ccomps: option -%c missing argument - ignored\n", optopt);
206 break;
207 case '?':
208 if (optopt == '?')
209 usage(0);
210 else
211 fprintf(stderr,
212 "ccomps: option -%c unrecognized - ignored\n", optopt);
213 break;
214 }
215 }
216 argv += optind;
217 argc -= optind;
218
219 if (sorted) {
220 if ((printMode == EXTRACT) && (x_index >= 0)) {
221 printMode = INTERNAL;
222 sortIndex = x_index;
223 sortFinal = x_final;
224 }
225 else if (printMode == EXTERNAL) {
226 sortIndex = -1;
227 printMode = INTERNAL;
228 }
229 else
230 sorted = 0; /* not relevant; turn off */
231 }
232 if (argc > 0)
233 Files = argv;
234 }
235
236 typedef struct blk_t {
237 Agnode_t **data;
238 Agnode_t **endp;
239 struct blk_t *prev;
240 struct blk_t *next;
241 } blk_t;
242
243 typedef struct {
244 blk_t *fstblk;
245 blk_t *curblk;
246 Agnode_t **curp;
247 } stk_t;
248
249
250 #define SMALLBUF 1024
251 #define BIGBUF 1000000
252
253 static Agnode_t *base[SMALLBUF];
254 static blk_t Blk;
255 static stk_t Stk;
256
initStk(void)257 static void initStk(void)
258 {
259 Blk.data = base;
260 Blk.endp = Blk.data + SMALLBUF;
261 Stk.curblk = Stk.fstblk = &Blk;
262 Stk.curp = Stk.curblk->data;
263 }
264
push(Agnode_t * np)265 static void push(Agnode_t * np)
266 {
267 if (Stk.curp == Stk.curblk->endp) {
268 if (Stk.curblk->next == NULL) {
269 blk_t *bp = NEW(blk_t);
270 if (bp == 0) {
271 fprintf(stderr, "gc: Out of memory\n");
272 exit(1);
273 }
274 bp->prev = Stk.curblk;
275 bp->next = NULL;
276 bp->data = N_NEW(BIGBUF, Agnode_t *);
277 if (bp->data == 0) {
278 fprintf(stderr, "%s: Out of memory\n", Cmd);
279 exit(1);
280 }
281 bp->endp = bp->data + BIGBUF;
282 Stk.curblk->next = bp;
283 }
284 Stk.curblk = Stk.curblk->next;
285 Stk.curp = Stk.curblk->data;
286 }
287 ND_mark(np) = -1;
288 *Stk.curp++ = np;
289 }
290
pop(void)291 static Agnode_t *pop(void)
292 {
293 if (Stk.curp == Stk.curblk->data) {
294 if (Stk.curblk == Stk.fstblk)
295 return 0;
296 Stk.curblk = Stk.curblk->prev;
297 Stk.curp = Stk.curblk->endp;
298 }
299 Stk.curp--;
300 return *Stk.curp;
301 }
302
dfs(Agraph_t * g,Agnode_t * n,Agraph_t * out)303 static int dfs(Agraph_t * g, Agnode_t * n, Agraph_t * out)
304 {
305 Agedge_t *e;
306 Agnode_t *other;
307 int cnt = 0;
308
309 push(n);
310 while ((n = pop())) {
311 ND_mark(n) = 1;
312 cnt++;
313 agsubnode(out, n, 1);
314 for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
315 if ((other = agtail(e)) == n)
316 other = aghead(e);
317 if (ND_mark(other) == 0)
318 push (other);
319 }
320 }
321 return cnt;
322 }
323
324 /* nodeInduce:
325 * Using the edge set of eg, add to g any edges
326 * with both endpoints in g.
327 */
nodeInduce(Agraph_t * g,Agraph_t * eg)328 static int nodeInduce(Agraph_t * g, Agraph_t * eg)
329 {
330 Agnode_t *n;
331 Agedge_t *e;
332 int e_cnt = 0;
333
334 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
335 for (e = agfstout(eg, n); e; e = agnxtout(eg, e)) {
336 if (agsubnode(g, aghead(e), 0)) {
337 agsubedge(g, e, 1);
338 e_cnt++;
339 }
340 }
341 }
342 return e_cnt;
343 }
344
getName(void)345 static char *getName(void)
346 {
347 char *name;
348 static char *buf = 0;
349
350 if (sufcnt == 0)
351 name = outfile;
352 else {
353 if (!buf)
354 buf = (char *) malloc(strlen(outfile) + 20); /* enough to handle '_number' */
355 if (suffix)
356 sprintf(buf, "%s_%d.%s", path, sufcnt, suffix);
357 else
358 sprintf(buf, "%s_%d", path, sufcnt);
359 name = buf;
360 }
361 sufcnt++;
362 return name;
363 }
364
gwrite(Agraph_t * g)365 static void gwrite(Agraph_t * g)
366 {
367 FILE *outf;
368 char *name;
369
370 if (!outfile) {
371 agwrite(g, stdout);
372 fflush(stdout);
373 } else {
374 name = getName();
375 outf = fopen(name, "w");
376 if (!outf) {
377 fprintf(stderr, "Could not open %s for writing\n", name);
378 perror("ccomps");
379 }
380 agwrite(g, outf);
381 fflush(outf);
382 fclose(outf);
383 }
384 }
385
386 /* getBuf
387 * Return pointer to buffer containing at least n bytes.
388 * Non-reentrant.
389 */
getBuf(int n)390 static char *getBuf(int n)
391 {
392 static int len = 0;
393 static char *buf = 0;
394 int sz;
395
396 if (n > len) {
397 sz = n + 100;
398 if (len == 0)
399 buf = (char *) malloc(sz);
400 else
401 buf = (char *) realloc(buf, sz);
402 len = sz;
403 }
404 return buf;
405 }
406
407 /* projectG:
408 * If any nodes of subg are in g, create a subgraph of g
409 * and fill it with all nodes of subg in g and their induced
410 * edges in subg. Copy the attributes of subg to g. Return the subgraph.
411 * If not, return null.
412 */
projectG(Agraph_t * subg,Agraph_t * g,int inCluster)413 static Agraph_t *projectG(Agraph_t * subg, Agraph_t * g, int inCluster)
414 {
415 Agraph_t *proj = 0;
416 Agnode_t *n;
417 Agnode_t *m;
418
419 for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
420 if ((m = agfindnode(g, agnameof(n)))) {
421 if (proj == 0) {
422 proj = agsubg(g, agnameof(subg), 1);
423 }
424 agsubnode(proj, m, 1);
425 }
426 }
427 if (!proj && inCluster) {
428 proj = agsubg(g, agnameof(subg), 1);
429 }
430 if (proj) {
431 if (doEdges) nodeInduce(proj, subg);
432 agcopyattr(subg, proj);
433 }
434
435 return proj;
436 }
437
438 /* subgInduce:
439 * Project subgraphs of root graph on subgraph.
440 * If non-empty, add to subgraph.
441 */
442 static void
subgInduce(Agraph_t * root,Agraph_t * g,int inCluster)443 subgInduce(Agraph_t * root, Agraph_t * g, int inCluster)
444 {
445 Agraph_t *subg;
446 Agraph_t *proj;
447 int in_cluster;
448
449 /* fprintf (stderr, "subgInduce %s inCluster %d\n", agnameof(root), inCluster); */
450 for (subg = agfstsubg(root); subg; subg = agnxtsubg(subg)) {
451 if (GD_cc_subg(subg))
452 continue;
453 if ((proj = projectG(subg, g, inCluster))) {
454 in_cluster = inCluster || (useClusters && isCluster(subg));
455 subgInduce(subg, proj, in_cluster);
456 }
457 }
458 }
459
460 static void
subGInduce(Agraph_t * g,Agraph_t * out)461 subGInduce(Agraph_t* g, Agraph_t * out)
462 {
463 subgInduce(g, out, 0);
464 }
465
466 #define PFX1 "%s_cc"
467 #define PFX2 "%s_cc_%ld"
468
469 /* deriveClusters:
470 * Construct nodes in derived graph corresponding top-level clusters.
471 * Since a cluster might be wrapped in a subgraph, we need to traverse
472 * down into the tree of subgraphs
473 */
deriveClusters(Agraph_t * dg,Agraph_t * g)474 static void deriveClusters(Agraph_t* dg, Agraph_t * g)
475 {
476 Agraph_t *subg;
477 Agnode_t *dn;
478 Agnode_t *n;
479
480 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
481 if (!strncmp(agnameof(subg), "cluster", 7)) {
482 dn = agnode(dg, agnameof(subg), 1);
483 agbindrec (dn, "nodeinfo", sizeof(Agnodeinfo_t), TRUE);
484 ND_ptr(dn) = (Agobj_t*)subg;
485 for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
486 if (ND_ptr(n)) {
487 fprintf (stderr, "Error: node \"%s\" belongs to two non-nested clusters \"%s\" and \"%s\"\n",
488 agnameof (n), agnameof(subg), agnameof(ND_dn(n)));
489 }
490 ND_ptr(n) = (Agobj_t*)dn;
491 }
492 }
493 else {
494 deriveClusters (dg, subg);
495 }
496 }
497 }
498
499 /* deriveGraph:
500 * Create derived graph dg of g where nodes correspond to top-level nodes
501 * or clusters, and there is an edge in dg if there is an edge in g
502 * between any nodes in the respective clusters.
503 */
deriveGraph(Agraph_t * g)504 static Agraph_t *deriveGraph(Agraph_t * g)
505 {
506 Agraph_t *dg;
507 Agnode_t *dn;
508 Agnode_t *n;
509
510 dg = agopen("dg", Agstrictundirected, (Agdisc_t *) 0);
511
512 deriveClusters (dg, g);
513
514 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
515 if (ND_dn(n))
516 continue;
517 dn = agnode(dg, agnameof(n), 1);
518 agbindrec (dn, "nodeinfo", sizeof(Agnodeinfo_t), TRUE);
519 ND_ptr(dn) = (Agobj_t*)n;
520 ND_ptr(n) = (Agobj_t*)dn;
521 }
522
523 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
524 Agedge_t *e;
525 Agnode_t *hd;
526 Agnode_t *tl = ND_dn(n);
527 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
528 hd = ND_dn(aghead(e));
529 if (hd == tl)
530 continue;
531 if (hd > tl)
532 agedge(dg, tl, hd, 0, 1);
533 else
534 agedge(dg, hd, tl, 0, 1);
535 }
536 }
537
538 return dg;
539 }
540
541 /* unionNodes:
542 * Add all nodes in cluster nodes of dg to g
543 */
unionNodes(Agraph_t * dg,Agraph_t * g)544 static void unionNodes(Agraph_t * dg, Agraph_t * g)
545 {
546 Agnode_t *n;
547 Agnode_t *dn;
548 Agraph_t *clust;
549
550 for (dn = agfstnode(dg); dn; dn = agnxtnode(dg, dn)) {
551 if (AGTYPE(ND_ptr(dn)) == AGNODE) {
552 agsubnode(g, ND_dn(dn), 1);
553 } else {
554 clust = ND_clust(dn);
555 for (n = agfstnode(clust); n; n = agnxtnode(clust, n))
556 agsubnode(g, n, 1);
557 }
558 }
559 }
560
561 typedef int (*qsort_cmpf) (const void *, const void *);
562
cmp(Agraph_t ** p0,Agraph_t ** p1)563 static int cmp(Agraph_t** p0, Agraph_t** p1)
564 {
565 return (agnnodes(*p1) - agnnodes(*p0));
566 }
567
568 static void
printSorted(Agraph_t * root,int c_cnt)569 printSorted (Agraph_t* root, int c_cnt)
570 {
571 Agraph_t** ccs = N_NEW(c_cnt, Agraph_t*);
572 Agraph_t* subg;
573 int i = 0, endi;
574
575 for (subg = agfstsubg(root); subg; subg = agnxtsubg(subg)) {
576 if (GD_cc_subg(subg))
577 ccs[i++] = subg;
578 }
579 /* sort by component size, largest first */
580 qsort (ccs, c_cnt, sizeof(Agraph_t*), (qsort_cmpf)cmp);
581
582 if (sortIndex >= 0) {
583 if (x_mode == BY_INDEX) {
584 if (sortIndex >= c_cnt) {
585 fprintf(stderr,
586 "ccomps: component %d not found in graph %s - ignored\n",
587 sortIndex, agnameof(root));
588 return;
589 }
590 if (sortFinal >= sortIndex) {
591 endi = sortFinal;
592 if (endi >= c_cnt) endi = c_cnt-1;
593 }
594 else
595 endi = c_cnt-1;
596 for (i = sortIndex; i <= endi ; i++) {
597 subg = ccs[i];
598 if (doAll)
599 subGInduce(root, subg);
600 gwrite(subg);
601 }
602 }
603 else if (x_mode == BY_SIZE) {
604 if (sortFinal == -1)
605 sortFinal = agnnodes(ccs[0]);
606 for (i = 0; i < c_cnt ; i++) {
607 int sz;
608 subg = ccs[i];
609 sz = agnnodes(subg);
610 if (sz > sortFinal) continue;
611 if (sz < sortIndex) break;
612 if (doAll)
613 subGInduce(root, subg);
614 gwrite(subg);
615 }
616 }
617 }
618 else for (i = 0; i < c_cnt; i++) {
619 subg = ccs[i];
620 if (doAll)
621 subGInduce(root, subg);
622 gwrite(subg);
623 }
624 free (ccs);
625 }
626
627 /* processClusters:
628 * Return 0 if graph is connected.
629 */
processClusters(Agraph_t * g,char * graphName)630 static int processClusters(Agraph_t * g, char* graphName)
631 {
632 Agraph_t *dg;
633 long n_cnt, c_cnt, e_cnt;
634 char *name;
635 Agraph_t *out;
636 Agnode_t *n;
637 Agraph_t *dout;
638 Agnode_t *dn;
639 int extracted = 0;
640
641 dg = deriveGraph(g);
642
643 if (x_node) {
644 n = agfindnode(g, x_node);
645 if (!n) {
646 fprintf(stderr, "ccomps: node %s not found in graph %s\n",
647 x_node, agnameof(g));
648 return 1;
649 }
650 name = getBuf(sizeof(PFX1) + strlen(graphName));
651 sprintf(name, PFX1, graphName);
652 dout = agsubg(dg, name, 1);
653 out = agsubg(g, name, 1);
654 aginit(out, AGRAPH, "graphinfo", sizeof(Agraphinfo_t), TRUE);
655 GD_cc_subg(out) = 1;
656 dn = ND_dn(n);
657 n_cnt = dfs(dg, dn, dout);
658 unionNodes(dout, out);
659 if (doEdges)
660 e_cnt = nodeInduce(out, out->root);
661 else
662 e_cnt = 0;
663 if (doAll)
664 subGInduce(g, out);
665 gwrite(out);
666 if (verbose)
667 fprintf(stderr, " %7ld nodes %7ld edges\n", n_cnt, e_cnt);
668 return 0;
669 }
670
671 c_cnt = 0;
672 for (dn = agfstnode(dg); dn; dn = agnxtnode(dg, dn)) {
673 if (ND_mark(dn))
674 continue;
675 name = getBuf(sizeof(PFX2) + strlen(graphName) + 32);
676 sprintf(name, PFX2, graphName, c_cnt);
677 dout = agsubg(dg, name, 1);
678 out = agsubg(g, name, 1);
679 aginit(out, AGRAPH, "graphinfo", sizeof(Agraphinfo_t), TRUE);
680 GD_cc_subg(out) = 1;
681 n_cnt = dfs(dg, dn, dout);
682 unionNodes(dout, out);
683 if (doEdges)
684 e_cnt = nodeInduce(out, out->root);
685 else
686 e_cnt = 0;
687 if (printMode == EXTERNAL) {
688 if (doAll)
689 subGInduce(g, out);
690 gwrite(out);
691 } else if (printMode == EXTRACT) {
692 if (x_mode == BY_INDEX) {
693 if (x_index <= c_cnt) {
694 extracted = 1;
695 if (doAll)
696 subGInduce(g, out);
697 gwrite(out);
698 if (c_cnt == x_final)
699 return 0;
700 }
701 }
702 else if (x_mode == BY_SIZE) {
703 int sz = agnnodes(out);
704 if ((x_index <= sz) && ((x_final == -1) || (sz <= x_final))) {
705 extracted = 1;
706 if (doAll)
707 subGInduce(g, out);
708 gwrite(out);
709 }
710 }
711 }
712 if (printMode != INTERNAL)
713 agdelete(g, out);
714 agdelete(dg, dout);
715 if (verbose)
716 fprintf(stderr, "(%4ld) %7ld nodes %7ld edges\n",
717 c_cnt, n_cnt, e_cnt);
718 c_cnt++;
719 }
720 if ((printMode == EXTRACT) && !extracted && (x_mode == BY_INDEX)) {
721 fprintf(stderr,
722 "ccomps: component %d not found in graph %s - ignored\n",
723 x_index, agnameof(g));
724 return 1;
725 }
726
727 if (sorted)
728 printSorted (g, c_cnt);
729 else if (printMode == INTERNAL)
730 gwrite(g);
731
732 if (verbose)
733 fprintf(stderr, " %7d nodes %7d edges %7ld components %s\n",
734 agnnodes(g), agnedges(g), c_cnt, agnameof(g));
735
736 agclose(dg);
737
738 return (c_cnt ? 1 : 0);
739 }
740
741 static void
bindGraphinfo(Agraph_t * g)742 bindGraphinfo (Agraph_t * g)
743 {
744 Agraph_t *subg;
745
746 aginit(g, AGRAPH, "graphinfo", sizeof(Agraphinfo_t), TRUE);
747 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
748 bindGraphinfo (subg);
749 }
750 }
751
752 /* process:
753 * Return 0 if graph is connected.
754 */
process(Agraph_t * g,char * graphName)755 static int process(Agraph_t * g, char* graphName)
756 {
757 long n_cnt, c_cnt, e_cnt;
758 char *name;
759 Agraph_t *out;
760 Agnode_t *n;
761 int extracted = 0;
762
763 aginit(g, AGNODE, "nodeinfo", sizeof(Agnodeinfo_t), TRUE);
764 bindGraphinfo (g);
765 initStk();
766
767 if (useClusters)
768 return processClusters(g, graphName);
769
770 if (x_node) {
771 n = agfindnode(g, x_node);
772 if (!n) {
773 fprintf(stderr,
774 "ccomps: node %s not found in graph %s - ignored\n",
775 x_node, agnameof(g));
776 return 1;
777 }
778 name = getBuf(sizeof(PFX1) + strlen(graphName));
779 sprintf(name, PFX1, graphName);
780 out = agsubg(g, name, 1);
781 aginit(out, AGRAPH, "graphinfo", sizeof(Agraphinfo_t), TRUE);
782 GD_cc_subg(out) = 1;
783 n_cnt = dfs(g, n, out);
784 if (doEdges)
785 e_cnt = nodeInduce(out, out->root);
786 else
787 e_cnt = 0;
788 if (doAll)
789 subGInduce(g, out);
790 gwrite(out);
791 if (verbose)
792 fprintf(stderr, " %7ld nodes %7ld edges\n", n_cnt, e_cnt);
793 return 0;
794 }
795
796 c_cnt = 0;
797 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
798 if (ND_mark(n))
799 continue;
800 name = getBuf(sizeof(PFX2) + strlen(graphName) + 32);
801 sprintf(name, PFX2, graphName, c_cnt);
802 out = agsubg(g, name, 1);
803 aginit(out, AGRAPH, "graphinfo", sizeof(Agraphinfo_t), TRUE);
804 GD_cc_subg(out) = 1;
805 n_cnt = dfs(g, n, out);
806 if (doEdges)
807 e_cnt = nodeInduce(out, out->root);
808 else
809 e_cnt = 0;
810 if (printMode == EXTERNAL) {
811 if (doAll)
812 subGInduce(g, out);
813 gwrite(out);
814 } else if (printMode == EXTRACT) {
815 if (x_mode == BY_INDEX) {
816 if (x_index <= c_cnt) {
817 extracted = 1;
818 if (doAll)
819 subGInduce(g, out);
820 gwrite(out);
821 if (c_cnt == x_final)
822 return 0;
823 }
824 }
825 else if (x_mode == BY_SIZE) {
826 int sz = agnnodes(out);
827 if ((x_index <= sz) && ((x_final == -1) || (sz <= x_final))) {
828 extracted = 1;
829 if (doAll)
830 subGInduce(g, out);
831 gwrite(out);
832 }
833 }
834 }
835 if (printMode != INTERNAL)
836 agdelete(g, out);
837 if (verbose)
838 fprintf(stderr, "(%4ld) %7ld nodes %7ld edges\n",
839 c_cnt, n_cnt, e_cnt);
840 c_cnt++;
841 }
842 if ((printMode == EXTRACT) && !extracted && (x_mode == BY_INDEX)) {
843 fprintf(stderr,
844 "ccomps: component %d not found in graph %s - ignored\n",
845 x_index, agnameof(g));
846 return 1;
847 }
848
849 if (sorted)
850 printSorted (g, c_cnt);
851 else if (printMode == INTERNAL)
852 gwrite(g);
853
854 if (verbose)
855 fprintf(stderr, " %7d nodes %7d edges %7ld components %s\n",
856 agnnodes(g), agnedges(g), c_cnt, agnameof(g));
857 return (c_cnt > 1);
858 }
859
gread(FILE * fp)860 static Agraph_t *gread(FILE * fp)
861 {
862 return agread(fp, (Agdisc_t *) 0);
863 }
864
865 /* chkGraphName:
866 * If the graph is anonymous, its name starts with '%'.
867 * If we use this as the prefix for subgraphs, they will not be
868 * emitted in agwrite() because cgraph assumes these were anonymous
869 * structural subgraphs all of whose properties are attached directly
870 * to the nodes and edges involved.
871 *
872 * This function checks for an initial '%' and if found, prepends '_'
873 * the the graph name.
874 * NB: static buffer is used.
875 */
876 static char*
chkGraphName(Agraph_t * g)877 chkGraphName (Agraph_t* g)
878 {
879 static char* buf = NULL;
880 static int buflen = 0;
881 char* s = agnameof(g);
882 int len;
883
884 if (*s != '%') return s;
885 len = strlen(s) + 2; /* plus '\0' and '_' */
886 if (len > buflen) {
887 buf = realloc (buf, len);
888 buflen = len;
889 }
890 buf[0] = '_';
891 strcpy (buf+1, s);
892
893 return buf;
894 }
895
main(int argc,char * argv[])896 int main(int argc, char *argv[])
897 {
898 Agraph_t *g;
899 ingraph_state ig;
900 int r = 0;
901 init(argc, argv);
902 newIngraph(&ig, Files, gread);
903
904 while ((g = nextGraph(&ig)) != 0) {
905 r += process(g, chkGraphName(g));
906 agclose(g);
907 }
908
909 return r;
910 }
911