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#include "config.h"
15
16#include <stdio.h>
17#include <stdlib.h>
18#include <math.h>
19#include "cgraph.h"
20#include "ingraphs.h"
21#include <getopt.h>
22
23#ifndef HUGE
24/* HUGE is not defined on 64bit HP-UX */
25#define HUGE HUGE_VAL
26#endif
27
28static char *CmdName;
29static char **Files;
30static char **Nodes;
31static int setall = 0; /* if false, don't set dist attribute for
32 * nodes in different components.
33 */
34static int doPath = 0; /* if 1, record shortest paths */
35static int doDirected; /* if 1, use directed paths */
36static Agsym_t *len_sym;
37
38typedef struct nodedata_s {
39 Agrec_t hdr;
40 double dist; /* always positive for scanned nodes */
41 Agnode_t* prev;
42 int done; /* > 0 if finished */
43} nodedata_t;
44
45#if 0
46typedef struct edgedata_s {
47 Agrec_t hdr;
48 double length; /* non-negative */
49 int init; /* non-zero if length is set */
50} edgedata_t;
51#endif
52
53static double getlength(Agedge_t * e)
54{
55 double len;
56 char* lens;
57 char* p;
58
59 if (len_sym && (*(lens = agxget(e, len_sym)))) {
60 len = strtod (lens, &p);
61 if ((len < 0) || (p == lens))
62 len = 1;
63 }
64 else
65 len = 1;
66 return len;
67}
68
69#ifdef USE_FNS
70static double getdist(Agnode_t * n)
71{
72 nodedata_t *data;
73 data = (nodedata_t *) (n->base.data);
74 return data->dist;
75}
76
77static void setdist(Agnode_t * n, double dist)
78{
79 nodedata_t *data;
80 data = (nodedata_t *) (n->base.data);
81 data->dist = dist;
82}
83#else
84#define getdist(n) (((nodedata_t*)((n)->base.data))->dist)
85#define setdist(n,d) (((nodedata_t*)((n)->base.data))->dist = (d))
86#define getprev(n) (((nodedata_t*)((n)->base.data))->prev)
87#define setprev(n,p) (((nodedata_t*)((n)->base.data))->prev = (p))
88#define isDone(n) (((nodedata_t*)((n)->base.data))->done)
89#define setDone(n) (((nodedata_t*)((n)->base.data))->done = 1)
90#endif
91
92static int cmpf(Dt_t * d, void *key1, void *key2, Dtdisc_t * disc)
93{
94 double t;
95 t = getdist((Agnode_t *) key1) - getdist((Agnode_t *) key2);
96 if (t < 0)
97 return -1;
98 if (t > 0)
99 return 1;
100 if (key1 < key2)
101 return -1;
102 if (key1 > key2)
103 return 1;
104 return 0;
105}
106
107static Dtdisc_t MyDisc = {
108 0, /* int key */
109 0, /* int size */
110 -1, /* int link */
111 0, /* Dtmake_f makef */
112 0, /* Dtfree_f freef */
113 cmpf, /* Dtcompar_f comparf */
114 0, /* Dthash_f hashf */
115 0, /* Dtmemory_f memoryf */
116 0 /* Dtevent_f eventf */
117};
118
119static Agnode_t *extract_min(Dict_t * Q)
120{
121 Agnode_t *rv;
122 rv = dtfirst(Q);
123 dtdelete(Q, rv);
124 return rv;
125}
126
127static void update(Dict_t * Q, Agnode_t * dest, Agnode_t * src, double len)
128{
129 double newlen = getdist(src) + len;
130 double oldlen = getdist(dest);
131
132 if (oldlen == 0) { /* first time to see dest */
133 setdist(dest, newlen);
134 if (doPath) setprev(dest, src);
135 dtinsert(Q, dest);
136 } else if (newlen < oldlen) {
137 dtdelete(Q, dest);
138 setdist(dest, newlen);
139 if (doPath) setprev(dest, src);
140 dtinsert(Q, dest);
141 }
142}
143
144static void pre(Agraph_t * g)
145{
146 len_sym = agattr(g, AGEDGE, "len", NULL);
147 aginit(g, AGNODE, "dijkstra", sizeof(nodedata_t), 1);
148#if 0
149 aginit(g, AGEDGE, "dijkstra", sizeof(edgedata_t), 1);
150#endif
151}
152
153static void post(Agraph_t * g)
154{
155 Agnode_t *v;
156 Agnode_t *prev;
157 char buf[256];
158 char dflt[256];
159 Agsym_t *sym;
160 Agsym_t *psym = NULL;
161 double dist, oldmax;
162 double maxdist = 0.0; /* maximum "finite" distance */
163
164 sym = agattr(g, AGNODE, "dist", "");
165 if (doPath)
166 psym = agattr(g, AGNODE, "prev", "");
167
168 if (setall)
169 sprintf(dflt, "%.3lf", HUGE);
170
171 for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
172 dist = getdist(v);
173 if (dist) {
174 dist--;
175 sprintf(buf, "%.3lf", dist);
176 agxset(v, sym, buf);
177 if (doPath && (prev = getprev(v)))
178 agxset(v, psym, agnameof(prev));
179 if (maxdist < dist)
180 maxdist = dist;
181 } else if (setall)
182 agxset(v, sym, dflt);
183 }
184
185 sym = agattrsym(g, "maxdist");
186 if (sym) {
187 if (!setall) {
188 /* if we are preserving distances in other components,
189 * check previous value of maxdist.
190 */
191 oldmax = atof(agxget(g, sym));
192 if (oldmax > maxdist)
193 maxdist = oldmax;
194 }
195 sprintf(buf, "%.3lf", maxdist);
196 agxset(g, sym, buf);
197 } else {
198 sprintf(buf, "%.3lf", maxdist);
199 agattr(g, AGRAPH, "maxdist", buf);
200 }
201
202 agclean(g, AGNODE, "dijkstra");
203 agclean(g, AGEDGE, "dijkstra");
204}
205
206void dijkstra(Dict_t * Q, Agraph_t * G, Agnode_t * n)
207{
208 Agnode_t *u;
209 Agedge_t *e;
210
211 pre(G);
212 setdist(n, 1);
213 dtinsert(Q, n);
214 if (doDirected) {
215 while ((u = extract_min(Q))) {
216 setDone (u);
217 for (e = agfstout(G, u); e; e = agnxtout(G, e)) {
218 if (!isDone(e->node)) update(Q, e->node, u, getlength(e));
219 }
220 }
221 } else {
222 while ((u = extract_min(Q))) {
223 setDone (u);
224 for (e = agfstedge(G, u); e; e = agnxtedge(G, e, u)) {
225 if (!isDone(e->node)) update(Q, e->node, u, getlength(e));
226 }
227 }
228 }
229 post(G);
230}
231
232static char *useString =
233 "Usage: dijkstra [-ap?] <node> [<file> <node> <file>]\n\
234 -a - for nodes in a different component, set dist very large\n\
235 -d - use forward directed edges\n\
236 -p - attach shortest path info\n\
237 -? - print usage\n\
238If no files are specified, stdin is used\n";
239
240static void usage(int v)
241{
242 printf("%s",useString);
243 exit(v);
244}
245
246static void init(int argc, char *argv[])
247{
248 int i, j, c;
249
250 CmdName = argv[0];
251 opterr = 0;
252 while ((c = getopt(argc, argv, "adp")) != -1) {
253 switch (c) {
254 case 'a':
255 setall = 1;
256 break;
257 case 'd':
258 doDirected = 1;
259 break;
260 case 'p':
261 doPath = 1;
262 break;
263 case '?':
264 if (optopt == '?')
265 usage(0);
266 else
267 fprintf(stderr, "%s: option -%c unrecognized - ignored\n",
268 CmdName, optopt);
269 break;
270 }
271 }
272 argv += optind;
273 argc -= optind;
274
275 if (argc == 0) {
276 fprintf(stderr, "%s: no node specified\n", CmdName);
277 usage(1);
278 }
279 Files = malloc(sizeof(char *) * (argc / 2 + 2));
280 Nodes = malloc(sizeof(char *) * (argc / 2 + 2));
281 for (j = i = 0; i < argc; i++) {
282 Nodes[j] = argv[i++];
283 Files[j] = (argv[i] ? argv[i] : "-");
284 j++;
285 }
286 Nodes[j] = Files[j] = 0;
287}
288
289static Agraph_t *gread(FILE * fp)
290{
291 return agread(fp, (Agdisc_t *) 0);
292}
293
294int main(int argc, char **argv)
295{
296 Agraph_t *g;
297 Agnode_t *n;
298 ingraph_state ig;
299 int i = 0;
300 int code = 0;
301 Dict_t *Q;
302
303 init(argc, argv);
304 newIngraph(&ig, Files, gread);
305
306 Q = dtopen(&MyDisc, Dtoset);
307 while ((g = nextGraph(&ig)) != 0) {
308 dtclear(Q);
309 if ((n = agnode(g, Nodes[i], 0)))
310 dijkstra(Q, g, n);
311 else {
312 fprintf(stderr, "%s: no node %s in graph %s in %s\n",
313 CmdName, Nodes[i], agnameof(g), fileName(&ig));
314 code = 1;
315 }
316 agwrite(g, stdout);
317 fflush(stdout);
318 agclose(g);
319 i++;
320 }
321 exit(code);
322}
323