/* File: cityroutes.c * Desc: Implementation of routing functions * Anthony Towns * 15 August 1997 */ #include "cityroutes.h" #include #include bool isIn( cityPath path, City city ) { int i; /* Is the city /city/ in the cityPath /path/? * Find out with this simple linear search! * * Yours today for only $19.95. * * But wait! There's more! If you compile with the standard DEBUG * macro defined, you'll get not one, not two, but, on average, * more than _n over two_ useful and valuable assertions! * * Compile now. This great offer _can't_ last. */ /* is the city valid? */ assert( 0 <= city && city < NoCity ); for ( i = 0; i < path.n_visited; i++ ) { /* is this city in the path valid? */ assert( 0 <= path.stop[i] && path.stop[i] < NoCity ); if ( path.stop[i] == city ) return TRUE; } return FALSE; } bool connected( City source, City destination, FlightRouteType routes ) { enum { notConnected, connected, checked } connect_to_source[ MAXCITIES ]; City i, j; bool changed; /* did anything get changed this iteration? */ /* This is a very brute-forcish algorithm. * * It looks through each city connected to the source city, then * marks any nodes connected to that city as connected to the * source, and repeats. * * It could be optimized in two ways: * * 1) Since it works out _every_ city connected to /source/, * the /connect_to_source/ array could be saved between calls. * (care will be needed if there are three (or more) sets of * mutually unreachable cities, however) * * 2) It could exit early by checking when * /connect_to_source[destination]/ is set to 1. */ /* both source and destination are valid cities */ assert( 0 <= source && source < NoCity ); assert( 0 <= destination && destination < NoCity ); /* so far, we only know the source city is connected to the, uh, * source city */ for ( i = 0; i < NoCity; i++ ) connect_to_source[i] = notConnected; connect_to_source[ source ] = connected; do { changed = FALSE; /* have we changed anything this time? Not * yet, that's for sure. */ for ( i = 0; i < NoCity; i++ ) { /* nothing nasty has happened to our connection array, * has it? */ assert( connect_to_source[i] == notConnected || connect_to_source[i] == connected || connect_to_source[i] == checked ); if ( connect_to_source[i] == connected ) { for ( j = 0; j < NoCity; j++ ) { if ( routes[i][j] && connect_to_source[j] == notConnected ) { changed = TRUE; connect_to_source[j] = connected; } } connect_to_source[i] = checked; } } } while( changed ); return connect_to_source[destination]; } void add_steps( cityPath path, stack *steps, FlightRouteType routes ) { City i; cityPair build_step; /* We need to find where we can go from here. We do this by * searching through all the cities, and, if we can get there * directly and we haven't already been there, we go there. */ /* precondition: we are somewhere, aren't we? */ assert( path.n_visited >= 1 ); /* precondition: and wherever we are is a valid city, right? */ assert( 0 <= path.stop[ path.n_visited - 1 ] && path.stop[ path.n_visited - 1 ] < NoCity ); for ( i = 0; i < NoCity; i++ ) { /* for each city */ /* if there's a step to it, and we haven't already visited * it */ if ( routes[ path.stop[ path.n_visited - 1 ] ][ i ] && !isIn( path, i ) ) { /* routes should be irreflexive */ assert( path.stop[ path.n_visited - 1 ] != i ); /* push this step onto our stack */ build_step.from = path.stop[ path.n_visited - 1]; build_step.to = i; push( steps, build_step ); } } } void take_step( cityPath* path, stack* untaken_steps ) { cityPair build; /* precondition: there must be a step to take */ assert( !isEmpty( *untaken_steps ) ); /* find the most recently noted step */ pop( untaken_steps, &build ); /* precondition: our current path _must_ include the step's * departure point. */ assert( isIn( *path, build.from ) ); /* backtrack until we're at this departure point */ while ( path->stop[ path->n_visited - 1 ] != build.from ) { path->n_visited--; } /* ...and, finally, actually step! */ path->stop[ path->n_visited++ ] = build.to; } int path_distance( cityPath path, FlightRouteType routes ) { int distance = 0; int i; /* work out how far it was from the start */ for ( i = 1; i < path.n_visited; i++ ) { /* each step should be valid */ assert( routes[path.stop[i-1]][path.stop[i]] > 0 ); distance += routes[path.stop[i-1]][path.stop[i]]; } return distance; } cityPath shortest_path( City source, City destination, FlightRouteType routes ) { cityPath shortest; int shortest_distance = 0; /* since no path can have a distance of zero (a zero in the * routes table indicates no step between the two cities), we * use a value of zero here to indicate that we haven't found * a shortest path yet. */ stack untaken_steps; /* other directions we could've taken */ cityPath visited; /* where we've gone */ /* precondition: both source and destination are valid cities */ assert( 0 <= source && source < NoCity ); assert( 0 <= destination && destination < NoCity ); /* precondition */ assert( source != destination ); /* precondition */ assert( connected( source, destination, routes ) ); newStack( &untaken_steps ); /* initialize stack */ /* The first point in the path is where we start. */ visited.stop[0] = source; visited.n_visited = 1; for(;;) { #ifdef DEBUG { int i, j, k; /* invariant (a) */ assert( visited.n_visited > 0 && visited.stop[0] == source ); fprintf( stderr, "%s", cityName[ visited.stop[0] ] ); for ( i = 1; i < visited.n_visited; i++ ) { fprintf( stderr, " --> %s", cityName[ visited.stop[i] ] ); for ( j = 0; j < i; j++ ) { /* invariant (b) */ assert( visited.stop[i] != visited.stop[j] ); } /* invariant (c) */ assert( routes[visited.stop[i]][visited.stop[i-1]] ); } fprintf( stderr, ".\n" ); /* The following requires internal knowledge of the * citystk implementation!!! */ j = 0; for ( i = 0; i < untaken_steps.nElems; i++ ) { /* invariant (d) */ assert( routes[ untaken_steps.elem[i].from ] [ untaken_steps.elem[i].to ] ); /* invariants (e) and (g) */ while ( visited.stop[j] != untaken_steps.elem[i].from ) { j++; assert( j < visited.n_visited ); } /* invariant (f) */ for ( k = 0; k < j; k++ ) { assert( visited.stop[k] != untaken_steps.elem[i].to ); } /* invariant (h) */ for ( k = 0; k < i; k++ ) { assert( untaken_steps.elem[i].to != untaken_steps.elem[k].to || untaken_steps.elem[i].from != untaken_steps.elem[k].from ); } } } #endif if ( visited.stop[visited.n_visited - 1] != destination ) { /* if we're not where we want to be, note down * everywhere we can go from here. */ add_steps( visited, &untaken_steps, routes ); } else { /* if we are there, we don't need to note down the * places we could go from here, but we do need to * check whether where we have gone is the shortest * path so far. */ int distance = path_distance( visited, routes ); if ( distance < shortest_distance || shortest_distance == 0 ) { shortest = visited; shortest_distance = distance; } } /* if we haven't got any more steps noted down to take, then * we've taken all steps we could, so we're done! */ if ( isEmpty( untaken_steps ) ) break; /* but if we did have some more steps, we'd better keep * trying them... * * note: our current path includes the next step's departure * point, because this is one of the steps we could have * taken originally, and we haven't backed up past that city * yet, because only more recent steps are (were) higher up * on the stack. */ take_step( &visited, &untaken_steps ); } /* And now, the culmination of all our efforts, that single line * of code that makes it all worthwhile: all the false starts, * all the dead ends and all the paths that were just too damn * long; the line of code that gives this function it's purpose * and it's name. */ return shortest; }