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#include "config.h"
21
22#ifdef HAVE_UNISTD_H
23#include <unistd.h>
24#endif
25#include <stdio.h>
26
27#include <stdlib.h>
28#include "cgraph.h"
29typedef struct {
30 Agrec_t h;
31 int mark;
32 int onstack;
33} Agnodeinfo_t;
34
35#define ND_mark(n) (((Agnodeinfo_t*)((n)->base.data))->mark)
36#define ND_onstack(n) (((Agnodeinfo_t*)((n)->base.data))->onstack)
37#define graphName(g) (agnameof(g))
38
39#include <getopt.h>
40
41static FILE *inFile;
42static FILE *outFile;
43static int doWrite = 1;
44static int Verbose;
45static char *cmd;
46static int num_rev;
47
48/* addRevEdge:
49 * Add a reversed version of e. The new edge has the same key.
50 * We also copy the attributes, reversing the roles of head and
51 * tail ports.
52 * This assumes we've already checked that such an edge does not exist.
53 */
54static void addRevEdge(Agraph_t * g, Agedge_t * e)
55{
56 Agsym_t* sym;
57 Agedge_t* f = agedge (g, aghead(e), agtail(e), agnameof(e), 1);
58
59 agcopyattr (e, f);
60
61 num_rev++;
62 sym = agattr (g, AGEDGE, TAILPORT_ID, 0);
63 if (sym) agsafeset (f, HEADPORT_ID, agxget (e, sym), "");
64 sym = agattr (g, AGEDGE, HEADPORT_ID, 0);
65 if (sym) agsafeset (f, TAILPORT_ID, agxget (e, sym), "");
66}
67
68/* dfs:
69 * Return the number of reversed edges for this component.
70 */
71static int dfs(Agraph_t * g, Agnode_t * t, int hasCycle)
72{
73 Agedge_t *e;
74 Agedge_t *f;
75 Agnode_t *h;
76
77 ND_mark(t) = 1;
78 ND_onstack(t) = 1;
79 for (e = agfstout(g, t); e; e = f) {
80 f = agnxtout(g, e);
81 if (agtail(e) == aghead(e))
82 continue;
83 h = aghead(e);
84 if (ND_onstack(h)) {
85 if (agisstrict(g)) {
86 if (agedge(g, h, t, 0, 0) == 0)
87 addRevEdge(g, e);
88 } else {
89 char* key = agnameof (e);
90 if (!key || (agedge(g, h, t, key, 0) == 0))
91 addRevEdge(g, e);
92 }
93 agdelete(g, e);
94 hasCycle = 1;
95 } else if (ND_mark(h) == 0)
96 hasCycle |= dfs(g, h, hasCycle);
97 }
98 ND_onstack(t) = 0;
99 return hasCycle;
100}
101
102static char *useString = "Usage: %s [-nv?] [-o outfile] <file>\n\
103 -o <file> - put output in <file>\n\
104 -n - do not output graph\n\
105 -v - verbose\n\
106 -? - print usage\n";
107
108static void usage(int v)
109{
110 fprintf(stderr, useString, cmd);
111 exit(v);
112}
113
114static FILE *openFile(char *name, char *mode)
115{
116 FILE *fp;
117 char *modestr;
118
119 fp = fopen(name, mode);
120 if (!fp) {
121 if (*mode == 'r')
122 modestr = "reading";
123 else
124 modestr = "writing";
125 fprintf(stderr, "%s: could not open file %s for %s\n",
126 cmd, name, modestr);
127 exit(-1);
128 }
129 return (fp);
130}
131
132static void init(int argc, char *argv[])
133{
134 int c;
135
136 cmd = argv[0];
137 opterr = 0;
138 while ((c = getopt(argc, argv, ":vno:")) != -1)
139 switch (c) {
140 case 'o':
141 outFile = openFile(optarg, "w");
142 break;
143 case 'n':
144 doWrite = 0;
145 break;
146 case 'v':
147 Verbose = 1;
148 break;
149 case '?':
150 if (optopt == '?')
151 usage(0);
152 else {
153 fprintf(stderr, "%s: option -%c unrecognized\n", cmd,
154 optopt);
155 usage(-1);
156 }
157 break;
158 case ':':
159 fprintf(stderr, "%s: missing argument for option -%c\n",
160 cmd, optopt);
161 usage(-1);
162 break;
163 }
164 if (optind < argc) {
165 inFile = openFile(argv[optind], "r");
166 } else
167 inFile = stdin;
168 if (!outFile)
169 outFile = stdout;
170
171}
172
173int main(int argc, char *argv[])
174{
175 Agraph_t *g;
176 Agnode_t *n;
177 int rv = 0;
178
179 init(argc, argv);
180
181 if ((g = agread(inFile, (Agdisc_t *) 0)) != 0) {
182 if (agisdirected (g)) {
183 aginit(g, AGNODE, "info", sizeof(Agnodeinfo_t), TRUE);
184 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
185 if (ND_mark(n) == 0)
186 rv |= dfs(g, n, 0);
187 }
188 if (doWrite) {
189 agwrite(g, outFile);
190 fflush(outFile);
191 }
192 if (Verbose) {
193 if (rv)
194 fprintf(stderr, "Graph \"%s\" has cycles; %d reversed edges\n", graphName(g), num_rev);
195 else
196 fprintf(stderr, "Graph \"%s\" is acyclic\n", graphName(g));
197 }
198 } else {
199 rv = -1;
200 if (Verbose)
201 fprintf(stderr, "Graph \"%s\" is undirected\n", graphName(g));
202 }
203 exit(rv);
204 } else
205 exit(-1);
206}
207