← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to tools/src/sccmap.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
tools/src/sccmap.c
 
1
/*
 
2
    This software may only be used by you under license from AT&T Corp.
 
3
    ("AT&T").  A copy of AT&T's Source Code Agreement is available at
 
4
    AT&T's Internet website having the URL:
 
5
    <http://www.research.att.com/sw/tools/graphviz/license/source.html>
 
6
    If you received this software without first entering into a license
 
7
    with AT&T, you have an infringing copy of this software and cannot use
 
8
    it without violating AT&T's intellectual property rights.
 
9
*/
 
10
 
 
11
/*
 
12
 * Written by Stephen North
 
13
 * Updated by Emden Gansner
 
14
 */
 
15
 
 
16
/*
 
17
 * This is a filter that reads a graph, searches for strongly
 
18
 * connected components, and writes each as a separate graph
 
19
 * along with a map of the components.
 
20
 */
 
21
 
 
22
#include <stdio.h>
 
23
#include <unistd.h>
 
24
#include <agraph.h>
 
25
#include <ingraphs.h>
 
26
 
 
27
#ifdef NO_OPTOPT_DECL
 
28
#include "getopt.h"
 
29
#endif
 
30
 
 
31
#define INF ((unsigned int)(-1))
 
32
 
 
33
typedef struct Agraphinfo_t {
 
34
    Agrec_t        h;
 
35
    Agnode_t*      rep;
 
36
} Agraphinfo_t;
 
37
 
 
38
typedef struct Agnodeinfo_t {
 
39
    Agrec_t        h;
 
40
    unsigned int   val;
 
41
    Agraph_t*      scc;
 
42
} Agnodeinfo_t;
 
43
 
 
44
#ifdef INLINE
 
45
#define getrep(g)  (((Agraphinfo_t*)(g->base.data))->rep)
 
46
#define setrep(g,rep)  (getrep(g) = rep)
 
47
#define getscc(n)    (((Agnodeinfo_t*)((n)->base.data))->scc)
 
48
#define setscc(n,sub)    (getscc(n) = sub)
 
49
#define getval(n)    (((Agnodeinfo_t*)((n)->base.data))->val)
 
50
#define setval(n,newval)    (getval(n) = newval)
 
51
#else
 
52
static Agnode_t *
 
53
getrep(Agraph_t *g) 
 
54
{
 
55
  return (((Agraphinfo_t*)(g->base.data))->rep);
 
56
}
 
57
static void 
 
58
setrep(Agraph_t *g, Agnode_t *rep)
 
59
{
 
60
  ((Agraphinfo_t*)(g->base.data))->rep = rep;
 
61
}
 
62
static Agraph_t *
 
63
getscc(Agnode_t *n) 
 
64
{
 
65
  return (((Agnodeinfo_t*)(n->base.data))->scc);
 
66
}
 
67
static void 
 
68
setscc(Agnode_t *n, Agraph_t *scc) 
 
69
{
 
70
  ((Agnodeinfo_t*)(n->base.data))->scc = scc;
 
71
}
 
72
static int
 
73
getval(Agnode_t *n) 
 
74
{
 
75
  return (((Agnodeinfo_t*)(n->base.data))->val);
 
76
}
 
77
static void 
 
78
setval(Agnode_t *n, int v)
 
79
{
 
80
  ((Agnodeinfo_t*)(n->base.data))->val = v;
 
81
}
 
82
#endif
 
83
 
 
84
/********* stack ***********/
 
85
typedef struct {
 
86
  Agnode_t**   data;
 
87
  Agnode_t**   ptr;
 
88
} Stack;
 
89
 
 
90
static void
 
91
initStack (Stack* sp, int sz)
 
92
{
 
93
  sp->data = (Agnode_t**)malloc(sz*sizeof(Agnode_t*));
 
94
  sp->ptr = sp->data;
 
95
}
 
96
 
 
97
static void
 
98
freeStack (Stack* sp)
 
99
{
 
100
  free (sp->data);
 
101
}
 
102
 
 
103
#ifdef INLINE
 
104
#define push(sp,n) (*((sp)->ptr++) = n)
 
105
#define top(sp) (*((sp)->ptr - 1))
 
106
#define pop(sp) (*(--((sp)->ptr)))
 
107
#else
 
108
static void
 
109
push (Stack* sp, Agnode_t* n)
 
110
{
 
111
  *(sp->ptr++) = n;
 
112
}
 
113
 
 
114
static Agnode_t*
 
115
top (Stack* sp)
 
116
{
 
117
  return *(sp->ptr - 1);
 
118
}
 
119
 
 
120
static Agnode_t*
 
121
pop (Stack* sp)
 
