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 Emden Gansner
17 */
18
19 #include "config.h"
20
21 #include <stdio.h>
22 #ifdef HAVE_UNISTD_H
23 #include <unistd.h>
24 #endif
25 #include <string.h>
26
27 #define NEW(t) (t*)malloc(sizeof(t))
28 #define N_NEW(n,t) (t*)calloc((n),sizeof(t))
29
30 #include "cgraph.h"
31 #include "cghdr.h"
32 typedef struct {
33 Agrec_t h;
34 int dfs_mark;
35 } Agnodeinfo_t;
36
37 #define ND_dfs_mark(n) (((Agnodeinfo_t*)(n->base.data))->dfs_mark)
38
39 #include "ingraphs.h"
40
41 #include <getopt.h>
42
43 #define NODES 1
44 #define EDGES 2
45 #define CC 4
46 #define CL 8
47
48 #define DIRECTED 1
49 #define UNDIRECTED 2
50
51 static int tot_edges;
52 static int tot_nodes;
53 static int tot_cc;
54 static int tot_cl;
55 static int n_graphs;
56 static int n_indent;
57 static int recurse;
58 static int silent;
59 static int verbose;
60 static int gtype;
61 static int flags;
62 static char *fname;
63 static char **Files;
64 static FILE *outfile;
65
66 static char *useString = "Usage: gc [-necCaDUrsv?] <files>\n\
67 -n - print number of nodes\n\
68 -e - print number of edges\n\
69 -c - print number of connected components\n\
70 -C - print number of clusters\n\
71 -a - print all counts\n\
72 -D - only directed graphs\n\
73 -U - only undirected graphs\n\
74 -r - recursively analyze subgraphs\n\
75 -s - silent\n\
76 -v - verbose\n\
77 -? - print usage\n\
78 By default, gc prints nodes and edges\n\
79 If no files are specified, stdin is used\n";
80
usage(int v)81 static void usage(int v)
82 {
83 printf("%s",useString);
84 exit(v);
85 }
86
init(int argc,char * argv[])87 static void init(int argc, char *argv[])
88 {
89 unsigned int c;
90
91 opterr = 0;
92 while ((c = getopt(argc, argv, "necCaDUrsv")) != -1) {
93 switch (c) {
94 case 'e':
95 flags |= EDGES;
96 break;
97 case 'n':
98 flags |= NODES;
99 break;
100 case 'c':
101 flags |= CC;
102 break;
103 case 'C':
104 flags |= CL;
105 tot_cl = 0;
106 break;
107 case 'a':
108 flags = NODES | EDGES | CC | CL;
109 break;
110 case 'r':
111 recurse = 1;
112 break;
113 case 's':
114 silent = 1;
115 break;
116 case 'v':
117 verbose = 1;
118 break;
119 case 'D':
120 gtype = DIRECTED;
121 break;
122 case 'U':
123 gtype = UNDIRECTED;
124 break;
125 case '?':
126 if (optopt == '?')
127 usage(0);
128 else
129 fprintf(stderr, "gc: option -%c unrecognized - ignored\n",
130 optopt);
131 break;
132 }
133 }
134 argv += optind;
135 argc -= optind;
136
137 if (argc)
138 Files = argv;
139 if (flags == 0)
140 flags = NODES | EDGES;
141 if (gtype == 0)
142 gtype = DIRECTED | UNDIRECTED;
143 outfile = stdout;
144 }
145
146 typedef struct blk_t {
147 Agnode_t **data;
148 Agnode_t **endp;
149 struct blk_t *prev;
150 struct blk_t *next;
151 } blk_t;
152
153 typedef struct {
154 blk_t *fstblk;
155 blk_t *curblk;
156 Agnode_t **curp;
157 } stk_t;
158
159
160 #define SMALLBUF 1024
161 #define BIGBUF 1000000
162
163 static Agnode_t *base[SMALLBUF];
164 static blk_t Blk;
165 static stk_t Stk;
166
initStk(void)167 static void initStk(void)
168 {
169 Blk.data = base;
170 Blk.endp = Blk.data + SMALLBUF;
171 Stk.curblk = Stk.fstblk = &Blk;
172 Stk.curp = Stk.curblk->data;
173 }
174
push(Agnode_t * np)175 static void push(Agnode_t * np)
176 {
177 if (Stk.curp == Stk.curblk->endp) {
178 if (Stk.curblk->next == NULL) {
179 blk_t *bp = NEW(blk_t);
180 if (bp == 0) {
181 fprintf(stderr, "gc: Out of memory\n");
182 exit(1);
183 }
184 bp->prev = Stk.curblk;
185 bp->next = NULL;
186 bp->data = N_NEW(BIGBUF, Agnode_t *);
187 if (bp->data == 0) {
188 fprintf(stderr, "gc: Out of memory\n");
189 exit(1);
190 }
191 bp->endp = bp->data + BIGBUF;
192 Stk.curblk->next = bp;
193 }
194 Stk.curblk = Stk.curblk->next;
195 Stk.curp = Stk.curblk->data;
196 }
197 ND_dfs_mark(np) = -1;
198 *Stk.curp++ = np;
199 }
200
pop(void)201 static Agnode_t *pop(void)
202 {
203 if (Stk.curp == Stk.curblk->data) {
204 if (Stk.curblk == Stk.fstblk)
205 return 0;
206 Stk.curblk = Stk.curblk->prev;
207 Stk.curp = Stk.curblk->endp;
208 }
209 Stk.curp--;
210 return *Stk.curp;
211 }
212
cc_dfs(Agraph_t * g,Agnode_t * n)213 static void cc_dfs(Agraph_t * g, Agnode_t * n)
214 {
215 Agedge_t *e;
216 Agnode_t *nxt;
217
218 push(n);
219 while ((n = pop())) {
220 ND_dfs_mark(n) = 1;
221 for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
222 if (n == agtail(e))
223 nxt = aghead(e);
224 else
225 nxt = agtail(e);
226 if (ND_dfs_mark(nxt) == 0)
227 push(nxt);
228 }
229 }
230 }
231
cntCluster(Agraph_t * g,Agobj_t * sg,void * arg)232 static void cntCluster(Agraph_t * g, Agobj_t * sg, void *arg)
233 {
234 char *sgname = agnameof((Agraph_t *) sg);
235
236 if (strncmp(sgname, "cluster", 7) == 0)
237 *(int *) (arg) += 1;
238 }
239
cc_decompose(Agraph_t * g)240 static int cc_decompose(Agraph_t * g)
241 {
242 int c_cnt = 0;
243 Agnode_t *n;
244
245 c_cnt = 0;
246 for (n = agfstnode(g); n; n = agnxtnode(g, n))
247 ND_dfs_mark(n) = 0;
248 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
249 if (ND_dfs_mark(n))
250 continue;
251 c_cnt++;
252 cc_dfs(g, n);
253 }
254
255 return c_cnt;
256 }
257
ipr(long num)258 static void ipr(long num)
259 {
260 printf(" %7ld", num);
261 }
262
263 static void
wcp(int nnodes,int nedges,int ncc,int ncl,char * gname,char * fname)264 wcp(int nnodes, int nedges, int ncc, int ncl, char *gname, char *fname)
265 {
266 int i;
267
268 if (silent)
269 return;
270 for (i = 0; i < n_indent; i++)
271 fputs(" ", outfile);
272 if (flags & NODES)
273 ipr(nnodes);
274 if (flags & EDGES)
275 ipr(nedges);
276 if (flags & CC)
277 ipr(ncc);
278 if (flags & CL)
279 ipr(ncl);
280 if (fname)
281 printf(" %s (%s)\n", gname, fname);
282 else
283 printf(" %s\n", gname);
284 }
285
emit(Agraph_t * g,int root,int cl_count)286 static void emit(Agraph_t * g, int root, int cl_count)
287 {
288 int n_edges = agnedges(g);
289 int n_nodes = agnnodes(g);
290 int n_cc = 0;
291 int n_cl = 0;
292 char *file = 0;
293
294 if (flags & CC)
295 n_cc = cc_decompose(g);
296
297 if (flags & CL)
298 n_cl = cl_count;
299
300 if (root)
301 file = fname;
302 wcp(n_nodes, n_edges, n_cc, n_cl, agnameof(g), file);
303
304 if (root) {
305 n_graphs++;
306 tot_edges += n_edges;
307 tot_nodes += n_nodes;
308 tot_cc += n_cc;
309 tot_cl += n_cl;
310 }
311 }
312
313 #define GTYPE(g) (agisdirected(g)?DIRECTED:UNDIRECTED)
314
eval(Agraph_t * g,int root)315 static int eval(Agraph_t * g, int root)
316 {
317 Agraph_t *subg;
318 int cl_count = 0;
319
320 if (root && !(GTYPE(g) & gtype))
321 return 1;
322
323 if (root) {
324 aginit(g, AGNODE, "nodeinfo", sizeof(Agnodeinfo_t), TRUE);
325 }
326
327 if ((flags & CL) && root)
328 agapply(g, (Agobj_t *) g, cntCluster, &cl_count, 0);
329
330 emit(g, root, cl_count);
331
332 if (recurse) {
333 n_indent++;
334 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg))
335 eval(subg, 0);
336 n_indent--;
337 }
338 return 0;
339 }
340
gread(FILE * fp)341 static Agraph_t *gread(FILE * fp)
342 {
343 return agread(fp, (Agdisc_t *) 0);
344 }
345
main(int argc,char * argv[])346 int main(int argc, char *argv[])
347 {
348 Agraph_t *g;
349 Agraph_t *prev = NULL;
350 ingraph_state ig;
351 int rv = 0;
352
353 init(argc, argv);
354 newIngraph(&ig, Files, gread);
355
356 if (flags & CC)
357 initStk();
358
359 while ((g = nextGraph(&ig)) != 0) {
360 if (prev)
361 agclose(prev);
362 prev = g;
363 fname = fileName(&ig);
364 if (verbose)
365 fprintf(stderr, "Process graph %s in file %s\n", agnameof(g),
366 fname);
367 rv |= eval(g, 1);
368 }
369
370 if (n_graphs > 1)
371 wcp(tot_nodes, tot_edges, tot_cc, tot_cl, "total", 0);
372
373 return rv;
374 }
375