Programeer opdrachtenOpdracht : opdr5_ptr.txt

Terug naar de inzendingen
Opdracht 5,Peter Postma
17 April 2005
 Mijn inzending voor de routekaart staat hier:
 http://www.pointless.nl/~peter/development/opdracht5/Makefile
 http://www.pointless.nl/~peter/development/opdracht5/opdracht5.c
 
 Het .c bestand is voorzien van een beschrijving onder de licentie. Alles is
 wel in het engels, ik hoop niet dat dat erg is.
 
 Verder was het een erg leuke opdracht, het is de eerste keer dat ik Dijkstra's
 algoritme implementeer en het viel niet mee moet ik eerlijk zeggen. Maar het
 is me nu wel helemaal duidelijk hoe dit algoritme werkt.
 
 Als laatste nog 2 opmerkingen over de opdracht:
 
 1) Zoals ik al eerder had opgemerkt kloppen de wegen niet in de opdracht,
 uiteraard klopt dit wel in mijn programma.
 
 2) In de opdracht staat dat de afstand tussen A en E 3.1 is. Mijn programma
 zal echter 3.2 aangeven omdat deze naar boven afrond (de afstand met 6 cijfers
 achter de komma is 3.162278).
 1 
****Makefile*****
  
 2PROG= opdracht5
 3SRC= opdracht5.c
 4
 5CC?= cc
 6CFLAGS?=-Wall
 7LIBS= -lm
 8
 9all:
 10 $(CC) $(CFLAGS) $(LIBS) -o $(PROG) $(SRC)
 11
 12clean:
 13 rm -f $(PROG) *.core
 1 