122
{
 
123
  sp->ptr--;
 
124
  return *(sp->ptr);
 
125
}
 
126
#endif
 
127
 
 
128
 
 
129
/********* end stack ***********/
 
130
 
 
131
typedef struct {
 
132
  int  Comp;
 
133
  int  ID;
 
134
  int  N_nodes_in_nontriv_SCC;
 
135
} sccstate;
 
136
 
 
137
int            wantDegenerateComp;
 
138
int            Silent;
 
139
int            Verbose;
 
140
char*          CmdName;
 
141
char**         Files;
 
142
 
 
143
static void 
 
144
nodeInduce(Agraph_t *g)
 
145
{
 
146
  Agnode_t        *n, *rootn;
 
147
  Agedge_t        *e;
 
148
 
 
149
  for (n = agfstnode(g); n; n = agnxtnode(n)) {
 
150
    rootn = agsubnode(agroot(g),n,FALSE);
 
151
    for (e = agfstout(rootn); e; e = agnxtout(e)) {
 
152
      if (agsubnode(g,aghead(e),FALSE)) agsubedge(g,e,TRUE);
 
153
      else {
 
154
        if (getscc(aghead(e)) && getscc(agtail(e)))
 
155
          agedge(getrep(getscc(agtail(e))),getrep(getscc(aghead(e))),
 
156
            NIL(char*),TRUE);
 
157
      }
 
158
    }
 
159
  }
 
160
}
 
161
 
 
162
static int 
 
163
visit(Agnode_t *n, Agraph_t* map, Stack* sp, sccstate* st)
 
164
{
 
165
  unsigned int  m,min;
 
166
  Agnode_t*     t;
 
167
  Agraph_t*     subg;
 
168
  Agedge_t*     e;
 
169
 
 
170
  min = ++(st->ID);
 
171
  setval(n,min);
 
172
  push (sp, n);
 
173
 
 
174
  for (e = agfstout(n); e; e = agnxtout(e)) {
 
175
    t = aghead(e);
 
176
    if (getval(t) == 0) m = visit(t,map,sp,st);
 
177
    else m = getval(t);
 
178
    if (m < min) min = m;
 
179
  }
 
180
 
 
181
  if (getval(n) == min) {
 
182
    if (!wantDegenerateComp && (top(sp) == n)) {
 
183
      setval(n,INF);
 
184
      pop(sp);
 
185
    }
 
186
    else {
 
187
      char name[32];
 
188
      Agraph_t*   G = agraphof(n);;
 
189
      sprintf(name,"cluster_%d",(st->Comp)++);
 
190
      subg = agsubg(G,name,TRUE);
 
191
      agbindrec(subg,"scc_graph",sizeof(Agraphinfo_t),TRUE);
 
192
      setrep(subg,agnode(map,name,TRUE));
 
193
      do {
 
194
        t = pop(sp);
 
195
        agsubnode(subg,t,TRUE);
 
196
        setval(t,INF);
 
197
        setscc(t,subg);
 
198
        st->N_nodes_in_nontriv_SCC++;
 
199
      } while (t != n);
 
200
      nodeInduce(subg);
 
201
      if (!Silent) agwrite(subg,stdout);
 
202
    }
 
203
  }
 
204
  return min;
 
205
}
 
206
 
 
207
static int 
 
208
label(Agnode_t *n, int nodecnt, int* edgecnt)
 
209
{
 
210
  Agedge_t    *e;
 
211
 
 
212
  setval(n,1);
 
213
  nodecnt++;
 
214
  for (e = agfstedge(n); e; e = agnxtedge(e,n)) {
 
215
    (*edgecnt) += 1;
 
216
    if (e->node == n) e = agopp(e);
 
217
    if (!getval(e->node))
 
218
      nodecnt = label(e->node,nodecnt,edgecnt);
 
219
  }
 
220
  return nodecnt;
 
221
}
 
222
 
 
223
static int 
 
224
countComponents(Agraph_t *g, int* max_degree, float *nontree_frac)
 
225
{
 
226
  int        nc = 0;
 
227
  int        sum_edges = 0;
 
228
  int        sum_nontree = 0;
 
229
  int        deg;
 
230
  int        n_edges;
 
231
  int        n_nodes;
 
232
  Agnode_t*  n;
 
233
 
 
234
  for (n = agfstnode(g); n; n = agnxtnode(n)) {
 
235
    if (!getval(n)) {
 
236
      nc++;
 
237
      n_edges = 0;
 
238
      n_nodes = label(n,0,&n_edges);
 
239
      sum_edges += n_edges;
 
240
      sum_nontree += (n_edges - n_nodes + 1);
 
241
    }
 
242
  }
 
243
  if (max_degree) {
 
244
    int maxd = 0;
 
245
    for (n = agfstnode(g); n; n = agnxtnode(n)) {
 
246
      deg = agdegree(n,TRUE,TRUE);
 
247
      if (maxd < deg) maxd = deg;
 
248
      setval(n,0);
 
249
    }
 
250
    *max_degree = maxd;
 
251
  }
 
252
  if (nontree_frac) {
 
253
    if (sum_edges > 0) *nontree_frac = (float)sum_nontree / (float)sum_edges;
 
254
    else *nontree_frac = 0.0;
 
255
  }
 
256
  return nc;
 
257
}
 
