Graphviz 13.1.3~dev.20250905.1412
Loading...
Searching...
No Matches
ccomps.c
Go to the documentation of this file.
1
6/*************************************************************************
7 * Copyright (c) 2011 AT&T Intellectual Property
8 * All rights reserved. This program and the accompanying materials
9 * are made available under the terms of the Eclipse Public License v1.0
10 * which accompanies this distribution, and is available at
11 * https://www.eclipse.org/legal/epl-v10.html
12 *
13 * Contributors: Details at https://graphviz.org
14 *************************************************************************/
15
16/*
17 * Written by Stephen North
18 * Updated by Emden Gansner
19 */
20
21#include <assert.h>
22#include <cgraph/cgraph.h>
23#include <cgraph/ingraphs.h>
24#include <common/render.h>
25#include <common/utils.h>
26#include <getopt.h>
27#include <stdbool.h>
28#include <stdio.h>
29#include <stdlib.h>
30#include <string.h>
31#include <util/agxbuf.h>
32#include <util/alloc.h>
33#include <util/exit.h>
34#include <util/gv_ctype.h>
35#include <util/list.h>
36#include <util/prisize_t.h>
37#include <util/strview.h>
38#include <util/unreachable.h>
39
40typedef struct {
42 bool cc_subg;
44
45typedef struct {
47 char mark;
50
51#define GD_cc_subg(g) (((graphinfo_t *)(g->base.data))->cc_subg)
52#define Node_mark(n) (((nodeinfo_t *)(n->base.data))->mark)
53#define ND_ptr(n) (((nodeinfo_t *)(n->base.data))->ptr)
54#define ND_dn(n) ((Agnode_t *)ND_ptr(n))
55#define Node_clust(n) ((Agraph_t *)ND_ptr(n))
56
57static char **Inputs;
58static bool verbose = false;
59static enum {
65static bool useClusters = false;
66static bool doEdges = true;
67static bool doAll = true;
68static char *suffix = 0;
69static char *outfile = 0;
71static int sufcnt = 0;
72static bool sorted = false;
73static int sortIndex = 0;
74static int sortFinal;
75static int x_index = -1;
76static int x_final = -1; // require 0 <= x_index <= x_final or x_final= -1
77static enum { BY_INDEX = 1, BY_SIZE = 2 } x_mode;
78static char *x_node;
79
80static char *useString =
81 "Usage: ccomps [-svenCx?] [-X[#%]s[-f]] [-o<out template>] <files>\n\
82 -s - silent\n\
83 -x - external\n\
84 -X - extract component\n\
85 -C - use clusters\n\
86 -e - do not induce edges\n\
87 -n - do not induce subgraphs\n\
88 -v - verbose\n\
89 -o - output file template\n\
90 -z - sort by size, largest first\n\
91 -? - print usage\n\
92If no files are specified, stdin is used\n";
93
94static void usage(int v) {
95 printf("%s", useString);
97}
98
99static void split(void) {
100 char *sfx = strrchr(outfile, '.');
101 if (sfx) {
102 suffix = sfx + 1;
103 size_t size = (size_t)(sfx - outfile);
104 rootpath = (strview_t){.data = outfile, .size = size};
105 } else {
106 rootpath = strview(outfile, '\0');
107 }
108}
109
110static void init(int argc, char *argv[]) {
111 int c;
112 char *endp;
113
114 opterr = 0;
115 while ((c = getopt(argc, argv, ":zo:xCX:nesv?")) != -1) {
116 switch (c) {
117 case 'o':
118 outfile = optarg;
119 split();
120 break;
121 case 'C':
122 useClusters = true;
123 break;
124 case 'e':
125 doEdges = false;
126 break;
127 case 'n':
128 doAll = false;
129 break;
130 case 'x':
132 break;
133 case 's':
135 break;
136 case 'X':
137 if (*optarg == '#' || *optarg == '%') {
138 char *p = optarg + 1;
139 if (*optarg == '#')
141 else
142 x_mode = BY_SIZE;
143 if (gv_isdigit(*p)) {
144 x_index = (int)strtol(p, &endp, 10);
146 if (*endp == '-') {
147 p = endp + 1;
148 if (gv_isdigit(*p)) {
149 x_final = atoi(p);
150 if (x_final < x_index) {
152 fprintf(stderr,
153 "ccomps: final index %d < start index %d in -X%s flag "
154 "- ignored\n",
155 x_final, x_index, optarg);
156 }
157 } else if (*p) {
159 fprintf(stderr,
160 "ccomps: number expected in -X%s flag - ignored\n",
161 optarg);
162 }
163 } else
165 } else
166 fprintf(stderr, "ccomps: number expected in -X%s flag - ignored\n",
167 optarg);
168 } else {
169 x_node = optarg;
171 }
172 break;
173 case 'v':
174 verbose = true;
175 break;
176 case 'z':
177 sorted = true;
178 break;
179 case ':':
180 fprintf(stderr, "ccomps: option -%c missing argument - ignored\n",
181 optopt);
182 break;
183 case '?':
184 if (optopt == '\0' || optopt == '?')
185 usage(0);
186 else {
187 fprintf(stderr, "ccomps: option -%c unrecognized\n", optopt);
188 usage(1);
189 }
190 break;
191 default:
192 UNREACHABLE();
193 }
194 }
195 argv += optind;
196 argc -= optind;
197
198 if (sorted) {
199 if (printMode == EXTRACT && x_index >= 0) {
203 } else if (printMode == EXTERNAL) {
204 sortIndex = -1;
206 } else
207 sorted = false; // not relevant; turn off
208 }
209 if (argc > 0)
210 Inputs = argv;
211}
212
213static LIST(Agnode_t *) Stk;
214
215static void push(Agnode_t *np) {
216 Node_mark(np) = -1;
217 LIST_PUSH_BACK(&Stk, np);
218}
219
220static Agnode_t *pop(void) {
221 if (LIST_IS_EMPTY(&Stk)) {
222 return NULL;
223 }
224 return LIST_POP_BACK(&Stk);
225}
226
227static int dfs(Agraph_t *g, Agnode_t *n, Agraph_t *out) {
228 Agnode_t *other;
229 int cnt = 0;
230
231 push(n);
232 while ((n = pop())) {
233 Node_mark(n) = 1;
234 cnt++;
235 agsubnode(out, n, 1);
236 for (Agedge_t *e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
237 if ((other = agtail(e)) == n)
238 other = aghead(e);
239 if (Node_mark(other) == 0)
240 push(other);
241 }
242 }
243 return cnt;
244}
245
246static char *getName(void) {
247 agxbuf name = {0};
248
249 if (sufcnt == 0)
250 agxbput(&name, outfile);
251 else {
252 if (suffix)
253 agxbprint(&name, "%.*s_%d.%s", (int)rootpath.size, rootpath.data, sufcnt,
254 suffix);
255 else
256 agxbprint(&name, "%.*s_%d", (int)rootpath.size, rootpath.data, sufcnt);
257 }
258 sufcnt++;
259 return agxbdisown(&name);
260}
261
262static void gwrite(Agraph_t *g) {
263 if (!outfile) {
264 agwrite(g, stdout);
265 fflush(stdout);
266 } else {
267 char *const name = getName();
268 FILE *const outf = fopen(name, "w");
269 if (!outf) {
270 fprintf(stderr, "Could not open %s for writing\n", name);
271 perror("ccomps");
272 free(name);
273 graphviz_exit(EXIT_FAILURE);
274 }
275 free(name);
276 agwrite(g, outf);
277 fclose(outf);
278 }
279}
280
281/* If any nodes of subg are in g, create a subgraph of g
282 * and fill it with all nodes of subg in g and their induced
283 * edges in subg. Copy the attributes of subg to g. Return the subgraph.
284 * If not, return null.
285 */
286static Agraph_t *projectG(Agraph_t *subg, Agraph_t *g, int inCluster) {
287 Agraph_t *proj = 0;
288 Agnode_t *m;
289
290 for (Agnode_t *n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
291 if ((m = agfindnode(g, agnameof(n)))) {
292 if (proj == 0) {
293 proj = agsubg(g, agnameof(subg), 1);
294 }
295 agsubnode(proj, m, 1);
296 }
297 }
298 if (!proj && inCluster) {
299 proj = agsubg(g, agnameof(subg), 1);
300 }
301 if (proj) {
302 if (doEdges)
303 (void)graphviz_node_induce(proj, subg);
304 agcopyattr(subg, proj);
305 }
306
307 return proj;
308}
309
310/* Project subgraphs of root graph on subgraph.
311 * If non-empty, add to subgraph.
312 */
313static void subgInduce(Agraph_t *root, Agraph_t *g, int inCluster) {
314 Agraph_t *proj;
315
316 for (Agraph_t *subg = agfstsubg(root); subg; subg = agnxtsubg(subg)) {
317 if (GD_cc_subg(subg))
318 continue;
319 if ((proj = projectG(subg, g, inCluster))) {
320 const int in_cluster = inCluster || (useClusters && is_a_cluster(subg));
321 subgInduce(subg, proj, in_cluster);
322 }
323 }
324}
325
326static void subGInduce(Agraph_t *g, Agraph_t *out) { subgInduce(g, out, 0); }
327
328#define PFX1 "%s_cc"
329#define PFX2 "%s_cc_%" PRISIZE_T
330
331/* Construct nodes in derived graph corresponding top-level clusters.
332 * Since a cluster might be wrapped in a subgraph, we need to traverse
333 * down into the tree of subgraphs
334 */
335static void deriveClusters(Agraph_t *dg, Agraph_t *g) {
336 for (Agraph_t *subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
337 if (is_a_cluster(subg)) {
338 Agnode_t *const dn = agnode(dg, agnameof(subg), 1);
339 agbindrec(dn, "nodeinfo", sizeof(nodeinfo_t), true);
340 ND_ptr(dn) = (Agobj_t *)subg;
341 for (Agnode_t *n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
342 if (ND_ptr(n)) {
343 fprintf(stderr,
344 "Error: node \"%s\" belongs to two non-nested clusters "
345 "\"%s\" and \"%s\"\n",
346 agnameof(n), agnameof(subg), agnameof(ND_dn(n)));
347 }
348 ND_ptr(n) = (Agobj_t *)dn;
349 }
350 } else {
351 deriveClusters(dg, subg);
352 }
353 }
354}
355
356/* Create derived graph dg of g where nodes correspond to top-level nodes
357 * or clusters, and there is an edge in dg if there is an edge in g
358 * between any nodes in the respective clusters.
359 */
362
363 deriveClusters(dg, g);
364
365 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
366 if (ND_dn(n))
367 continue;
368 Agnode_t *const dn = agnode(dg, agnameof(n), 1);
369 agbindrec(dn, "nodeinfo", sizeof(nodeinfo_t), true);
370 ND_ptr(dn) = (Agobj_t *)n;
371 ND_ptr(n) = (Agobj_t *)dn;
372 }
373
374 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
375 Agnode_t *tl = ND_dn(n);
376 for (Agedge_t *e = agfstout(g, n); e; e = agnxtout(g, e)) {
377 Agnode_t *const hd = ND_dn(aghead(e));
378 if (hd == tl)
379 continue;
380 if (hd > tl)
381 agedge(dg, tl, hd, 0, 1);
382 else
383 agedge(dg, hd, tl, 0, 1);
384 }
385 }
386
387 return dg;
388}
389
391static void unionNodes(Agraph_t *dg, Agraph_t *g) {
392 for (Agnode_t *dn = agfstnode(dg); dn; dn = agnxtnode(dg, dn)) {
393 if (AGTYPE(ND_ptr(dn)) == AGNODE) {
394 agsubnode(g, ND_dn(dn), 1);
395 } else {
396 Agraph_t *const clust = Node_clust(dn);
397 for (Agnode_t *n = agfstnode(clust); n; n = agnxtnode(clust, n))
398 agsubnode(g, n, 1);
399 }
400 }
401}
402
403static int cmp(const void *x, const void *y) {
404// Suppress Clang/GCC -Wcast-qual warning. Casting away const here is acceptable
405// as the later usage is const. We need the cast because `agnnodes` uses
406// non-const pointers.
407#ifdef __GNUC__
408#pragma GCC diagnostic push
409#pragma GCC diagnostic ignored "-Wcast-qual"
410#endif
411 Agraph_t **p0 = (Agraph_t **)x;
412 Agraph_t **p1 = (Agraph_t **)y;
413#ifdef __GNUC__
414#pragma GCC diagnostic pop
415#endif
416 const int n0 = agnnodes(*p0);
417 const int n1 = agnnodes(*p1);
418 if (n0 < n1) {
419 return 1;
420 }
421 if (n0 > n1) {
422 return -1;
423 }
424 return 0;
425}
426
427static void printSorted(Agraph_t *root, size_t c_cnt) {
428 Agraph_t **ccs = gv_calloc(c_cnt, sizeof(Agraph_t *));
429 size_t i = 0;
430
431 for (Agraph_t *subg = agfstsubg(root); subg; subg = agnxtsubg(subg)) {
432 if (GD_cc_subg(subg))
433 ccs[i++] = subg;
434 }
435 /* sort by component size, largest first */
436 qsort(ccs, c_cnt, sizeof(Agraph_t *), cmp);
437
438 if (sortIndex >= 0) {
439 if (x_mode == BY_INDEX) {
440 if ((size_t)sortIndex >= c_cnt) {
441 fprintf(stderr,
442 "ccomps: component %d not found in graph %s - ignored\n",
443 sortIndex, agnameof(root));
444 free(ccs);
445 return;
446 }
447 size_t endi;
448 if (sortFinal >= sortIndex) {
449 endi = (size_t)sortFinal;
450 if (endi >= c_cnt) {
451 assert(c_cnt > 0);
452 endi = c_cnt - 1;
453 }
454 } else
455 endi = c_cnt - 1;
456 for (i = (size_t)sortIndex; i <= endi; i++) {
457 Agraph_t *const subg = ccs[i];
458 if (doAll)
459 subGInduce(root, subg);
460 gwrite(subg);
461 }
462 } else if (x_mode == BY_SIZE) {
463 if (sortFinal == -1)
464 sortFinal = agnnodes(ccs[0]);
465 for (i = 0; i < c_cnt; i++) {
466 Agraph_t *const subg = ccs[i];
467 int sz = agnnodes(subg);
468 if (sz > sortFinal)
469 continue;
470 if (sz < sortIndex)
471 break;
472 if (doAll)
473 subGInduce(root, subg);
474 gwrite(subg);
475 }
476 }
477 } else
478 for (i = 0; i < c_cnt; i++) {
479 Agraph_t *const subg = ccs[i];
480 if (doAll)
481 subGInduce(root, subg);
482 gwrite(subg);
483 }
484 free(ccs);
485}
486
488static int processClusters(Agraph_t *g, char *graphName) {
489 Agraph_t *out;
490 Agraph_t *dout;
491 bool extracted = false;
492
493 Agraph_t *const dg = deriveGraph(g);
494
495 if (x_node) {
496 Agnode_t *const n = agfindnode(g, x_node);
497 if (!n) {
498 fprintf(stderr, "ccomps: node %s not found in graph %s\n", x_node,
499 agnameof(g));
500 return 1;
501 }
502 {
503 agxbuf buf = {0};
504 agxbprint(&buf, PFX1, graphName);
505 char *name = agxbuse(&buf);
506 dout = agsubg(dg, name, 1);
507 out = agsubg(g, name, 1);
508 agxbfree(&buf);
509 }
510 aginit(out, AGRAPH, "graphinfo", sizeof(graphinfo_t), true);
511 GD_cc_subg(out) = true;
512 Agnode_t *const dn = ND_dn(n);
513 const long n_cnt = dfs(dg, dn, dout);
514 unionNodes(dout, out);
515 size_t e_cnt = 0;
516 if (doEdges)
517 e_cnt = graphviz_node_induce(out, out->root);
518 if (doAll)
519 subGInduce(g, out);
520 gwrite(out);
521 if (verbose)
522 fprintf(stderr, " %7ld nodes %7" PRISIZE_T " edges\n", n_cnt, e_cnt);
523 return 0;
524 }
525
526 size_t c_cnt = 0;
527 for (Agnode_t *dn = agfstnode(dg); dn; dn = agnxtnode(dg, dn)) {
528 if (Node_mark(dn))
529 continue;
530 {
531 agxbuf buf = {0};
532 agxbprint(&buf, PFX2, graphName, c_cnt);
533 char *name = agxbuse(&buf);
534 dout = agsubg(dg, name, 1);
535 out = agsubg(g, name, 1);
536 agxbfree(&buf);
537 }
538 aginit(out, AGRAPH, "graphinfo", sizeof(graphinfo_t), true);
539 GD_cc_subg(out) = true;
540 const long n_cnt = dfs(dg, dn, dout);
541 unionNodes(dout, out);
542 size_t e_cnt = 0;
543 if (doEdges)
544 e_cnt = graphviz_node_induce(out, out->root);
545 if (printMode == EXTERNAL) {
546 if (doAll)
547 subGInduce(g, out);
548 gwrite(out);
549 } else if (printMode == EXTRACT) {
550 if (x_mode == BY_INDEX) {
551 if (x_index < 0 || (size_t)x_index <= c_cnt) {
552 extracted = true;
553 if (doAll)
554 subGInduce(g, out);
555 gwrite(out);
556 if (x_final >= 0 && c_cnt == (size_t)x_final)
557 return 0;
558 }
559 } else if (x_mode == BY_SIZE) {
560 int sz = agnnodes(out);
561 if (x_index <= sz && (x_final == -1 || sz <= x_final)) {
562 extracted = true;
563 if (doAll)
564 subGInduce(g, out);
565 gwrite(out);
566 }
567 }
568 }
569 if (printMode != INTERNAL)
570 agdelete(g, out);
571 agdelete(dg, dout);
572 if (verbose)
573 fprintf(stderr, "(%4" PRISIZE_T ") %7ld nodes %7" PRISIZE_T " edges\n",
574 c_cnt, n_cnt, e_cnt);
575 c_cnt++;
576 }
577 if (printMode == EXTRACT && !extracted && x_mode == BY_INDEX) {
578 fprintf(stderr, "ccomps: component %d not found in graph %s - ignored\n",
579 x_index, agnameof(g));
580 return 1;
581 }
582
583 if (sorted)
584 printSorted(g, c_cnt);
585 else if (printMode == INTERNAL)
586 gwrite(g);
587
588 if (verbose)
589 fprintf(stderr,
590 " %7d nodes %7d edges %7" PRISIZE_T " components %s\n",
591 agnnodes(g), agnedges(g), c_cnt, agnameof(g));
592
593 agclose(dg);
594
595 return c_cnt ? 1 : 0;
596}
597
598static void bindGraphinfo(Agraph_t *g) {
599 aginit(g, AGRAPH, "graphinfo", sizeof(graphinfo_t), true);
600 for (Agraph_t *subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
601 bindGraphinfo(subg);
602 }
603}
604
606static int process(Agraph_t *g, char *graphName) {
607 Agraph_t *out;
608 bool extracted = false;
609
610 aginit(g, AGNODE, "nodeinfo", sizeof(nodeinfo_t), true);
611 bindGraphinfo(g);
612
613 if (useClusters)
614 return processClusters(g, graphName);
615
616 if (x_node) {
617 Agnode_t *const n = agfindnode(g, x_node);
618 if (!n) {
619 fprintf(stderr, "ccomps: node %s not found in graph %s - ignored\n",
620 x_node, agnameof(g));
621 return 1;
622 }
623 {
624 agxbuf name = {0};
625 agxbprint(&name, PFX1, graphName);
626 out = agsubg(g, agxbuse(&name), 1);
627 agxbfree(&name);
628 }
629 aginit(out, AGRAPH, "graphinfo", sizeof(graphinfo_t), true);
630 GD_cc_subg(out) = true;
631 const long n_cnt = dfs(g, n, out);
632 size_t e_cnt = 0;
633 if (doEdges)
634 e_cnt = graphviz_node_induce(out, out->root);
635 if (doAll)
636 subGInduce(g, out);
637 gwrite(out);
638 if (verbose)
639 fprintf(stderr, " %7ld nodes %7" PRISIZE_T " edges\n", n_cnt, e_cnt);
640 return 0;
641 }
642
643 size_t c_cnt = 0;
644 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
645 if (Node_mark(n))
646 continue;
647 {
648 agxbuf name = {0};
649 agxbprint(&name, PFX2, graphName, c_cnt);
650 out = agsubg(g, agxbuse(&name), 1);
651 agxbfree(&name);
652 }
653 aginit(out, AGRAPH, "graphinfo", sizeof(graphinfo_t), true);
654 GD_cc_subg(out) = true;
655 const long n_cnt = dfs(g, n, out);
656 size_t e_cnt = 0;
657 if (doEdges)
658 e_cnt = graphviz_node_induce(out, out->root);
659 if (printMode == EXTERNAL) {
660 if (doAll)
661 subGInduce(g, out);
662 gwrite(out);
663 } else if (printMode == EXTRACT) {
664 if (x_mode == BY_INDEX) {
665 if (x_index < 0 || (size_t)x_index <= c_cnt) {
666 extracted = true;
667 if (doAll)
668 subGInduce(g, out);
669 gwrite(out);
670 if (x_final >= 0 && c_cnt == (size_t)x_final)
671 return 0;
672 }
673 } else if (x_mode == BY_SIZE) {
674 int sz = agnnodes(out);
675 if (x_index <= sz && (x_final == -1 || sz <= x_final)) {
676 extracted = true;
677 if (doAll)
678 subGInduce(g, out);
679 gwrite(out);
680 }
681 }
682 }
683 if (printMode != INTERNAL)
684 agdelete(g, out);
685 if (verbose)
686 fprintf(stderr, "(%4" PRISIZE_T ") %7ld nodes %7" PRISIZE_T " edges\n",
687 c_cnt, n_cnt, e_cnt);
688 c_cnt++;
689 }
690 if (printMode == EXTRACT && !extracted && x_mode == BY_INDEX) {
691 fprintf(stderr, "ccomps: component %d not found in graph %s - ignored\n",
692 x_index, agnameof(g));
693 return 1;
694 }
695
696 if (sorted)
697 printSorted(g, c_cnt);
698 else if (printMode == INTERNAL)
699 gwrite(g);
700
701 if (verbose)
702 fprintf(stderr,
703 " %7d nodes %7d edges %7" PRISIZE_T " components %s\n",
704 agnnodes(g), agnedges(g), c_cnt, agnameof(g));
705 return c_cnt > 1;
706}
707
708/* If the graph is anonymous, its name starts with '%'.
709 * If we use this as the prefix for subgraphs, they will not be
710 * emitted in agwrite() because cgraph assumes these were anonymous
711 * structural subgraphs all of whose properties are attached directly
712 * to the nodes and edges involved.
713 *
714 * This function checks for an initial '%' and if found, prepends '_'
715 * to the graph name.
716 * NB: static buffer is used.
717 */
718static char *chkGraphName(Agraph_t *g) {
719 static agxbuf buf;
720 char *s = agnameof(g);
721
722 if (*s != '%')
723 return s;
724 agxbprint(&buf, "_%s", s);
725
726 return agxbuse(&buf);
727}
728
729int main(int argc, char *argv[]) {
730 Agraph_t *g;
731 ingraph_state ig;
732 int r = 0;
733 init(argc, argv);
734 newIngraph(&ig, Inputs);
735
736 while ((g = nextGraph(&ig)) != 0) {
737 r += process(g, chkGraphName(g));
738 agclose(g);
739 }
740
741 LIST_FREE(&Stk);
742
743 graphviz_exit(r);
744}
static void out(agerrlevel_t level, const char *fmt, va_list args)
Report messages using a user-supplied or default write function.
Definition agerror.c:84
static void agxbfree(agxbuf *xb)
free any malloced resources
Definition agxbuf.h:77
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
Definition agxbuf.h:233
static WUR char * agxbuse(agxbuf *xb)
Definition agxbuf.h:306
static char * agxbdisown(agxbuf *xb)
Definition agxbuf.h:326
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
abstract graph C library, Cgraph API
#define graphName(g)
Definition acyclic.c:32
static void init(int argc, char *argv[])
Definition ccomps.c:110
static char ** Inputs
Definition ccomps.c:57
#define ND_dn(n)
Definition ccomps.c:54
static enum @57 printMode
static int processClusters(Agraph_t *g, char *graphName)
return 0 if graph is connected
Definition ccomps.c:488
static char * x_node
Definition ccomps.c:78
static int process(Agraph_t *g, char *graphName)
return 0 if graph is connected
Definition ccomps.c:606
static void gwrite(Agraph_t *g)
Definition ccomps.c:262
static bool doEdges
induce edges
Definition ccomps.c:66
#define ND_ptr(n)
Definition ccomps.c:53
static void split(void)
Definition ccomps.c:99
static char * suffix
Definition ccomps.c:68
static Agnode_t * pop(void)
Definition ccomps.c:220
static void deriveClusters(Agraph_t *dg, Agraph_t *g)
Definition ccomps.c:335
static Agraph_t * deriveGraph(Agraph_t *g)
Definition ccomps.c:360
static int sortIndex
Definition ccomps.c:73
static int sortFinal
Definition ccomps.c:74
static int cmp(const void *x, const void *y)
Definition ccomps.c:403
static void unionNodes(Agraph_t *dg, Agraph_t *g)
add all nodes in cluster nodes of dg to g
Definition ccomps.c:391
#define Node_clust(n)
Definition ccomps.c:55
static Agraph_t * projectG(Agraph_t *subg, Agraph_t *g, int inCluster)
Definition ccomps.c:286
#define Node_mark(n)
Definition ccomps.c:52
static char * getName(void)
Definition ccomps.c:246
static void subGInduce(Agraph_t *g, Agraph_t *out)
Definition ccomps.c:326
static void printSorted(Agraph_t *root, size_t c_cnt)
Definition ccomps.c:427
static void subgInduce(Agraph_t *root, Agraph_t *g, int inCluster)
Definition ccomps.c:313
static char * chkGraphName(Agraph_t *g)
Definition ccomps.c:718
static int dfs(Agraph_t *g, Agnode_t *n, Agraph_t *out)
Definition ccomps.c:227
static bool verbose
Definition ccomps.c:58
static int x_final
Definition ccomps.c:76
static char * useString
Definition ccomps.c:80
static char * outfile
Definition ccomps.c:69
static strview_t rootpath
Definition ccomps.c:70
static bool useClusters
Definition ccomps.c:65
static void bindGraphinfo(Agraph_t *g)
Definition ccomps.c:598
@ BY_SIZE
Definition ccomps.c:77
@ BY_INDEX
Definition ccomps.c:77
static int x_index
Definition ccomps.c:75
static enum @58 x_mode
#define PFX2
Definition ccomps.c:329
static int sufcnt
Definition ccomps.c:71
static bool doAll
induce subgraphs
Definition ccomps.c:67
#define PFX1
Definition ccomps.c:328
static bool sorted
Definition ccomps.c:72
@ EXTERNAL
Definition ccomps.c:61
@ SILENT
Definition ccomps.c:62
@ EXTRACT
Definition ccomps.c:63
@ INTERNAL
all components need to be generated before output
Definition ccomps.c:60
#define GD_cc_subg(g)
Definition ccomps.c:51
bool is_a_cluster(Agraph_t *g)
Definition utils.c:694
static NORETURN void graphviz_exit(int status)
Definition exit.h:23
void free(void *)
static gstack_t * push(gstack_t *s, Agraph_t *subg)
Definition grammar.c:1655
node NULL
Definition grammar.y:181
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:196
int agnedges(Agraph_t *g)
Definition graph.c:161
int agnnodes(Agraph_t *g)
Definition graph.c:155
size_t graphviz_node_induce(Agraph_t *g, Agraph_t *edgeset)
Definition node_induce.c:9
int agcopyattr(void *oldobj, void *newobj)
copies all of the attributes from one object to another
Definition attr.c:633
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition edge.c:253
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
#define agtail(e)
Definition cgraph.h:988
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition edge.c:96
#define aghead(e)
Definition cgraph.h:989
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition edge.c:87
Agdesc_t Agstrictundirected
strict undirected
Definition graph.c:273
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Definition graph.c:95
Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
creates a new graph with the given name and kind
Definition graph.c:42
int agwrite(Agraph_t *g, void *chan)
Return 0 on success, EOF on failure.
Definition write.c:696
Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition node.c:141
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition node.c:252
#define agfindnode(g, n)
Definition types.h:611
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
#define AGTYPE(obj)
returns AGRAPH, AGNODE, or AGEDGE depending on the type of the object
Definition cgraph.h:216
int agdelete(Agraph_t *g, void *obj)
deletes object. Equivalent to agclose, agdelnode, and agdeledge for obj being a graph,...
Definition obj.c:20
@ AGNODE
Definition cgraph.h:207
@ AGRAPH
Definition cgraph.h:207
void aginit(Agraph_t *g, int kind, const char *rec_name, int rec_size, int move_to_front)
attach new records to objects of specified kind
Definition rec.c:170
void * agbindrec(void *obj, const char *name, unsigned int recsize, int move_to_front)
attaches a new record of the given size to the object
Definition rec.c:89
Agraph_t * agfstsubg(Agraph_t *g)
Definition subg.c:73
Agraph_t * agnxtsubg(Agraph_t *subg)
Definition subg.c:78
Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition subg.c:53
replacements for ctype.h functions
static bool gv_isdigit(int c)
Definition gv_ctype.h:41
agxbput(xb, staging)
static const char * usage
Definition gvpr.c:51
Agraph_t * nextGraph(ingraph_state *sp)
Definition ingraphs.c:59
ingraph_state * newIngraph(ingraph_state *sp, char **files)
Definition ingraphs.c:138
supports user-supplied data
type-generic dynamically expanding list
#define LIST(type)
Definition list.h:55
#define LIST_FREE(list)
Definition list.h:379
#define LIST_POP_BACK(list)
Definition list.h:416
#define LIST_IS_EMPTY(list)
Definition list.h:90
#define LIST_PUSH_BACK(list, item)
Definition list.h:393
#define PRISIZE_T
Definition prisize_t.h:25
a generic header of Agraph_s, Agnode_s and Agedge_s
Definition cgraph.h:210
graph or subgraph
Definition cgraph.h:424
implementation of Agrec_t
Definition cgraph.h:172
Agrec_t h
Definition ccomps.c:41
bool cc_subg
true iff subgraph corresponds to a component
Definition ccomps.c:42
Agrec_t h
Definition ccomps.c:46
char mark
Definition ccomps.c:47
Agobj_t * ptr
Definition ccomps.c:48
a non-owning string reference
Definition strview.h:20
const char * data
start of the pointed to string
Definition strview.h:21
size_t size
extent of the string in bytes
Definition strview.h:22
Non-owning string references.
static strview_t strview(const char *referent, char terminator)
create a string reference
Definition strview.h:26
int main()
Definition grammar.c:90
#define UNREACHABLE()
Definition unreachable.h:30