Graphviz 13.1.3~dev.20250829.0113
Loading...
Searching...
No Matches
bcomps.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/*
18 * Generate biconnected components
19 *
20 * Written by Emden Gansner
21 */
22#include "config.h"
23
24#include <stdbool.h>
25#include <stdio.h>
26#include <string.h>
27#include <assert.h>
28#include <getopt.h>
29
30#include <stdlib.h>
31#include <cgraph/cgraph.h>
32#include <cgraph/ingraphs.h>
33#include <util/agxbuf.h>
34#include <util/alloc.h>
35#include <util/exit.h>
36#include <util/gv_math.h>
37#include <util/list.h>
38#include <util/unreachable.h>
39
40typedef struct {
44
45typedef struct {
48
49typedef struct {
51 int low;
52 int val;
53 int isCut;
55
56#define Low(n) (((Agnodeinfo_t*)(n->base.data))->low)
57#define Cut(n) (((Agnodeinfo_t*)(n->base.data))->isCut)
58#define N(n) (((Agnodeinfo_t*)(n->base.data))->val)
59#define NEXTBLK(g) (((Agraphinfo_t*)(g->base.data))->next)
60
61char **Files;
64char *outfile = 0;
65char *path = 0;
66char *suffix = 0;
67int external; /* emit blocks as root graphs */
68int doTree; /* emit block-cutpoint tree */
69
70typedef struct {
71 int count;
72 int nComp;
73 LIST(Agedge_t *) stk;
74 Agraph_t *blks;
75} bcstate;
76
77static char *blockName(agxbuf *xb, char *gname, int d) {
78 if (*gname == '%') /* anonymous graph */
79 agxbprint(xb, "_%s_bcc_%d", gname, d);
80 else
81 agxbprint(xb, "%s_bcc_%d", gname, d);
82 return agxbuse(xb);
83}
84
85/* getName:
86 * Generate name for output using input template.
87 * Has form path_<g>_<i>.suffix, for ith write for the gth graph.
88 * If isTree, use path_<g>_t.suffix.
89 * If sufcnt is zero and graph 0, use outfile
90 */
91static char *getName(int ng, int nb)
92{
93 agxbuf name = {0};
94
95 if (ng == 0 && nb == 0)
96 agxbput(&name, outfile);
97 else {
98 if (suffix) {
99 if (nb < 0)
100 agxbprint(&name, "%s_%d_T.%s", path, ng, suffix);
101 else
102 agxbprint(&name, "%s_%d_%d.%s", path, ng, nb, suffix);
103 } else {
104 if (nb < 0)
105 agxbprint(&name, "%s_%d_T", path, ng);
106 else
107 agxbprint(&name, "%s_%d_%d", path, ng, nb);
108 }
109 }
110 return agxbdisown(&name);
111}
112
113static void gwrite(Agraph_t * g, int ng, int nb)
114{
115 FILE *outf;
116 char *name;
117
118 if (silent)
119 return;
120 if (!outfile) {
121 agwrite(g, stdout);
122 fflush(stdout);
123 } else {
124 name = getName(ng, nb);
125 outf = fopen(name, "w");
126 if (!outf) {
127 fprintf(stderr, "Could not open %s for writing\n", name);
128 perror("bcomps");
129 free(name);
130 graphviz_exit(1);
131 }
132 free(name);
133 agwrite(g, outf);
134 fclose(outf);
135 }
136}
137
138static Agraph_t *mkBlock(Agraph_t * g, bcstate * stp)
139{
140 Agraph_t *sg;
141
142 stp->nComp++;
143 agxbuf xb = {0};
144 sg = agsubg(g, blockName(&xb, agnameof(g), stp->nComp), 1);
145 agxbfree(&xb);
146 agbindrec(sg, "info", sizeof(Agraphinfo_t), true);
147 NEXTBLK(sg) = stp->blks;
148 stp->blks = sg;
149 return sg;
150}
151
152static void
154{
155 Agnode_t *v;
156 Agedge_t *e;
157 Agedge_t *ep;
158 Agraph_t *sg;
159
160 stp->count++;
161 Low(u) = N(u) = stp->count;
162 for (e = agfstedge(g, u); e; e = agnxtedge(g, e, u)) {
163 if ((v = aghead(e)) == u)
164 v = agtail(e);
165 if (v == u)
166 continue;
167 if (N(v) == 0) {
168 LIST_PUSH_BACK(&stp->stk, e);
169 dfs(g, v, stp, u);
170 Low(u) = imin(Low(u), Low(v));
171 if (Low(v) >= N(u)) { /* u is an articulation point */
172 Cut(u) = 1;
173 sg = mkBlock(g, stp);
174 do {
175 ep = LIST_POP_BACK(&stp->stk);
176 agsubnode(sg, aghead(ep), 1);
177 agsubnode(sg, agtail(ep), 1);
178 } while (ep != e);
179 }
180 } else if (parent != v) {
181 Low(u) = imin(Low(u), N(v));
182 if (N(v) < N(u))
183 LIST_PUSH_BACK(&stp->stk, e);
184 }
185 }
186}
187
188static void addCutPts(Agraph_t * tree, Agraph_t * blk)
189{
190 Agnode_t *n;
191 Agnode_t *bn;
192 Agnode_t *cn;
193
194 bn = agnode(tree, agnameof(blk), 1);
195 for (n = agfstnode(blk); n; n = agnxtnode(blk, n)) {
196 if (Cut(n)) {
197 cn = agnode(tree, agnameof(n), 1);
198 agedge(tree, bn, cn, 0, 1);
199 }
200 }
201}
202
203static int process(Agraph_t * g, int gcnt)
204{
205 Agnode_t *n;
206 bcstate state = {0};
207 Agraph_t *blk;
208 Agraph_t *tree;
209 int bcnt;
210
211 aginit(g, AGNODE, "info", sizeof(Agnodeinfo_t), true);
212 aginit(g, AGEDGE, "info", sizeof(Agedgeinfo_t), true);
213 aginit(g, AGRAPH, "info", sizeof(Agraphinfo_t), true);
214
215 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
216 if (N(n) == 0)
217 dfs(g, n, &state, 0);
218 }
219 for (blk = state.blks; blk; blk = NEXTBLK(blk)) {
220 (void)graphviz_node_induce(blk, g);
221 }
222 if (external) {
223 bcnt = 0;
224 for (blk = state.blks; blk; blk = NEXTBLK(blk)) {
225 gwrite(blk, gcnt, bcnt++);
226 }
227 } else
228 gwrite(g, gcnt, 0);
229 if (doTree) {
230 tree = agopen("blkcut_tree", Agstrictundirected, 0);
231 for (blk = state.blks; blk; blk = NEXTBLK(blk))
232 addCutPts(tree, blk);
233 gwrite(tree, gcnt, -1);
234 agclose(tree);
235 }
236 if (verbose) {
237 int cuts = 0;
238 bcnt = 0;
239 for (blk = state.blks; blk; blk = NEXTBLK(blk))
240 bcnt++;
241 for (n = agfstnode(g); n; n = agnxtnode(g, n))
242 if (Cut(n))
243 cuts++;
244 fprintf(stderr, "%s: %d blocks %d cutpoints\n", agnameof(g), bcnt,
245 cuts);
246 }
247 LIST_FREE(&state.stk);
248 if (state.blks && NEXTBLK(state.blks))
249 return 1; /* >= 2 blocks */
250 else
251 return 0;
252}
253
254static char *useString =
255 "Usage: bcomps [-stvx?] [-o<out template>] <files>\n\
256 -o - output file template\n\
257 -s - don't print components\n\
258 -t - emit block-cutpoint tree\n\
259 -v - verbose\n\
260 -x - external\n\
261 -? - print usage\n\
262If no files are specified, stdin is used\n";
263
264static void usage(int v)
265{
266 printf("%s",useString);
267 graphviz_exit(v);
268}
269
270static void split(char *name)
271{
272 char *sfx = 0;
273
274 sfx = strrchr(name, '.');
275 if (sfx) {
276 size_t size = (size_t)(sfx - name);
277 suffix = sfx + 1;
278 path = gv_strndup(name, size);
279 } else {
280 path = name;
281 }
282}
283
284static void init(int argc, char *argv[])
285{
286 int c;
287
288 opterr = 0;
289 while ((c = getopt(argc, argv, ":o:xstv?")) != -1) {
290 switch (c) {
291 case 'o':
292 outfile = optarg;
293 split(outfile);
294 break;
295 case 's':
296 verbose = 1;
297 silent = 1;
298 break;
299 case 'v':
300 verbose = 1;
301 break;
302 case 't':
303 doTree = 1;
304 break;
305 case 'x':
306 external = 1;
307 break;
308 case ':':
309 fprintf(stderr, "bcomps: option -%c missing argument - ignored\n", optopt);
310 break;
311 case '?':
312 if (optopt == '\0' || optopt == '?')
313 usage(0);
314 else {
315 fprintf(stderr,
316 "bcomps: option -%c unrecognized\n", optopt);
317 usage(1);
318 }
319 break;
320 default:
321 UNREACHABLE();
322 }
323 }
324 argv += optind;
325 argc -= optind;
326
327 if (argc > 0)
328 Files = argv;
329}
330
331int main(int argc, char *argv[])
332{
333 Agraph_t *g;
334 ingraph_state ig;
335 int r = 0;
336 int gcnt = 0;
337
338 init(argc, argv);
339 newIngraph(&ig, Files);
340
341 while ((g = nextGraph(&ig)) != 0) {
342 r |= process(g, gcnt);
343 agclose(g);
344 gcnt++;
345 }
346
347 graphviz_exit(r);
348}
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 char * gv_strndup(const char *original, size_t length)
Definition alloc.h:114
int doTree
Definition bcomps.c:68
static void init(int argc, char *argv[])
Definition bcomps.c:284
int verbose
Definition bcomps.c:62
#define Low(n)
Definition bcomps.c:56
#define N(n)
Definition bcomps.c:58
int silent
Definition bcomps.c:63
char * suffix
Definition bcomps.c:66
static void gwrite(Agraph_t *g, int ng, int nb)
Definition bcomps.c:113
int external
Definition bcomps.c:67
static int process(Agraph_t *g, int gcnt)
Definition bcomps.c:203
static char * blockName(agxbuf *xb, char *gname, int d)
Definition bcomps.c:77
static char * useString
Definition bcomps.c:254
static void dfs(Agraph_t *g, Agnode_t *u, bcstate *stp, Agnode_t *parent)
Definition bcomps.c:153
char * outfile
Definition bcomps.c:64
#define NEXTBLK(g)
Definition bcomps.c:59
static void addCutPts(Agraph_t *tree, Agraph_t *blk)
Definition bcomps.c:188
char ** Files
Definition bcomps.c:61
static Agraph_t * mkBlock(Agraph_t *g, bcstate *stp)
Definition bcomps.c:138
#define Cut(n)
Definition bcomps.c:57
abstract graph C library, Cgraph API
#define parent(i)
Definition closest.c:81
static void split(void)
Definition ccomps.c:99
static char * getName(void)
Definition ccomps.c:246
static NORETURN void graphviz_exit(int status)
Definition exit.h:23
static char * gname
Definition gml2gv.c:25
void free(void *)
size_t graphviz_node_induce(Agraph_t *g, Agraph_t *edgeset)
Definition node_induce.c:9
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition edge.c:253
#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 * 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
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
@ AGEDGE
Definition cgraph.h:207
@ 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 * agsubg(Agraph_t *g, char *name, int cflag)
Definition subg.c:53
Arithmetic helper functions.
static int imin(int a, int b)
minimum of two integers
Definition gv_math.h:29
agxbput(xb, staging)
@ tree
Definition gvgen.c:34
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_PUSH_BACK(list, item)
Definition list.h:393
Agrec_t h
Definition bcomps.c:46
Agrec_t h
Definition bcomps.c:50
int isCut
Definition bcomps.c:53
graph or subgraph
Definition cgraph.h:424
Agraph_t * next
Definition bcomps.c:42
Agrec_t h
Definition bcomps.c:41
implementation of Agrec_t
Definition cgraph.h:172
int count
Definition bcomps.c:71
int nComp
Definition bcomps.c:72
Definition types.h:81
int main()
#define UNREACHABLE()
Definition unreachable.h:30