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*)malloc((n)*sizeof(t))
29
30#include "cgraph.h"
31#include "cghdr.h"
32typedef 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
51static int tot_edges;
52static int tot_nodes;
53static int tot_cc;
54static int tot_cl;
55static int n_graphs;
56static int n_indent;
57static int recurse;
58static int silent;
59static int verbose;
60static int gtype;
61static int flags;
62static char *fname;
63static char **Files;
64static FILE *outfile;
65
66static 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\
78By default, gc prints nodes and edges\n\
79If no files are specified, stdin is used\n";
80
81static void usage(int v)
82{
83 printf("%s",useString);
84 exit(v);
85}
86
87static 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
146typedef 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
153typedef 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
163static Agnode_t *base[SMALLBUF];
164static blk_t Blk;
165static stk_t Stk;
166
167static 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
175static 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
201static 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
213static 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
232static 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
240static 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
258static void ipr(long num)
259{
260 printf(" %7ld", num);
261}
262
263static void
264wcp(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
286static 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
315static 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
341static Agraph_t *gread(FILE * fp)
342{
343 return agread(fp, (Agdisc_t *) 0);
344}
345
346int 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