*****opdracht5.c*****
  
 2/*
 3 * Copyright (c) 2005 Peter Postma 
 4 * All rights reserved.
 5 *
 6 * Redistribution and use in source and binary forms, with or without
 7 * modification, are permitted provided that the following conditions
 8 * are met:
 9 * 1. Redistributions of source code must retain the above copyright
 10 *    notice, this list of conditions and the following disclaimer.
 11 * 2. Redistributions in binary form must reproduce the above copyright
 12 *    notice, this list of conditions and the following disclaimer in the
 13 *    documentation and/or other materials provided with the distribution.
 14 *
 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 18 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 25 * SUCH DAMAGE.
 26 */
 27
 28/*
 29 * Description:
 30 *   This program calculates the shortest path between two points in a graph.
 31 *   It uses Dijkstra's algorithm to accomplish this. The points and links
 32 *   between the points (ways) are both defined in a structure and can be
 33 *   extended very easily. This program is used as submission for Pascals
 34 *   programming assignment #5.
 35 *
 36 * Language:
 37 *   ANSI C
 38 *
 39 * Written by:
 40 *   Peter Postma , on 12 - 17 April 2005.
 41 *
 42 * License:
 43 *   See above.
 44 *
 45 * Usage:
 46 *   Compile with a C89 compliant C compiler and make sure to link to the
 47 *   math library: $ cc -Wall -lm -o opdracht5 opdracht5.c
 48 *
 49 *   Or just typ 'make' to start the compile process.
 50 *
 51 *   The program wants two arguments, point1 and point2 which are both
 52 *   single characters between A and F, e.g.: $ ./opdracht5 e b
 53 */
 54
 55#include 
 56
 57#include 
 58#include 
 59#include 
 60#include 
 61#include 
 62#include 
 63
 64#define arraycount(x) (sizeof(x) / sizeof(x[0]))
 65
 66/* Define the points. */
 67static struct point {
 68 char p;
 69 int x, y;
 70} points[] = {
 71 { 'A', 1, 0 },
 72 { 'B', 4, 0 },
 73 { 'C', 1, 2 },
 74 { 'D', 2, 2 },
 75 { 'E', 0, 3 },
 76 { 'F', 4, 3 }
 77};
 78
 79/* Define the ways. */
 80static struct way {
 81 char p1, p2;
 82} ways[] = {
 83 { 'A', 'C' },
 84 { 'A', 'E' },
 85 { 'B', 'D' },
 86 { 'C', 'D' },
 87 { 'D', 'F' },
 88 { 'F', 'E' }
 89};
 90
 91/* Structure for the vertex. */
 92struct vertex {
 93 struct point *p; /* reference to points */
 94 struct way *edges; /* array with ways for the point */
 95 size_t nedges;  /* number of ways */
 96 double distance; /* total distance */
 97 size_t predecessor; /* vertex predecessor */
 98 int done;  /* completion indicator */
 99};
 100
 101/*
 102 * get_point --
 103 * Find the point p. Returns a pointer to the point when found,
 104 * or NULL when not found.
 105 */
 106static struct point *
 107get_point(char p)
 108{
 109 size_t i;
 110
 111 for (i = 0; i < arraycount(points); i++)
 112  if (points[i].p == p)
 113   return &points[i];
 114 return NULL;
 115}
 116
 117/*
 118 * get_index --
 119 * Returns the array index of the next point in struct way.
 120 */
 121static size_t
 122get_index(struct way *w, char current)
 123{
 124 return ((current == w->p2) ? w->p1 : w->p2) - 'A';
 125}
 126
 127/*
 128 * calc_weight --
 129 * Calculates the weight for a way (distance between two points).
 130 */
 131static double
 132calc_weight(struct way *w)
 133{
 134 struct point *p1, *p2;
 135
 136 p1 = get_point(w->p1);
 137 p2 = get_point(w->p2);
 138
 139 if (p1 == NULL || p2 == NULL)
 140  return 0.0;
 141
 142 return sqrt(pow(p1->x - p2->x, 2) + pow(p1->y - p2->y, 2));
 143}
 144
 145/*
 146 * calc_shortest_path --
 147 * Calculate the shortest path in graph g, from p1 to p2 using
 148 * Dijkstra's algorithm. Returns the distance of shortest path as
 149 * double. If the route is invalid, the function will return INT_MAX.
 150 * The graph g will be modified during operation and will be filled
 151 * with the distance and predecessor(s) of each vertex.
 152 */
 153static double
 154calc_shortest_path(struct vertex *g, size_t count, char p1, char p2)
 155{
 156 size_t i, j, cur, index, start = 0;
 157 double weight, min, shortest;
 158
 159 for (i = 0; i < count; i++) {
 160  if (g[i].p->p == p1) {
 161   start = i;
 162   g[i].distance = 0;
 163  } else
 164   g[i].distance = INT_MAX;
 165  g[i].done = 0;
 166  g[i].predecessor = UINT_MAX;
 167 }
 168
 169 cur = start;
 170
 171 while (!g[cur].done && g[cur].p->p != p2) {
 172  min = INT_MAX;
 173
 174  for (j = 0; j < g[cur].nedges; j++) {
 175   index = get_index(&g[cur].edges[j], g[cur].p->p);
 176   weight = calc_weight(&g[cur].edges[j]);
 177
 178   if (g[index].distance > g[cur].distance + weight) {
 179    g[index].distance = g[cur].distance + weight;
 180    g[index].predecessor = cur;
 181   }
 182  }
 183  g[cur].done = 1;
 184
 185  cur = start;
 186  min = INT_MAX;
 187
 188  for (j = 0; j < count; j++) {
 189   if (!g[j].done && min >= g[j].distance) {
 190    min = g[j].distance;
 191    cur = j;
 192   }
 193  }
 194 }
 195
 196 shortest = INT_MAX;
 197 for (i = 0; i < count; i++) {
 198  if (p2 == g[i].p->p) {
 199   shortest = g[i].distance;
 200   break;
 201  }
 202 }
 203
 204 return shortest;
 205}
 206
 207/*
 208 * main --
 209 * Main entry point.
 210 */
 211int
 212main(int argc, char *argv[])
 213{
 214 size_t size, start, cur, num, i, j;
 215 struct vertex *g; /* array of vertices: graph */
 216 double shortest;
 217 char p1, p2;
 218 char *route;
 219
 220 if (argc != 3) {
 221  fprintf(stderr, "Usage: %s point1 point2\n", argv[0]);
 222  exit(EXIT_FAILURE);
 223 }
 224
 225 if (strlen(argv[1]) != 1 || strlen(argv[2]) != 1) {
 226  fprintf(stderr,
 227      "Point1 and point2 should be a single character.\n");
 228  exit(EXIT_FAILURE);
 229 }
 230
 231 p1 = toupper((unsigned char)*argv[1]);
 232 p2 = toupper((unsigned char)*argv[2]);
 233
 234 /* Validate the points. */
 235 if (get_point(p1) == NULL || get_point(p2) == NULL) {
 236  fprintf(stderr, "Invalid point(s), must be between A and
 237F.\n");
 238  exit(EXIT_FAILURE);
 239 }
 240
 241 /* Bogus, point1 and point2 are the same. */
 242 if (p1 == p2) {
 243  fprintf(stderr,
 244      "Points are the same, no route to calculate.\n");
 245  exit(EXIT_FAILURE);
 246 }
 247
 248 size = arraycount(points);
 249 g = malloc(size * sizeof(struct vertex));
 250 if (g == NULL) {
 251  fprintf(stderr, "Failed to allocate memory.\n");
 252  exit(EXIT_FAILURE);
 253 }
 254
 255 /*
 256  * Fill the graph g with all points. For every vertex, calculate all
 257  * ways and add these to the edges array.
 258  */
 259 for (i = 0; i < size; i++) {
 260  g[i].p = &points[i];
 261  for (num = 0, j = 0; j < arraycount(ways); j++) {
 262   if (g[i].p->p == ways[j].p1 ||
 263       g[i].p->p == ways[j].p2)
 264    num++;
 265  }
 266  if (num > 0) {
 267   /* Allocate an array of pointers. */
 268   g[i].edges = malloc(num * sizeof(struct way *));
 269   if (g[i].edges == NULL) {
 270    fprintf(stderr, "Failed to allocate
 271memory.\n");
 272    exit(EXIT_FAILURE);
 273   }
 274   for (cur = 0, j = 0; j < arraycount(ways); j++) {
 275    if (g[i].p->p == ways[j].p1 ||
 276        g[i].p->p == ways[j].p2)
 277     g[i].edges[cur++] = ways[j];
 278   }
 279  }
 280  g[i].nedges = num;
 281 }
 282
 283 /* Calculate the shortest path. */
 284 shortest = calc_shortest_path(g, size, p1, p2);
 285
 286 if (shortest == INT_MAX) {
 287  printf("Invalid route from %c to %c\n", p1, p2);
 288 } else {
 289  printf("The shortest route from %c to %c is %.1f\n",
 290      p1, p2, shortest);
 291
 292  /*
 293   * Show the route from p1 to p2. We can only read the route
 294   * in the graph backwards, so we'll need to store it in a
 295   * temporary buffer.
 296   */
 297
 298  /* Start at the last point. */
 299  start = UINT_MAX;
 300  for (i = 0; i < size; i++) {
 301   if (g[i].p->p == p2) {
 302    start = i;
 303    break;
 304   }
 305  }
 306  if (start == UINT_MAX) {
 307   /* Should never happen. */
 308   printf("Unable to find the route.");
 309
 310  } else {
 311   /* First count all points in the path. */
 312   num = 0;
 313   cur = start;
 314   do {
 315    num++;
 316    cur = g[cur].predecessor;
 317   } while (cur != UINT_MAX);
 318
 319   route = malloc(num * sizeof(char));
 320   if (route == NULL) {
 321    fprintf(stderr, "Failed to allocate
 322memory.\n");
 323    exit(EXIT_FAILURE);
 324   }
 325
 326   /* Store the route in the array. */
 327   i = num;
 328   cur = start;
 329   do {
 330    route[--i] = g[cur].p->p;
 331    cur = g[cur].predecessor;
 332   } while (cur != UINT_MAX);
 333
 334   /* Finally, print the route. */
 335   printf("Route: ");
 336   for (i = 0; i < num - 1; i++)
 337    printf("%c -> ", route[i]);
 338   printf("%c\n", route[i]);
 339  }
 340 }
 341
 342 return 0;
 343}
 344