git.sur5r.net Git - cc65/blob - test/ref/dijkstra.c

   1 /*
   2   !!DESCRIPTION!! Dijkstras Algorithm
   3   !!ORIGIN!!      testsuite
   4   !!LICENCE!!     Public Domain
   5   !!AUTHOR!!      Groepaz/Hitmen
   6 */
   7
   8 #include <stdio.h>
   9 #include <stdlib.h>
  10
  11 #ifndef NULL
  12 #define NULL ((void*)0)
  13 #endif
  14
  15 #define DIJKSTRA_INFINITY       (0xffff)
  16
  17 #define DIJKSTRA_FLAG_UNVISITED (0x0)
  18 /*
  19 #define DIJKSTRA_FLAG_OPEN      (0x1)
  20 */
  21 #define DIJKSTRA_FLAG_CLOSED    (0x2)
  22
  23 typedef struct _DIJKSTRA_EDGE {
  24     struct _DIJKSTRA_NODE *NEXTNODE;
  25     unsigned short DISTANCE;
  26 } DIJKSTRA_EDGE;
  27
  28 typedef struct _DIJKSTRA_NODE {
  29     DIJKSTRA_EDGE *EDGES;
  30     unsigned char  TAG;
  31     unsigned char  FLAG;
  32     unsigned short MINDIST;
  33     struct _DIJKSTRA_NODE *PREVIOUS;
  34 } DIJKSTRA_NODE;
  35
  36 /* init with graph, startnode, working-array */
  37 void Dijkstra_Init(const DIJKSTRA_NODE *graph,DIJKSTRA_NODE *start,DIJKSTRA_NODE *nodes);
  38
  39 /* call main algo with working-array */
  40 void Dijkstra_Search(DIJKSTRA_NODE *nodes);
  41
  42 /* print path, call with working-array, endnode */
  43 void Dijkstra_Path(DIJKSTRA_NODE *nodes,DIJKSTRA_NODE *end);
  44
  45 /* print table, call with working-array, current node */
  46 void Dijkstra_Table(DIJKSTRA_NODE *nodes,DIJKSTRA_NODE *current);
  47
  48 /* internally used routines */
  49
  50 unsigned short Dijkstra_Distance(DIJKSTRA_NODE *currnode,DIJKSTRA_NODE *nextnode);
  51 void Dijkstra_Relax(DIJKSTRA_NODE *currnode,DIJKSTRA_NODE *nextnode);
  52 DIJKSTRA_NODE *Dijkstra_NextCheapest(DIJKSTRA_NODE *graph);
  53 unsigned short Dijkstra_CountUnvisited(DIJKSTRA_NODE *graph);
  54
  55 /* define to get printed info as the algorithm proceeds */
  56 #define DIJKSTRA_PRINTDEBUG
  57
  58 /* the working array */
  59 DIJKSTRA_NODE mynodes[0x10];
  60
  61 /* test-network data (mypoints and myedges) */
  62
  63 const DIJKSTRA_EDGE myedges_A[]={
  64     {&mynodes[1],1},
  65     {NULL}
  66 };
  67 const DIJKSTRA_EDGE myedges_B[]={
  68     {&mynodes[0],1},
  69     {&mynodes[2],2},
  70     {&mynodes[3],1},
  71     {NULL}
  72 };
  73 const DIJKSTRA_EDGE myedges_C[]={
  74     {&mynodes[1],2},
  75     {&mynodes[5],1},
  76     {NULL}
  77 };
  78 const DIJKSTRA_EDGE myedges_D[]={
  79     {&mynodes[1],1},
  80     {&mynodes[4],1},
  81     {NULL}
  82 };
  83 const DIJKSTRA_EDGE myedges_E[]={
  84     {&mynodes[6],1},
  85     {NULL}
  86 };
  87 const DIJKSTRA_EDGE myedges_F[]={
  88     {&mynodes[7],1},
  89     {NULL}
  90 };
  91 const DIJKSTRA_EDGE myedges_G[]={
  92     {&mynodes[8],1},
  93     {&mynodes[7],4},
  94     {NULL}
  95 };
  96 const DIJKSTRA_EDGE myedges_H[]={
  97     {&mynodes[9],1},
  98     {&mynodes[6],4},
  99     {NULL}
 100 };
 101 const DIJKSTRA_EDGE myedges_I[]={
 102     {&mynodes[10],5},
 103     {NULL}
 104 };
 105 const DIJKSTRA_EDGE myedges_J[]={
 106     {&mynodes[10],1},
 107     {NULL}
 108 };
 109 const DIJKSTRA_EDGE myedges_K[]={
 110     {&mynodes[11],1},
 111     {NULL}
 112 };
 113 const DIJKSTRA_EDGE myedges_L[]={
 114     {&mynodes[10],1},
 115     {NULL}
 116 };
 117
 118 const DIJKSTRA_NODE mypoints[]={
 119     {(DIJKSTRA_EDGE *)&myedges_A[0],'A'},
 120     {(DIJKSTRA_EDGE *)&myedges_B[0],'B'},
 121     {(DIJKSTRA_EDGE *)&myedges_C[0],'C'},
 122     {(DIJKSTRA_EDGE *)&myedges_D[0],'D'},
 123     {(DIJKSTRA_EDGE *)&myedges_E[0],'E'},
 124     {(DIJKSTRA_EDGE *)&myedges_F[0],'F'},
 125     {(DIJKSTRA_EDGE *)&myedges_G[0],'G'},
 126     {(DIJKSTRA_EDGE *)&myedges_H[0],'H'},
 127     {(DIJKSTRA_EDGE *)&myedges_I[0],'I'},
 128     {(DIJKSTRA_EDGE *)&myedges_J[0],'J'},
 129     {(DIJKSTRA_EDGE *)&myedges_K[0],'K'},
 130     {(DIJKSTRA_EDGE *)&myedges_L[0],'L'},
 131     {NULL}
 132 };
 133
 134 /*
 135  *      initialize working-array
 136  */
 137
 138 void Dijkstra_Init(const DIJKSTRA_NODE *graph,DIJKSTRA_NODE *start,DIJKSTRA_NODE *nodes) {
 139     while(graph->EDGES!=NULL) {
 140         nodes->EDGES=graph->EDGES;
 141         nodes->TAG=graph->TAG;
 142         nodes->FLAG=DIJKSTRA_FLAG_UNVISITED;
 143         nodes->MINDIST=DIJKSTRA_INFINITY;
 144         nodes->PREVIOUS=NULL;
 145
 146         graph++;nodes++;
 147
 148     }
 149 /*
 150     start->FLAG=DIJKSTRA_FLAG_OPEN;
 151     start->PREVIOUS=NULL;
 152  */
 153     start->MINDIST=0;
 154 }
 155
 156 /*
 157  *      compute the distance between two Nodes in the Graph
 158  */
 159
 160 unsigned short Dijkstra_Distance(DIJKSTRA_NODE *currnode,DIJKSTRA_NODE *nextnode){
 161 DIJKSTRA_EDGE *edge;
 162
 163     edge=currnode->EDGES;
 164
 165     while(edge!=NULL) {
 166         if(edge->NEXTNODE == nextnode){
 167             return(edge->DISTANCE);
 168         }
 169
 170         edge++;
 171
 172     }
 173
 174     return(DIJKSTRA_INFINITY);
 175 }
 176
 177 /*
 178  *      'relax' one node against another
 179  */
 180
 181 void Dijkstra_Relax(DIJKSTRA_NODE *currnode,DIJKSTRA_NODE *nextnode){
 182 unsigned short newdist;
 183
 184 #ifdef DIJKSTRA_PRINTDEBUG
 185     printf("relax >%c< to >%c<\n",currnode->TAG,nextnode->TAG);
 186 #endif
 187
 188     newdist=currnode->MINDIST+Dijkstra_Distance(currnode,nextnode);
 189
 190     if((nextnode->MINDIST)>(newdist)){
 191         nextnode->MINDIST=newdist;
 192         nextnode->PREVIOUS=currnode;
 193
 194     }
 195 }
 196
 197 /*
 198  *      find the yet unprocessed Node with the currently
 199  *      smallest estimated MINDIST
 200  */
 201
 202 DIJKSTRA_NODE *Dijkstra_NextCheapest(DIJKSTRA_NODE *graph){
 203 unsigned short mindist;
 204 DIJKSTRA_NODE *node;
 205
 206     node=NULL;
 207     mindist=DIJKSTRA_INFINITY;
 208
 209     while(graph->EDGES!=NULL) {
 210         if(graph->FLAG!=DIJKSTRA_FLAG_CLOSED){
 211             if(!(mindist<graph->MINDIST)){
 212                      mindist=graph->MINDIST;
 213                      node=graph;
 214             }
 215         }
 216
 217         graph++;
 218
 219     }
 220
 221 #ifdef DIJKSTRA_PRINTDEBUG
 222     if(node!=NULL) printf("next cheapest Node: >%c<\n",node->TAG);
 223 #endif
 224
 225     return(node);
 226 }
 227
 228 /*
 229  *      count number of Nodes that are left for processing
 230  */
 231
 232 unsigned short Dijkstra_CountUnvisited(DIJKSTRA_NODE *graph){
 233 unsigned short num;
 234
 235     num=0;
 236
 237     while(graph->EDGES!=NULL) {
 238         if(graph->FLAG!=DIJKSTRA_FLAG_CLOSED){
 239             num++;
 240         }
 241
 242         graph++;
 243
 244     }
 245
 246     return(num);
 247 }
 248
 249 /*
 250  *      Dijkstra-Algorithmus main processing
 251  */
 252
 253 void Dijkstra_Search(DIJKSTRA_NODE *graph){
 254 DIJKSTRA_NODE *currnode,*nextnode;
 255 DIJKSTRA_EDGE *edge;
 256
 257     currnode=graph;
 258
 259     while(Dijkstra_CountUnvisited(graph)>0){
 260         edge=currnode->EDGES;
 261         while(edge->NEXTNODE!=NULL){
 262             nextnode=edge->NEXTNODE;
 263             if(nextnode->FLAG!=DIJKSTRA_FLAG_CLOSED){
 264 /*
 265    nextnode->FLAG=DIJKSTRA_FLAG_OPEN;
 266  */
 267                 Dijkstra_Relax(currnode,nextnode);
 268 #ifdef DIJKSTRA_PRINTDEBUG
 269                 Dijkstra_Table(graph,currnode);
 270 #endif
 271             }
 272             edge++;
 273         }
 274         currnode=Dijkstra_NextCheapest(graph);
 275         currnode->FLAG=DIJKSTRA_FLAG_CLOSED;
 276     }
 277 }
 278
 279 /*
 280  *      print the Path from start Node to one other Node
 281  */
 282
 283 void Dijkstra_Path(DIJKSTRA_NODE *graph,DIJKSTRA_NODE *end){
 284 DIJKSTRA_NODE *currnode,*nextnode;
 285
 286     printf("Path from >%c< to >%c< : ",end->TAG,graph->TAG);
 287
 288     currnode=end;
 289
 290         while(currnode->PREVIOUS!=NULL){
 291             printf(">%c< ",currnode->TAG);
 292             currnode=currnode->PREVIOUS;
 293         }
 294
 295     printf(">%c<\n",currnode->TAG);
 296 }
 297
 298 /*
 299  *      print working-array as a table
 300  */
 301
 302 void Dijkstra_Table(DIJKSTRA_NODE *graph,DIJKSTRA_NODE *current){
 303 DIJKSTRA_NODE *g;
 304
 305     printf("----------------------\n");
 306
 307     printf("Node    |");
 308     g=graph;while(g->EDGES!=NULL) {
 309         printf("-->%c<-|",g->TAG);
 310         g++;
 311     }
 312     printf("\n");
 313
 314     printf("MinDist |");
 315     g=graph;while(g->EDGES!=NULL) {
 316         printf(" %5u|",g->MINDIST);
 317         g++;
 318     }
 319     printf("\n");
 320
 321     printf("Flag    |");
 322     g=graph;while(g->EDGES!=NULL) {
 323         switch(g->FLAG){
 324 /*
 325             case DIJKSTRA_FLAG_OPEN:
 326                 printf("opened|");
 327                 break;
 328  */
 329             case DIJKSTRA_FLAG_CLOSED:
 330                 printf("closed|");
 331                 break;
 332             default:
 333                 if(g->MINDIST!=DIJKSTRA_INFINITY){
 334                     printf("opened|");
 335                 } else {
 336                     printf("------|");
 337                 }
 338                 break;
 339         }
 340         g++;
 341     }
 342     printf("\n");
 343
 344     printf("Previous|");
 345     g=graph;while(g->EDGES!=NULL) {
 346         if(g->PREVIOUS==NULL)
 347             printf("------|");
 348         else
 349             printf("  (%c) |",g->PREVIOUS->TAG);
 350         g++;
 351     }
 352     printf("\n");
 353
 354     printf("----------------------\n");
 355 }
 356
 357 int main(void)
 358 {
 359     /* init with graph, startnode, working-array */
 360     Dijkstra_Init(&mypoints[0],&mynodes[0],&mynodes[0]);
 361     /* call main algo with working-array */
 362     Dijkstra_Search(&mynodes[0]);
 363     /* print table, call with working-array, endnode */
 364     Dijkstra_Table(&mynodes[0],&mynodes[11]);
 365     /* print path, call with working-array, endnode */
 366     Dijkstra_Path(&mynodes[0],&mynodes[11]);
 367
 368     return 0;
 369 }