Graphviz 13.1.2~dev.20250807.2324
Loading...
Searching...
No Matches
dijkstra.c
Go to the documentation of this file.
1
6/*************************************************************************
7 * Copyright (c) 2011 AT&T Intellectual Property
8 * All rights reserved. This program and the accompanying materials
9 * are made available under the terms of the Eclipse Public License v1.0
10 * which accompanies this distribution, and is available at
11 * https://www.eclipse.org/legal/epl-v10.html
12 *
13 * Contributors: Details at https://graphviz.org
14 *************************************************************************/
15
16#include "config.h"
17
18#include <stdbool.h>
19#include <stddef.h>
20#include <stdio.h>
21#include <stdlib.h>
22#include <math.h>
23#include <cgraph/cgraph.h>
24#include <cgraph/ingraphs.h>
25#include <getopt.h>
26#include <util/alloc.h>
27#include <util/exit.h>
28#include <util/unreachable.h>
29
30static char *CmdName;
31static char **Files;
32static char **Nodes;
33static bool setall; /* if false, don't set dist attribute for
34 * nodes in different components.
35 */
36static bool doPath; /* if true, record shortest paths */
37static bool doDirected; /* if true, use directed paths */
39
40typedef struct {
42 double dist; /* always positive for scanned nodes */
44 bool done;
46
47static double getlength(Agedge_t * e)
48{
49 double len;
50 char* lens;
51 char* p;
52
53 if (len_sym && (*(lens = agxget(e, len_sym)))) {
54 len = strtod (lens, &p);
55 if (len < 0 || p == lens)
56 len = 1;
57 }
58 else
59 len = 1;
60 return len;
61}
62
63static double getdist(Agnode_t * n)
64{
65 nodedata_t *const data =
66 (nodedata_t *)((char *)n->base.data - offsetof(nodedata_t, hdr));
67 return data->dist;
68}
69
70static void setdist(Agnode_t * n, double dist)
71{
72 nodedata_t *const data =
73 (nodedata_t *)((char *)n->base.data - offsetof(nodedata_t, hdr));
74 data->dist = dist;
75}
76
77#define getprev(n) (((nodedata_t*)((n)->base.data))->prev)
78#define setprev(n,p) (((nodedata_t*)((n)->base.data))->prev = (p))
79#define isDone(n) (((nodedata_t*)((n)->base.data))->done)
80#define setDone(n) (((nodedata_t*)((n)->base.data))->done = true)
81
82static int cmpf(void *key1, void *key2) {
83 const double dist1 = getdist(key1);
84 const double dist2 = getdist(key2);
85 if (dist1 < dist2)
86 return -1;
87 if (dist1 > dist2)
88 return 1;
89 if (key1 < key2)
90 return -1;
91 if (key1 > key2)
92 return 1;
93 return 0;
94}
95
96static Dtdisc_t MyDisc = {
97 0, /* int key */
98 0, /* int size */
99 -1, /* int link */
100 0, /* Dtmake_f makef */
101 0, /* Dtfree_f freef */
102 cmpf, /* Dtcompar_f comparf */
103};
104
106{
107 Agnode_t *rv;
108 rv = dtfirst(Q);
109 dtdelete(Q, rv);
110 return rv;
111}
112
113static void update(Dict_t * Q, Agnode_t * dest, Agnode_t * src, double len)
114{
115 double newlen = getdist(src) + len;
116 double oldlen = getdist(dest);
117
118 if (oldlen == 0) { /* first time to see dest */
119 setdist(dest, newlen);
120 if (doPath) setprev(dest, src);
121 dtinsert(Q, dest);
122 } else if (newlen < oldlen) {
123 dtdelete(Q, dest);
124 setdist(dest, newlen);
125 if (doPath) setprev(dest, src);
126 dtinsert(Q, dest);
127 }
128}
129
130static void pre(Agraph_t * g)
131{
132 len_sym = agattr_text(g, AGEDGE, "len", NULL);
133 aginit(g, AGNODE, "dijkstra", sizeof(nodedata_t), true);
134}
135
136static void post(Agraph_t * g)
137{
138 Agnode_t *v;
139 Agnode_t *prev;
140 char buf[256];
141 char dflt[256];
142 Agsym_t *sym;
143 Agsym_t *psym = NULL;
144 double dist, oldmax;
145 double maxdist = 0.0; /* maximum "finite" distance */
146
147 sym = agattr_text(g, AGNODE, "dist", "");
148 if (doPath)
149 psym = agattr_text(g, AGNODE, "prev", "");
150
151 if (setall)
152 snprintf(dflt, sizeof(dflt), "%.3lf", HUGE_VAL);
153
154 for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
155 dist = getdist(v);
156 if (dist) {
157 dist--;
158 snprintf(buf, sizeof(buf), "%.3lf", dist);
159 agxset(v, sym, buf);
160 if (doPath && (prev = getprev(v)))
161 agxset(v, psym, agnameof(prev));
162 if (maxdist < dist)
163 maxdist = dist;
164 } else if (setall)
165 agxset(v, sym, dflt);
166 }
167
168 sym = agattrsym(g, "maxdist");
169 if (sym) {
170 if (!setall) {
171 /* if we are preserving distances in other components,
172 * check previous value of maxdist.
173 */
174 oldmax = atof(agxget(g, sym));
175 if (oldmax > maxdist)
176 maxdist = oldmax;
177 }
178 snprintf(buf, sizeof(buf), "%.3lf", maxdist);
179 agxset(g, sym, buf);
180 } else {
181 snprintf(buf, sizeof(buf), "%.3lf", maxdist);
182 agattr_text(g, AGRAPH, "maxdist", buf);
183 }
184
185 agclean(g, AGNODE, "dijkstra");
186 agclean(g, AGEDGE, "dijkstra");
187}
188
189static void dijkstra(Dict_t * Q, Agraph_t * G, Agnode_t * n)
190{
191 Agnode_t *u;
192 Agedge_t *e;
193
194 pre(G);
195 setdist(n, 1);
196 dtinsert(Q, n);
197 if (doDirected) {
198 while ((u = extract_min(Q))) {
199 setDone (u);
200 for (e = agfstout(G, u); e; e = agnxtout(G, e)) {
201 if (!isDone(e->node)) update(Q, e->node, u, getlength(e));
202 }
203 }
204 } else {
205 while ((u = extract_min(Q))) {
206 setDone (u);
207 for (e = agfstedge(G, u); e; e = agnxtedge(G, e, u)) {
208 if (!isDone(e->node)) update(Q, e->node, u, getlength(e));
209 }
210 }
211 }
212 post(G);
213}
214
215static char *useString =
216 "Usage: dijkstra [-ap?] <node> [<file> <node> <file>]\n\
217 -a - for nodes in a different component, set dist very large\n\
218 -d - use forward directed edges\n\
219 -p - attach shortest path info\n\
220 -? - print usage\n\
221If no files are specified, stdin is used\n";
222
223static void usage(int v)
224{
225 printf("%s",useString);
226 graphviz_exit(v);
227}
228
229static void init(int argc, char *argv[])
230{
231 int i, j, c;
232
233 CmdName = argv[0];
234 opterr = 0;
235 while ((c = getopt(argc, argv, "adp?")) != -1) {
236 switch (c) {
237 case 'a':
238 setall = true;
239 break;
240 case 'd':
241 doDirected = true;
242 break;
243 case 'p':
244 doPath = true;
245 break;
246 case '?':
247 if (optopt == '\0' || optopt == '?')
248 usage(0);
249 else {
250 fprintf(stderr, "%s: option -%c unrecognized\n",
251 CmdName, optopt);
252 usage(1);
253 }
254 break;
255 default:
256 UNREACHABLE();
257 }
258 }
259 argv += optind;
260 argc -= optind;
261
262 if (argc == 0) {
263 fprintf(stderr, "%s: no node specified\n", CmdName);
264 usage(1);
265 }
266 Files = gv_calloc((size_t)argc / 2 + 2, sizeof(char *));
267 Nodes = gv_calloc((size_t)argc / 2 + 2, sizeof(char *));
268 for (j = i = 0; i < argc; i++) {
269 Nodes[j] = argv[i++];
270 Files[j] = argv[i] ? argv[i] : "-";
271 j++;
272 }
273 Nodes[j] = Files[j] = NULL;
274}
275
276int main(int argc, char **argv)
277{
278 Agraph_t *g;
279 Agnode_t *n;
280 ingraph_state ig;
281 size_t i = 0;
282 int code = 0;
283 Dict_t *Q;
284
285 init(argc, argv);
286 newIngraph(&ig, Files);
287
288 Q = dtopen(&MyDisc, Dtoset);
289 while ((g = nextGraph(&ig)) != 0) {
290 dtclear(Q);
291 if ((n = agnode(g, Nodes[i], 0)))
292 dijkstra(Q, g, n);
293 else {
294 fprintf(stderr, "%s: no node %s in graph %s in %s\n",
295 CmdName, Nodes[i], agnameof(g), fileName(&ig));
296 code = 1;
297 }
298 agwrite(g, stdout);
299 fflush(stdout);
300 agclose(g);
301 i++;
302 }
303 free(Nodes);
304 free(Files);
305 graphviz_exit(code);
306}
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define dtclear(d)
Definition cdt.h:188
#define dtinsert(d, o)
Definition cdt.h:185
CDT_API Dtmethod_t * Dtoset
ordered set (self-adjusting tree)
Definition dttree.c:304
#define dtdelete(d, o)
Definition cdt.h:186
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
Definition dtopen.c:9
#define dtfirst(d)
Definition cdt.h:179
abstract graph C library, Cgraph API
static void init(int argc, char *argv[])
Definition dijkstra.c:229
#define getprev(n)
Definition dijkstra.c:77
static char ** Nodes
Definition dijkstra.c:32
static Agsym_t * len_sym
Definition dijkstra.c:38
static void setdist(Agnode_t *n, double dist)
Definition dijkstra.c:70
static bool doDirected
Definition dijkstra.c:37
static void dijkstra(Dict_t *Q, Agraph_t *G, Agnode_t *n)
Definition dijkstra.c:189
#define isDone(n)
Definition dijkstra.c:79
static Agnode_t * extract_min(Dict_t *Q)
Definition dijkstra.c:105
static Dtdisc_t MyDisc
Definition dijkstra.c:96
static void update(Dict_t *Q, Agnode_t *dest, Agnode_t *src, double len)
Definition dijkstra.c:113
#define setprev(n, p)
Definition dijkstra.c:78
static bool doPath
Definition dijkstra.c:36
static char * useString
Definition dijkstra.c:215
static bool setall
Definition dijkstra.c:33
static double getlength(Agedge_t *e)
Definition dijkstra.c:47
static double getdist(Agnode_t *n)
Definition dijkstra.c:63
static int cmpf(void *key1, void *key2)
Definition dijkstra.c:82
static char ** Files
Definition dijkstra.c:31
static char * CmdName
Definition dijkstra.c:30
#define setDone(n)
Definition dijkstra.c:80
static NORETURN void graphviz_exit(int status)
Definition exit.h:23
static double dist(int dim, double *x, double *y)
#define G
Definition gdefs.h:7
static double len(glCompPoint p)
Definition glutils.c:136
void free(void *)
node NULL
Definition grammar.y:180
Agsym_t * agattr_text(Agraph_t *g, int kind, char *name, const char *value)
creates or looks up text attributes of a graph
Definition attr.c:334
Agsym_t * agattrsym(void *obj, char *name)
looks up a string attribute for a graph object given as an argument
Definition attr.c:144
int agxset(void *obj, Agsym_t *sym, const char *value)
Definition attr.c:522
char * agxget(void *obj, Agsym_t *sym)
Definition attr.c:458
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition edge.c:96
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition edge.c:87
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Definition graph.c:95
int agwrite(Agraph_t *g, void *chan)
Return 0 on success, EOF on failure.
Definition write.c:696
Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition node.c:141
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
@ AGEDGE
Definition cgraph.h:207
@ AGNODE
Definition cgraph.h:207
@ AGRAPH
Definition cgraph.h:207
void aginit(Agraph_t *g, int kind, const char *rec_name, int rec_size, int move_to_front)
attach new records to objects of specified kind
Definition rec.c:170
void agclean(Agraph_t *g, int kind, char *rec_name)
calls agdelrec for all objects of the same class in an entire graph
Definition rec.c:202
static const char * usage
Definition gvpr.c:49
$2 u p prev
Definition htmlparse.y:297
char * fileName(ingraph_state *sp)
Return name of current file being processed.
Definition ingraphs.c:154
Agraph_t * nextGraph(ingraph_state *sp)
Definition ingraphs.c:59
ingraph_state * newIngraph(ingraph_state *sp, char **files)
Definition ingraphs.c:138
supports user-supplied data
char * post
Definition maze.c:58
char * pre
Definition maze.c:32
PATHUTIL_API COORD dist2(Ppoint_t, Ppoint_t)
Definition visibility.c:120
Agnode_t * node
Definition cgraph.h:272
Agobj_t base
Definition cgraph.h:260
Agrec_t * data
stores programmer-defined data, access with AGDATA
Definition cgraph.h:212
graph or subgraph
Definition cgraph.h:424
implementation of Agrec_t
Definition cgraph.h:172
string attribute descriptor symbol in Agattr_s.dict
Definition cgraph.h:651
Definition legal.c:50
Definition cdt.h:100
double dist
Definition dijkstra.c:42
Agnode_t * prev
Definition dijkstra.c:43
Agrec_t hdr
Definition dijkstra.c:41
bool done
true if finished
Definition dijkstra.c:44
int main()
#define UNREACHABLE()
Definition unreachable.h:30