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/*
21 * This is a filter that reads a graph, searches for strongly
22 * connected components, and writes each as a separate graph
23 * along with a map of the components.
24 */
25#include "config.h"
26
27#include <stdio.h>
28#include <stdlib.h>
29#ifdef HAVE_UNISTD_H
30#include <unistd.h>
31#endif
32#include "cgraph.h"
33#include "ingraphs.h"
34
35#include <getopt.h>
36
37#define INF ((unsigned int)(-1))
38
39typedef struct Agraphinfo_t {
40 Agrec_t h;
41 Agnode_t *rep;
42} Agraphinfo_t;
43
44typedef struct Agnodeinfo_t {
45 Agrec_t h;
46 unsigned int val;
47 Agraph_t *scc;
48} Agnodeinfo_t;
49
50#ifdef INLINE
51#define getrep(g) (((Agraphinfo_t*)(g->base.data))->rep)
52#define setrep(g,rep) (getrep(g) = rep)
53#define getscc(n) (((Agnodeinfo_t*)((n)->base.data))->scc)
54#define setscc(n,sub) (getscc(n) = sub)
55#define getval(n) (((Agnodeinfo_t*)((n)->base.data))->val)
56#define setval(n,newval) (getval(n) = newval)
57#else
58static Agnode_t *getrep(Agraph_t * g)
59{
60 return (((Agraphinfo_t *) (g->base.data))->rep);
61}
62static void setrep(Agraph_t * g, Agnode_t * rep)
63{
64 ((Agraphinfo_t *) (g->base.data))->rep = rep;
65}
66static Agraph_t *getscc(Agnode_t * n)
67{
68 return (((Agnodeinfo_t *) (n->base.data))->scc);
69}
70static void setscc(Agnode_t * n, Agraph_t * scc)
71{
72 ((Agnodeinfo_t *) (n->base.data))->scc = scc;
73}
74static int getval(Agnode_t * n)
75{
76 return (((Agnodeinfo_t *) (n->base.data))->val);
77}
78static void setval(Agnode_t * n, int v)
79{
80 ((Agnodeinfo_t *) (n->base.data))->val = v;
81}
82#endif
83
84/********* stack ***********/
85typedef struct {
86 Agnode_t **data;
87 Agnode_t **ptr;
88} Stack;
89
90static void initStack(Stack * sp, int sz)
91{
92 sp->data = (Agnode_t **) malloc(sz * sizeof(Agnode_t *));
93 sp->ptr = sp->data;
94}
95
96static void freeStack(Stack * sp)
97{
98 free(sp->data);
99}
100
101#ifdef INLINE
102#define push(sp,n) (*((sp)->ptr++) = n)
103#define top(sp) (*((sp)->ptr - 1))
104#define pop(sp) (*(--((sp)->ptr)))
105#else
106static void push(Stack * sp, Agnode_t * n)
107{
108 *(sp->ptr++) = n;
109}
110
111static Agnode_t *top(Stack * sp)
112{
113 return *(sp->ptr - 1);
114}
115
116static Agnode_t *pop(Stack * sp)
117{
118 sp->ptr--;
119 return *(sp->ptr);
120}
121#endif
122
123
124/********* end stack ***********/
125
126typedef struct {
127 int Comp;
128 int ID;
129 int N_nodes_in_nontriv_SCC;
130} sccstate;
131
132static int wantDegenerateComp;
133static int Silent;
134static int StatsOnly;
135static int Verbose;
136static char *CmdName;
137static char **Files;
138static FILE *outfp; /* output; stdout by default */
139
140static void nodeInduce(Agraph_t * g, Agraph_t* map)
141{
142 Agnode_t *n;
143 Agedge_t *e;
144 Agraph_t* rootg = agroot (g);
145
146
147 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
148 for (e = agfstout(rootg, n); e; e = agnxtout(rootg, e)) {
149 if (agsubnode(g, aghead(e), FALSE))
150 agsubedge(g, e, TRUE);
151 else {
152 Agraph_t* tscc = getscc(agtail(e));
153 Agraph_t* hscc = getscc(aghead(e));
154 if (tscc && hscc)
155 agedge(map, getrep(tscc),
156 getrep(hscc), NIL(char *), TRUE);
157 }
158 }
159 }
160}
161
162static int visit(Agnode_t * n, Agraph_t * map, Stack * sp, sccstate * st)
163{
164 unsigned int m, min;
165 Agnode_t *t;
166 Agraph_t *subg;
167 Agedge_t *e;
168
169 min = ++(st->ID);
170 setval(n, min);
171 push(sp, n);
172
173 for (e = agfstout(n->root, n); e; e = agnxtout(n->root, e)) {
174 t = aghead(e);
175 if (getval(t) == 0)
176 m = visit(t, map, sp, st);
177 else
178 m = getval(t);
179 if (m < min)
180 min = m;
181 }
182
183 if (getval(n) == min) {
184 if (!wantDegenerateComp && (top(sp) == n)) {
185 setval(n, INF);
186 pop(sp);
187 } else {
188 char name[32];
189 Agraph_t *G = agraphof(n);;
190 sprintf(name, "cluster_%d", (st->Comp)++);
191 subg = agsubg(G, name, TRUE);
192 agbindrec(subg, "scc_graph", sizeof(Agraphinfo_t), TRUE);
193 setrep(subg, agnode(map, name, TRUE));
194 do {
195 t = pop(sp);
196 agsubnode(subg, t, TRUE);
197 setval(t, INF);
198 setscc(t, subg);
199 st->N_nodes_in_nontriv_SCC++;
200 } while (t != n);
201 nodeInduce(subg, map);
202 if (!StatsOnly)
203 agwrite(subg, outfp);
204 }
205 }
206 return min;
207}
208
209static int label(Agnode_t * n, int nodecnt, int *edgecnt)
210{
211 Agedge_t *e;
212
213 setval(n, 1);
214 nodecnt++;
215 for (e = agfstedge(n->root, n); e; e = agnxtedge(n->root, e, n)) {
216 (*edgecnt) += 1;
217 if (e->node == n)
218 e = agopp(e);
219 if (!getval(e->node))
220 nodecnt = label(e->node, nodecnt, edgecnt);
221 }
222 return nodecnt;
223}
224
225static int
226countComponents(Agraph_t * g, int *max_degree, float *nontree_frac)
227{
228 int nc = 0;
229 int sum_edges = 0;
230 int sum_nontree = 0;
231 int deg;
232 int n_edges;
233 int n_nodes;
234 Agnode_t *n;
235
236 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
237 if (!getval(n)) {
238 nc++;
239 n_edges = 0;
240 n_nodes = label(n, 0, &n_edges);
241 sum_edges += n_edges;
242 sum_nontree += (n_edges - n_nodes + 1);
243 }
244 }
245 if (max_degree) {
246 int maxd = 0;
247 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
248 deg = agdegree(g, n, TRUE, TRUE);
249 if (maxd < deg)
250 maxd = deg;
251 setval(n, 0);
252 }
253 *max_degree = maxd;
254 }
255 if (nontree_frac) {
256 if (sum_edges > 0)
257 *nontree_frac = (float) sum_nontree / (float) sum_edges;
258 else
259 *nontree_frac = 0.0;
260 }
261 return nc;
262}
263
264static void process(Agraph_t * G)
265{
266 Agnode_t *n;
267 Agraph_t *map;
268 int nc = 0;
269 float nontree_frac = 0;
270 int Maxdegree = 0;
271 Stack stack;
272 sccstate state;
273
274 aginit(G, AGRAPH, "scc_graph", sizeof(Agraphinfo_t), TRUE);
275 aginit(G, AGNODE, "scc_node", sizeof(Agnodeinfo_t), TRUE);
276 state.Comp = state.ID = 0;
277 state.N_nodes_in_nontriv_SCC = 0;
278
279 if (Verbose)
280 nc = countComponents(G, &Maxdegree, &nontree_frac);
281
282 initStack(&stack, agnnodes(G) + 1);
283 map = agopen("scc_map", Agdirected, (Agdisc_t *) 0);
284 for (n = agfstnode(G); n; n = agnxtnode(G, n))
285 if (getval(n) == 0)
286 visit(n, map, &stack, &state);
287 freeStack(&stack);
288 if (!StatsOnly)
289 agwrite(map, outfp);
290 agclose(map);
291
292 if (Verbose)
293 fprintf(stderr, "%d %d %d %d %.4f %d %.4f\n",
294 agnnodes(G), agnedges(G), nc, state.Comp,
295 state.N_nodes_in_nontriv_SCC / (double) agnnodes(G),
296 Maxdegree, nontree_frac);
297 else if (!Silent)
298 fprintf(stderr, "%d nodes, %d edges, %d strong components\n",
299 agnnodes(G), agnedges(G), state.Comp);
300
301}
302
303static FILE *openFile(char *name, char *mode)
304{
305 FILE *fp;
306 char *modestr;
307
308 fp = fopen(name, mode);
309 if (!fp) {
310 if (*mode == 'r')
311 modestr = "reading";
312 else
313 modestr = "writing";
314 fprintf(stderr, "gvpack: could not open file %s for %s\n",
315 name, modestr);
316 exit(1);
317 }
318 return (fp);
319}
320
321static char *useString = "Usage: %s [-sdv?] <files>\n\
322 -s - only produce statistics\n\
323 -S - silent\n\
324 -d - allow degenerate components\n\
325 -o<outfile> - write to <outfile> (stdout)\n\
326 -v - verbose\n\
327 -? - print usage\n\
328If no files are specified, stdin is used\n";
329
330static void usage(int v)
331{
332 printf(useString, CmdName);
333 exit(v);
334}
335
336static void scanArgs(int argc, char **argv)
337{
338 int c;
339
340 CmdName = argv[0];
341 opterr = 0;
342 while ((c = getopt(argc, argv, ":o:sdvS")) != EOF) {
343 switch (c) {
344 case 's':
345 StatsOnly = 1;
346 break;
347 case 'd':
348 wantDegenerateComp = 1;
349 break;
350 case 'o':
351 outfp = openFile(optarg, "w");
352 break;
353 case 'v':
354 Verbose = 1;
355 break;
356 case 'S':
357 Verbose = 0;
358 Silent = 1;
359 break;
360 case ':':
361 fprintf(stderr, "%s: option -%c missing argument - ignored\n", CmdName, optopt);
362 break;
363 case '?':
364 if (optopt == '?')
365 usage(0);
366 else
367 fprintf(stderr, "%s: option -%c unrecognized - ignored\n",
368 CmdName, optopt);
369 break;
370 }
371 }
372 argv += optind;
373 argc -= optind;
374
375 if (argc > 0)
376 Files = argv;
377 if (!outfp)
378 outfp = stdout; /* stdout the default */
379}
380
381static Agraph_t *gread(FILE * fp)
382{
383 return agread(fp, (Agdisc_t *) 0);
384}
385
386int main(int argc, char **argv)
387{
388 Agraph_t *g;
389 ingraph_state ig;
390
391 scanArgs(argc, argv);
392 newIngraph(&ig, Files, gread);
393
394 while ((g = nextGraph(&ig)) != 0) {
395 if (agisdirected(g))
396 process(g);
397 else
398 fprintf(stderr, "Graph %s in %s is undirected - ignored\n",
399 agnameof(g), fileName(&ig));
400 agclose(g);
401 }
402
403 return 0;
404}
405