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
12
13/*
14 * Written by Stephen North
15 * Updated by Emden Gansner
16 */
17
18/*
19 * reads a sequence of graphs on stdin, and writes their
20 * transitive reduction on stdout
21 */
22
23#include "config.h"
24
25#include "cgraph.h"
26#include "arith.h"
27#include "timing.h"
28#include <stdlib.h>
29
30#define NEW(t) (t*)malloc(sizeof(t))
31#define N_NEW(n,t) (t*)malloc((n)*sizeof(t))
32
33typedef struct {
34 unsigned char on_stack;
35 unsigned char dist;
36} nodeinfo_t;
37
38#define ON_STACK(ninfo,n) (ninfo[AGSEQ(n)].on_stack)
39#define DIST(ninfo,n) (ninfo[AGSEQ(n)].dist)
40#define agrootof(n) ((n)->root)
41
42#ifdef HAVE_UNISTD_H
43#include <unistd.h>
44#endif
45#include "ingraphs.h"
46
47#include <getopt.h>
48
49static char **Files;
50static char *CmdName;
51static int Verbose;
52
53typedef struct blk_t {
54 Agedge_t **data;
55 Agedge_t **endp;
56 struct blk_t *prev;
57 struct blk_t *next;
58} blk_t;
59
60typedef struct {
61 blk_t *fstblk;
62 blk_t *curblk;
63 Agedge_t **curp;
64} stk_t;
65
66#define SMALLBUF 1024
67#define BIGBUF 1000000
68
69typedef struct {
70 Agedge_t *base[SMALLBUF];
71 blk_t Blk;
72 stk_t Stk;
73} estack_t;
74
75
76static void initStk(estack_t* sp)
77{
78 sp->Blk.data = sp->base;
79 sp->Blk.endp = sp->Blk.data + SMALLBUF;
80 sp->Stk.curblk = sp->Stk.fstblk = &(sp->Blk);
81 sp->Stk.curp = sp->Stk.curblk->data;
82}
83
84static void push(estack_t* sp, Agedge_t * ep, nodeinfo_t* ninfo)
85{
86 if (sp->Stk.curp == sp->Stk.curblk->endp) {
87 if (sp->Stk.curblk->next == NULL) {
88 blk_t *bp = NEW(blk_t);
89 if (bp == 0) {
90 fprintf(stderr, "%s: Out of memory\n", CmdName);
91 exit(1);
92 }
93 bp->prev = sp->Stk.curblk;
94 bp->next = NULL;
95 bp->data = N_NEW(BIGBUF, Agedge_t *);
96 if (bp->data == 0) {
97 fprintf(stderr, "%s: Out of memory\n", CmdName);
98 exit(1);
99 }
100 bp->endp = bp->data + BIGBUF;
101 sp->Stk.curblk->next = bp;
102 }
103 sp->Stk.curblk = sp->Stk.curblk->next;
104 sp->Stk.curp = sp->Stk.curblk->data;
105 }
106 ON_STACK(ninfo, aghead(ep)) = 1;
107 *sp->Stk.curp++ = ep;
108}
109
110static Agedge_t *pop(estack_t* sp, nodeinfo_t* ninfo)
111{
112 Agedge_t* e;
113 if (sp->Stk.curp == sp->Stk.curblk->data) {
114 if (sp->Stk.curblk == sp->Stk.fstblk)
115 return 0;
116 sp->Stk.curblk = sp->Stk.curblk->prev;
117 sp->Stk.curp = sp->Stk.curblk->endp;
118 }
119 sp->Stk.curp--;
120 e = *sp->Stk.curp;
121 ON_STACK(ninfo,aghead(e)) = 0;
122 return e;
123}
124
125static Agedge_t *top(estack_t* sp)
126{
127 Agedge_t** pp;
128 if (sp->Stk.curp == sp->Stk.curblk->data) {
129 if (sp->Stk.curblk == sp->Stk.fstblk)
130 return 0;
131 pp = sp->Stk.curblk->prev->endp-1;
132 }
133 else
134 pp = sp->Stk.curp-1;
135 return *pp;
136}
137
138/* dfs:
139 * Main function for transitive reduction.
140 * This does a DFS starting at node n. Each node records the length of
141 * its largest simple path from n. We only care if the length is > 1. Node
142 * n will have distance 0; outneighbors of n will have distance 1 or 2; all
143 * others will have distance 2.
144 *
145 * During the DFS, we only push edges on the stack whose head has distance 0
146 * (i.e., hasn't been visited yet), setting its distance to the distance of the
147 * tail node plus one. If we find a head node with distance 1, we don't push the
148 * edge, since it has already been in a DFS, but we update its distance. We also
149 * check for back edges and report these.
150 *
151 * After the DFS, we check all outedges of n. Those edges whose head has
152 * distance 2 we delete. We also delete all but one copy of any edges with the
153 * same head.
154 */
155static int dfs(Agnode_t * n, nodeinfo_t* ninfo, int warn, estack_t* sp)
156{
157 Agraph_t *g = agrootof(n);
158 Agedgepair_t dummy;
159 Agedge_t* link;
160 Agedge_t* next;
161 Agedge_t* prev;
162 Agedge_t* e;
163 Agedge_t* f;
164 Agnode_t* v;
165 Agnode_t* hd;
166 Agnode_t* oldhd;
167
168 dummy.out.base.tag.objtype = AGOUTEDGE;
169 dummy.out.node = n;
170 dummy.in.base.tag.objtype = AGINEDGE;
171 dummy.in.node = NULL;
172
173 push(sp, &dummy.out, ninfo);
174 prev = 0;
175
176 while ((link = top(sp))) {
177 v = aghead(link);
178 if (prev)
179 next = agnxtout(g, prev);
180 else
181 next = agfstout(g, v);
182 for (; next; next = agnxtout(g, next)) {
183 hd = aghead(next);
184 if (hd == v) continue; // Skip a loop
185 if (ON_STACK(ninfo,hd)) {
186 if (!warn) {
187 warn++;
188 fprintf(stderr,
189 "warning: %s has cycle(s), transitive reduction not unique\n",
190 agnameof(g));
191 fprintf(stderr, "cycle involves edge %s -> %s\n",
192 agnameof(v), agnameof(hd));
193 }
194 }
195 else if (DIST(ninfo,hd) == 0) {
196 DIST(ninfo,hd) = MIN(1,DIST(ninfo,v))+1;
197 break;
198 }
199 else if (DIST(ninfo,hd) == 1) {
200 DIST(ninfo,hd) = MIN(1,DIST(ninfo,v))+1;
201 }
202 }
203 if (next) {
204 push(sp, next, ninfo);
205 prev = 0;
206 }
207 else {
208 prev = pop(sp, ninfo);
209 }
210 }
211 oldhd = NULL;
212 for (e = agfstout(g, n); e; e = f) {
213 f = agnxtout(g, e);
214 hd = aghead(e);
215 if (oldhd == hd)
216 agdelete(g, e);
217 else {
218 oldhd = hd;
219 if (DIST(ninfo, hd)>1) agdelete(g, e);
220 }
221 }
222 return warn;
223}
224
225static char *useString = "Usage: %s [-v?] <files>\n\
226 -v - verbose\n\
227 -? - print usage\n\
228If no files are specified, stdin is used\n";
229
230static void usage(int v)
231{
232 printf(useString, CmdName);
233 exit(v);
234}
235
236static void init(int argc, char *argv[])
237{
238 int c;
239
240 CmdName = argv[0];
241 opterr = 0;
242 while ((c = getopt(argc, argv, "v")) != -1) {
243 switch (c) {
244 case 'v':
245 Verbose = 1;
246 break;
247 case '?':
248 if (optopt == '?')
249 usage(0);
250 else
251 fprintf(stderr, "%s: option -%c unrecognized - ignored\n",
252 CmdName, optopt);
253 break;
254 }
255 }
256 argv += optind;
257 argc -= optind;
258
259 if (argc)
260 Files = argv;
261}
262
263/* process:
264 * Do a DFS for each vertex in graph g, so the time
265 * complexity is O(|V||E|).
266 */
267static void process(Agraph_t * g, estack_t* sp)
268{
269 Agnode_t *n;
270 int cnt = 0;
271 int warn = 0;
272 double secs;
273 double total_secs = 0;
274 nodeinfo_t* ninfo;
275 size_t infosize;
276
277 infosize = (agnnodes(g)+1)*sizeof(nodeinfo_t);
278 ninfo = (nodeinfo_t*)malloc(infosize);
279
280 if (Verbose)
281 fprintf(stderr, "Processing graph %s\n", agnameof(g));
282 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
283 memset(ninfo, 0, infosize);
284 if (Verbose) start_timer();
285 warn = dfs(n, ninfo, warn, sp);
286 if (Verbose) {
287 secs = elapsed_sec();
288 total_secs += secs;
289 cnt++;
290 if ((cnt%1000) == 0) fprintf (stderr, "[%d]\n", cnt);
291 }
292 }
293 if (Verbose)
294 fprintf(stderr, "Finished graph %s: %.02f secs.\n", agnameof(g), total_secs);
295 free (ninfo);
296 agwrite(g, stdout);
297 fflush(stdout);
298}
299
300static Agraph_t *gread(FILE * fp)
301{
302 return agread(fp, (Agdisc_t *) 0);
303}
304
305int main(int argc, char **argv)
306{
307 Agraph_t *g;
308 ingraph_state ig;
309 estack_t estk;
310
311 init(argc, argv);
312 newIngraph(&ig, Files, gread);
313 initStk(&estk);
314
315 while ((g = nextGraph(&ig)) != 0) {
316 if (agisdirected(g))
317 process(g, &estk);
318 agclose(g);
319 }
320
321 return 0;
322}
323
324