258
 
 
259
static void 
 
260
process(Agraph_t* G)
 
261
{
 
262
  Agnode_t*    n;
 
263
  Agraph_t*    map;
 
264
  int          nc;
 
265
  float        nontree_frac;
 
266
  int          Maxdegree;
 
267
  Stack        stack;
 
268
  sccstate     state;
 
269
 
 
270
  aginit(G,AGRAPH,"scc_graph",sizeof(Agraphinfo_t),TRUE);
 
271
  aginit(G,AGNODE,"scc_node",sizeof(Agnodeinfo_t),TRUE);
 
272
  state.Comp = state.ID = 0;
 
273
  state.N_nodes_in_nontriv_SCC = 0;
 
274
 
 
275
  if (Verbose)
 
276
    nc = countComponents(G,&Maxdegree,&nontree_frac);
 
277
 
 
278
  initStack(&stack, agnnodes(G) + 1);
 
279
  map = agopen("scc_map",Agdirected,(Agdisc_t *)0);
 
280
  for (n = agfstnode(G); n; n = agnxtnode(n))
 
281
    if (getval(n) == 0) visit(n,map,&stack,&state);
 
282
  freeStack(&stack);
 
283
  if (!Silent) agwrite(map,stdout);
 
284
  agclose(map);
 
285
 
 
286
  if (Verbose) 
 
287
    fprintf(stderr,"%d %d %d %d %.4lf %d %.4f\n",
 
288
      agnnodes(G), agnedges(G), nc, state.Comp,
 
289
      state.N_nodes_in_nontriv_SCC / (double) agnnodes(G), Maxdegree,
 
290
      nontree_frac);
 
291
  else
 
292
    fprintf(stderr,"%d nodes, %d edges, %d strong components\n",
 
293
      agnnodes(G), agnedges(G), state.Comp);
 
294
 
 
295
}
 
296
 
 
297
static char* useString = 
 
298
"Usage: %s [-sdv?] <files>\n\
 
299
  -s - silent\n\
 
300
  -d - allow degenerate components\n\
 
301
  -v - verbose\n\
 
302
  -? - print usage\n\
 
303
If no files are specified, stdin is used\n";
 
304
 
 
305
static void
 
306
usage (int v)
 
307
{
 
308
    printf (useString, CmdName);
 
309
    exit (v);
 
310
}
 
311
 
 
312
static void
 
313
scanArgs(int argc,char **argv)
 
314
{
 
315
  int            c;
 
316
 
 
317
  CmdName = argv[0];
 
318
  while ((c = getopt(argc,argv,":?sdv")) != EOF) {
 
319
    switch (c) {
 
320
    case 's': 
 
321
      Silent = 1; break;
 
322
    case 'd': 
 
323
      wantDegenerateComp = 1; break;
 
324
    case 'v': 
 
325
      Verbose = 1; break;
 
326
    case '?':
 
327
      if (optopt == '?') usage(0);
 
328
      else fprintf(stderr,"%s: option -%c unrecognized - ignored\n", 
 
329
        CmdName, c);
 
330
      break;
 
331
    }
 
332
  }
 
333
  argv += optind;
 
334
  argc -= optind;
 
335
  
 
336
  if (argc) Files = argv;
 
337
}
 
338
 
 
339
static Agraph_t*
 
340
gread (FILE* fp)
 
341
{
 
342
  return agread(fp,(Agdisc_t*)0);
 
343
}
 
344
 
 
345
int 
 
346
main(int argc, char **argv)
 
347
{
 
348
  Agraph_t*     g;
 
349
  ingraph_state ig;
 
350
 
 
351
  scanArgs(argc,argv);
 
352
  newIngraph (&ig, Files, gread);
 
353
  
 
354
  while ((g = nextGraph(&ig)) != 0) {
 
355
    if (agisdirected(g)) process (g);
 
356
    else fprintf (stderr, "Graph %s in %s is undirected - ignored\n", 
 
357
      agnameof(g), fileName(&ig));
 
358
    agclose (g);
 
359
  }
 
360
 
 
361
  return 0;
 
362
}
 
363