#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <agraph.h>
#include <ingraphs.h>
#ifdef HAVE_GETOPT_H
#include <getopt.h>
#else
#include "compat_getopt.h"
#endif
#define BIG HUGE
static char *CmdName;
typedef struct nodedata_s {
Agrec_t hdr;
double dist;
unsigned char inheap;
} nodedata_t;
typedef struct edgedata_s {
Agrec_t hdr;
double length;
unsigned char initialized;
} edgedata_t;
static double getlength(Agedge_t *e)
{
edgedata_t *data;
data = (edgedata_t*)(e->base.data);
if (!data->initialized) {
data->length = atof(agget(e,"len"));
if (data->length <= 0) data->length = 1.0;
data->initialized = 1;
}
return data->length;
}
static double getdist(Agnode_t *n)
{
nodedata_t *data;
data = (nodedata_t*)(n->base.data);
return data->dist;
}
static void setdist(Agnode_t *n, double dist)
{
nodedata_t *data;
data = (nodedata_t*)(n->base.data);
data->dist = dist;
}
static int cmpf(Dt_t *d, void *key1, void *key2, Dtdisc_t *disc)
{
double t;
t = getdist((Agnode_t*)key1) - getdist((Agnode_t*)key2);
if (t < 0) return -1;
if (t > 0) return 1;
if (key1 < key2) return -1;
if (key1 > key2) return 1;
return 0;
}
static Dtdisc_t MyDisc = {
0,
0,
-1,
0,
0,
cmpf,
0,
0,
0
};
static void insert(Dict_t *Q, Agnode_t *n)
{
dtinsert(Q,n);
}
static Dict_t *queue_nodes(Agraph_t *G, Agnode_t *src)
{
Agnode_t *n;
Dict_t *Q = dtopen(&MyDisc,Dtoset);
for (n = agfstnode(G); n; n = agnxtnode(n))
setdist(n,BIG);
setdist(src,0);
for (n = agfstnode(G); n; n = agnxtnode(n))
insert(Q,n);
return Q;
}
static Agnode_t *extract_min(Dict_t *Q)
{
Agnode_t *rv;
rv = dtfirst(Q);
dtdelete(Q,rv);
return rv;
}
static void update(Dict_t *Q, Agnode_t *dest, Agnode_t *src, double len)
{
double newlen;
newlen = getdist(src) + len;
if (newlen < getdist(dest)) {
dtdelete(Q,dest);
setdist(dest,newlen);
dtinsert(Q,dest);
}
}
static void pre(Agraph_t *g)
{
aginit(g,AGNODE,"dijkstra",sizeof(nodedata_t),1);
aginit(g,AGEDGE,"dijkstra",sizeof(edgedata_t),1);
}
static void post(Agraph_t *g)
{
Agnode_t *v;
char buf[16];
Agsym_t *sym;
double dist,maxdist = 0.0;
sym = agattr(g,AGNODE,"dist","");
for (v = agfstnode(g); v; v = agnxtnode(v)) {
dist = getdist(v);
sprintf(buf,"%.3lf",dist);
if (maxdist < dist) maxdist = dist;
agxset(v,sym,buf);
}
sprintf(buf,"%.3lf",maxdist);
sym = agattr(g,AGRAPH,"maxdist",buf);
agclean(g,AGNODE,"dijkstra");
agclean(g,AGEDGE,"dijkstra");
}
void dijkstra(Agraph_t *G, Agnode_t *n)
{
Dict_t *Q;
Agnode_t *u;
Agedge_t *e;
pre(G);
Q = queue_nodes(G,n);
while ((u = extract_min(Q))) {
for (e = agfstedge(u); e; e = agnxtedge(e,u)) {
update(Q,e->node,u,getlength(e));
}
}
post(G);
}
#ifdef NOTDEF
int main(int argc, char **argv)
{
Agraph_t *g;
while ((g = agread(stdin,0))) {
dijkstra(g,agfstnode(g));
agwrite(g,stdout);
}
return 1;
}
#endif
static char **Files;
static char **Nodes;
static char* useString =
"Usage: dijkstra [-?] <files>\n\
-? - print usage\n\
If no files are specified, stdin is used\n";
static void
usage (int v)
{
printf (useString);
exit (v);
}
static void
init (int argc, char* argv[])
{
int i,c;
CmdName = argv[0];
while ((c = getopt(argc, argv, ":?")) != -1) {
switch (c) {
case '?':
if (optopt == '?') usage(0);
else fprintf(stderr,"%s: option -%c unrecognized - ignored\n",CmdName, c);
break;
}
}
argv += optind;
argc -= optind;
Files = malloc(sizeof(char*) * argc/2 + 1);
Nodes = malloc(sizeof(char*) * argc/2 + 1);
for (i = 0; i + 1 < argc; i += 2) {
Nodes[i/2] = argv[i];
Files[i/2] = argv[i+1];
}
Nodes[i/2] = Files[i/2] = 0;
}
static Agraph_t*
gread (FILE* fp)
{
return agread(fp,(Agdisc_t*)0);
}
int main(int argc,char **argv)
{
Agraph_t *g;
Agnode_t *n;
ingraph_state ig;
int i = 0;
int code = 0;
init (argc, argv);
newIngraph (&ig, Files, gread);
while ((g = nextGraph(&ig)) != 0) {
if ((n = agnode(g,Nodes[i],0)))
dijkstra(g,n);
else {
fprintf(stderr,"%s: no such node as %s in graph %s in %s\n",CmdName,Nodes[i],agnameof(g),fileName(&ig));
code = 1;
}
agwrite(g,stdout);
fflush(stdout);
agclose (g);
i++;
}
exit(code);
}