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 * Generate biconnected components
17 *
18 * Written by Emden Gansner
19 */
20#include "config.h"
21
22#include <stdio.h>
23#include <string.h>
24#include <assert.h>
25#include <getopt.h>
26
27#include <stdlib.h>
28#include "cgraph.h"
29
30typedef struct {
31 Agrec_t h;
32 Agraph_t *next;
33} Agraphinfo_t;
34
35typedef struct {
36 Agrec_t h;
37 Agedge_t *next;
38} Agedgeinfo_t;
39
40typedef struct {
41 Agrec_t h;
42 int low;
43 int val;
44 int isCut;
45} Agnodeinfo_t;
46
47#define Low(n) (((Agnodeinfo_t*)(n->base.data))->low)
48#define Cut(n) (((Agnodeinfo_t*)(n->base.data))->isCut)
49#define N(n) (((Agnodeinfo_t*)(n->base.data))->val)
50#define NEXT(e) (((Agedgeinfo_t*)(e->base.data))->next)
51#define NEXTBLK(g) (((Agraphinfo_t*)(g->base.data))->next)
52
53#include "ingraphs.h"
54
55#define min(a,b) ((a) < (b) ? (a) : (b))
56
57char **Files;
58int verbose;
59int silent;
60char *outfile = 0;
61char *path = 0;
62char *suffix = 0;
63int external; /* emit blocks as root graphs */
64int doTree; /* emit block-cutpoint tree */
65
66static void push(Agedge_t ** sp, Agedge_t * e)
67{
68 NEXT(e) = *sp;
69 *sp = e;
70}
71
72static Agedge_t *pop(Agedge_t ** sp)
73{
74 Agedge_t *top = *sp;
75
76 assert(top);
77 *sp = NEXT(top);
78 return top;
79}
80
81#define top(sp) (sp)
82
83typedef struct {
84 int count;
85 int nComp;
86 Agedge_t *stk;
87 Agraph_t *blks;
88} bcstate;
89
90static char *blockName(char *gname, int d)
91{
92 static char *buf;
93 static int bufsz;
94 int sz;
95
96 sz = strlen(gname) + 128;
97 if (sz > bufsz) {
98 if (buf)
99 free(buf);
100 buf = (char *) malloc(sz);
101 }
102
103 if (*gname == '%') /* anonymous graph */
104 sprintf(buf, "_%s_bcc_%d", gname, d);
105 else
106 sprintf(buf, "%s_bcc_%d", gname, d);
107 return buf;
108}
109
110/* getName:
111 * Generate name for output using input template.
112 * Has form path_<g>_<i>.suffix, for ith write for the gth graph.
113 * If isTree, use path_<g>_t.suffix.
114 * If sufcnt is zero and graph 0, use outfile
115 */
116static char *getName(int ng, int nb)
117{
118 char *name;
119 static char *buf;
120 int sz;
121
122 if ((ng == 0) && (nb == 0))
123 name = outfile;
124 else {
125 if (!buf) {
126 sz = strlen(outfile) + 100; /* enough to handle '_<g>_<b>' */
127 buf = (char *) malloc(sz);
128 }
129 if (suffix) {
130 if (nb < 0)
131 sprintf(buf, "%s_%d_T.%s", path, ng, suffix);
132 else
133 sprintf(buf, "%s_%d_%d.%s", path, ng, nb, suffix);
134 } else {
135 if (nb < 0)
136 sprintf(buf, "%s_%d_T", path, ng);
137 else
138 sprintf(buf, "%s_%d_%d", path, ng, nb);
139 }
140 name = buf;
141 }
142 return name;
143}
144
145static void gwrite(Agraph_t * g, int ng, int nb)
146{
147 FILE *outf;
148 char *name;
149
150 if (silent)
151 return;
152 if (!outfile) {
153 agwrite(g, stdout);
154 fflush(stdout);
155 } else {
156 name = getName(ng, nb);
157 outf = fopen(name, "w");
158 if (!outf) {
159 fprintf(stderr, "Could not open %s for writing\n", name);
160 perror("bcomps");
161 exit(1);
162 }
163 agwrite(g, outf);
164 fclose(outf);
165 }
166}
167
168static Agraph_t *mkBlock(Agraph_t * g, bcstate * stp)
169{
170 Agraph_t *sg;
171
172 stp->nComp++;
173 sg = agsubg(g, blockName(agnameof(g), stp->nComp), 1);
174 agbindrec(sg, "info", sizeof(Agraphinfo_t), TRUE);
175 NEXTBLK(sg) = stp->blks;
176 stp->blks = sg;
177 return sg;
178}
179
180static void
181dfs(Agraph_t * g, Agnode_t * u, bcstate * stp, Agnode_t * parent)
182{
183 Agnode_t *v;
184 Agedge_t *e;
185 Agedge_t *ep;
186 Agraph_t *sg;
187
188 stp->count++;
189 Low(u) = N(u) = stp->count;
190 for (e = agfstedge(g, u); e; e = agnxtedge(g, e, u)) {
191 if ((v = aghead(e)) == u)
192 v = agtail(e);
193 if (v == u)
194 continue;
195 if (N(v) == 0) {
196 push(&stp->stk, e);
197 dfs(g, v, stp, u);
198 Low(u) = min(Low(u), Low(v));
199 if (Low(v) >= N(u)) { /* u is an articulation point */
200 Cut(u) = 1;
201 sg = mkBlock(g, stp);
202 do {
203 ep = pop(&stp->stk);
204 agsubnode(sg, aghead(ep), 1);
205 agsubnode(sg, agtail(ep), 1);
206 } while (ep != e);
207 }
208 } else if (parent != v) {
209 Low(u) = min(Low(u), N(v));
210 if (N(v) < N(u))
211 push(&stp->stk, e);
212 }
213 }
214}
215
216static void nodeInduce(Agraph_t * g, Agraph_t * eg)
217{
218 Agnode_t *n;
219 Agedge_t *e;
220
221 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
222 for (e = agfstout(eg, n); e; e = agnxtout(eg, e)) {
223 if (agsubnode(g, aghead(e), 0)) {
224 agsubedge(g, e, 1);
225 }
226 }
227 }
228}
229
230static void addCutPts(Agraph_t * tree, Agraph_t * blk)
231{
232 Agnode_t *n;
233 Agnode_t *bn;
234 Agnode_t *cn;
235
236 bn = agnode(tree, agnameof(blk), 1);
237 for (n = agfstnode(blk); n; n = agnxtnode(blk, n)) {
238 if (Cut(n)) {
239 cn = agnode(tree, agnameof(n), 1);
240 agedge(tree, bn, cn, 0, 1);
241 }
242 }
243}
244
245static int process(Agraph_t * g, int gcnt)
246{
247 Agnode_t *n;
248 bcstate state;
249 Agraph_t *blk;
250 Agraph_t *tree;
251 int bcnt;
252
253 aginit(g, AGNODE, "info", sizeof(Agnodeinfo_t), TRUE);
254 aginit(g, AGEDGE, "info", sizeof(Agedgeinfo_t), TRUE);
255 aginit(g, AGRAPH, "info", sizeof(Agraphinfo_t), TRUE);
256
257 state.count = 0;
258 state.nComp = 0;
259 state.stk = 0;
260 state.blks = 0;
261
262 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
263 if (N(n) == 0)
264 dfs(g, n, &state, 0);
265 }
266 for (blk = state.blks; blk; blk = NEXTBLK(blk)) {
267 nodeInduce(blk, g);
268 }
269 if (external) {
270 bcnt = 0;
271 for (blk = state.blks; blk; blk = NEXTBLK(blk)) {
272 gwrite(blk, gcnt, bcnt++);
273 }
274 } else
275 gwrite(g, gcnt, 0);
276 if (doTree) {
277 tree = agopen("blkcut_tree", Agstrictundirected, 0);
278 for (blk = state.blks; blk; blk = NEXTBLK(blk))
279 addCutPts(tree, blk);
280 gwrite(tree, gcnt, -1);
281 agclose(tree);
282 }
283 if (verbose) {
284 int cuts = 0;
285 bcnt = 0;
286 for (blk = state.blks; blk; blk = NEXTBLK(blk))
287 bcnt++;
288 for (n = agfstnode(g); n; n = agnxtnode(g, n))
289 if (Cut(n))
290 cuts++;
291 fprintf(stderr, "%s: %d blocks %d cutpoints\n", agnameof(g), bcnt,
292 cuts);
293 }
294 if (state.blks && NEXTBLK(state.blks))
295 return 1; /* >= 2 blocks */
296 else
297 return 0;
298}
299
300static char *useString =
301 "Usage: bcomps [-stvx?] [-o<out template>] <files>\n\
302 -o - output file template\n\
303 -s - don't print components\n\
304 -t - emit block-cutpoint tree\n\
305 -v - verbose\n\
306 -x - external\n\
307 -? - print usage\n\
308If no files are specified, stdin is used\n";
309
310static void usage(int v)
311{
312 printf("%s",useString);
313 exit(v);
314}
315
316static void split(char *name)
317{
318 char *sfx = 0;
319 int size;
320
321 sfx = strrchr(name, '.');
322 if (sfx) {
323 size = sfx - name;
324 suffix = sfx + 1;
325 path = (char *) malloc(size + 1);
326 strncpy(path, name, size);
327 *(path + size) = '\0';
328 } else {
329 path = name;
330 }
331}
332
333static void init(int argc, char *argv[])
334{
335 int c;
336
337 opterr = 0;
338 while ((c = getopt(argc, argv, ":o:xstv")) != -1) {
339 switch (c) {
340 case 'o':
341 outfile = optarg;
342 split(outfile);
343 break;
344 case 's':
345 verbose = 1;
346 silent = 1;
347 break;
348 case 'v':
349 verbose = 1;
350 break;
351 case 't':
352 doTree = 1;
353 break;
354 case 'x':
355 external = 1;
356 break;
357 case ':':
358 fprintf(stderr, "bcomps: option -%c missing argument - ignored\n", optopt);
359 break;
360 case '?':
361 if (optopt == '?')
362 usage(0);
363 else
364 fprintf(stderr,
365 "bcomps: option -%c unrecognized - ignored\n", optopt);
366 break;
367 }
368 }
369 argv += optind;
370 argc -= optind;
371
372 if (argc > 0)
373 Files = argv;
374}
375
376static Agraph_t *gread(FILE * fp)
377{
378 return agread(fp, (Agdisc_t *) 0);
379}
380
381int main(int argc, char *argv[])
382{
383 Agraph_t *g;
384 ingraph_state ig;
385 int r = 0;
386 int gcnt = 0;
387
388 init(argc, argv);
389 newIngraph(&ig, Files, gread);
390
391 while ((g = nextGraph(&ig)) != 0) {
392 r |= process(g, gcnt);
393 agclose(g);
394 gcnt++;
395 }
396
397 return r;
398}
399