20-CS-122-001 Computer Science II Spring 2012
Homework Assignment 6

Virtual functions, classes, inheritance, lists, queues, stacks, applications

Minimize Hops Between Two Cities

Due: May 19, 2012 (submit instructions: here)

 

Rationale:

We use several instances of the Queue class (given below) to solve a fundamental optimization problem.

Purpose:

Use classes in a meaningful way, to represent objects. Read input data from a file; make multiple passes through the data file to avoid using constants to establish memory for data structures. Understand that a queue is used primarily to simulate simultaneity.

Background:

As you know, there are many cities in the United States of America. Some cities are directly connected to other cities by fiber optic cables. By directly connected I mean if one end of a single FO cable is in one city (call it Ca) and the other end is in another city (call it Cb) then cities Ca and Cb are directly connected. One city may be directly connected to several other cities but usually not more than ten others.

Electronic messages can be sent between two cities that are directly connected. Messages can also be sent between two cities, say Co and Cd, that are not directly connected provided there is a sequence of cities {c1,c2,...,cn} such that, for all i={1,2,..n-1}, ci and ci+1 are directly connected, Co is directly connected to c1, and cn is directly connected to Cd. Call such a connecting sequence of cities a path between Co and Cd. Call each of the cities c1,...,cn on a path an intermediate city. A message may travel along a path from Co to intermediate city c1 and so on to intermediate city cn and finally to cd. There may be many possible paths between a given pair of cities but every message uses exactly one path in order to get from its city of origin to its destination city.

Although messages move rapidly from one end of a FO cable to the other, they encounter a significant delay when they are switched from one FO cable to another in an intermediate city. Hence, a message taking a path with fewest intermediate cities will arrive in less time than a message taking any other path (between the same two cities) with more intermediate cities even if such a path covers fewer miles.

Now, suppose a communications company wants to choose the fastest communications route between a specified pair of cities for a given customer. That is, the communications company wants to select a path connecting specified cities Co and Cd over which messages reach their destination in the shortest time (minimum number of intermediate cities encountered) compared to all other possible paths between those cities. Your job will be to provide a program that can choose the best path. The company will run your code and construct routing tables for the customer from the result.

The Homework Problem:

Write a C++ program which finds fastest paths for the communications company. The program will take the following as input:

  1. A subset S of all cities in the USA with at least one FO cable.
  2. A collection of pairs of cities from S such that any two cities in S are directly connected if and only if they are both members of a given pair.
  3. Two distinguished cities, Co and Cd, in S representing the cities the customer wishes to send messages between.
The program will output a sequence of intermediate cities which are the ones encountered when traversing the fastest (least number of intermediate cities) path between Co and Cd.

Demo:

Try this  

Analysis:

Use "path objects" to keep track of a path as it is extended from one city to the next. Let each path object contain a "from" variable that points backward to the city from which the path is extended.

Here is an idea for an algorithm:

  1. Start with all cities unmarked.
  2. Mark Co "visiting"
  3. Construct a path object for Co.
  4. Repeat the following until Cd is marked "visiting."
  5.   For all cities cv marked "visiting" do this:
  6.     For each unmarked city cu directly connected to cv do this:
  7.       Construct a path object for cu.
  8.       Set its "from" variable to point to the path object of cv.
  9.       Mark cu "visiting."
 10.     Mark cv "done."
 11. From the path object of Cd follow "from" links back
     to the path object of Co outputting the identity
     of each city encountered on the way.

Why does this work? The statements between lines labeled 5 and 10 are expected to be executed many times. We can talk about the first iteration of execution or the second or, in general, the ith iteration of these lines. Every city that is marked "visiting" by line 9 on the ith iteration is a minimum number i "hops" away from Co and this fact does not change in future iterations. Therefore, when Cd is marked "visiting," it is a number of "hops" away from Co equal to the iteration on which this marking occurred and tracing the "from" variables of path objects back from that of Cd reveals a sequence of cities corresponding to a minimum length path of intermediate cities.

But, how can we implement a C++ solution efficiently? We need some way to keep track of all cities that are marked "visiting" on a particular iteration of the algorithm. We also need some way to maintain arbitrarily long "neighbor" lists for each city (all directly connected cities are neighbors). The use of Queues can solve both problems. Construct one Queue to store path objects and one Queue per city to store neighbors.

Consider the Queue of path objects. When a path object is placed into the Queue, this has the effect of marking the corresponding city "visiting." When a path object is taken from the Queue, this has the effect of marking the city "done."

Consider the Queue of neighbors. When a path object is removed from the path object Queue, one path object is created for each of its corresponding city's neighbors and that path object is placed into the path object Queue (that is, the corresponding city is marked "visiting"). How can we be sure that other path objects are not created later for the neighbors? Answer: by deleting the neighbor Queue of a city that is changing its marking from "visiting" to "done."

Here is sample code for implementing a Queue:

class Cell {
friend ostream & operator<<(ostream & out, Queue &lst);
friend class Queue;
   Cell *next; void *object;
 public:
   Cell (void *o, Cell *n) { next = n; object = o; }
};

class Queue {
friend ostream & operator<<(ostream & out, Queue &que);
   Cell *tail;

public:
   Queue() { tail = NULL;  }

   void enqueue(void *t) {
      if (t == NULL) return;
      if (tail == NULL) {
         tail = new Cell(t, NULL);
         tail->next = tail;
      } else {
         Cell *h = new Cell(t, tail->next);
         tail->next = h;
         tail = h;
      }
   }

   void *dequeue() {
      if (tail == NULL) return NULL;
      Cell *ptr = tail->next;
      void *t = ptr->object;
      if (ptr != tail) tail->next = ptr->next; else tail = NULL;
      delete ptr;
      return t;
   }

   int isEmpty() {  return tail == NULL;  }
};

ostream & operator<<(ostream & out, Queue &que) {
   Cell *t;
   if (que.isEmpty()) { 
      out << "(empty)";
   } else {
      for (Cell *ptr=que.tail->next ; ptr != que.tail ; ptr=ptr->next)
	 out << *((int *)(ptr->object)) << " ";
      out << *((int *)(que.tail->object));
   }   
   out << "\n";
   return out;
}

Organization of Solution Using Queues:

  1.  Declare a City class with neighbor queue.
  2.  Create City objects from file information.
  3.  Build City object neighbor queues from file information.
  4.  Establish a global "event" queue.
  5.  Mark the origin City object and put it into the event queue.
  6.  Repeat the following as long as the event queue is not empty:
  7.    Dequeue a "current" City object from the event queue.
  8.    Repeat until the current object's neighbor queue is empty:
  9.      Dequeue a "neighbor" City object from the neighbor queue.
 10.      If the neighbor object is the destination City object:
 11.        Set a back link to the current object from the neighbor object.
 12.        Trace trough all back links to output a solution.
 13.        Terminate.
 14.      Otherwise, if the neighbor object is not marked:
 15.        Mark the neighbor object and put it into the event queue.
 16.        Set a back link to the current object from the neighbor object.
 17.  If execution made it to here, there is no route to the destination. 

Requirements:

  1. Functional requirements:
    1. The program shall read a text file and display the results to the console.
    2. The input file shall be identified on the command line (that is, use int main(int argc, char **argv)).
    3. The input file shall contain printable ascii characters only plus newline characters for terminating a line.
    4. Enumerate all cities from 0 to n-1 (assuming there are n such cities given). The 0th line shall name all the components and subassemblies to be represented by vertices. All names are to be separated by blanks. The line shall end with a '-' character after a blank. The first name corresponds to object 0, the second to object 1 and so on. The 0th city will be assumed to be the city of origin and the n-1st city will be assumed to be the city of destination.
    5. Each additional line of the input file shall contain a sequence of positive integers, separated by blanks, with a blank-separated terminating character of '-'. The ith line (after the 0th) is the list of cities directly connected to the i-1st city.
    6. See hops.10.dat for an example input file.
    7. The output will consist of a list of identities of cities in the order they should be visited from the city of origin to the destination city. See hops.result.10 for the output corresponding to the above problem.

  2. Performance requirements:
    1. Time: Less than 1 second to read a 10000 object file such as hops.10000.dat on a hard drive of 20 MB/s throughput (solution to this example is: Origin: 0 Destin: 9999 path: 9999 9967 9819 9697 3877 0). Less than 1 second to solve a 10000 city input averaging less than 10 direct connections per city on a 1 GHz or faster i386 or compatible architecture.
    2. Space: Less than 2MB of RAM for 10000 objects.

  3. Implementation requirements:
    1. Use a City class to hold city data and methods.
      class City {
         Queue *q;       // List of cities this one is directly connected to
         City  *from;    // To trace a path back to origin
         char  *name;    // Name of the city 
         bool   mark;    // false=unmarked, true=visiting or done
      	
       public:
         City () { q = new Queue();  from = NULL;  mark = false;  name = NULL; }
         void setName (char *name);
         void neighbor (City *c) { q->enqueue(c); }
         City *next () { return (City *)q->dequeue(); }
      	
         void displayBestRoute ();  // displays route back to city of origin
      
         ~City () { delete q; if (name != NULL) delete name; }
      };
      

    2. Use a DataOrganizer class to read data from file.

      class DataOrganizer {
         int count;      // Counts the number of cities
         char name[128]; // accepts input from the file
         City **cities;
      
      public:
        DataOrganizer () { count = 0; }
      
         // File format: 
         //---------------------------------------------------
         // First line: a list of names, space separated, ending in -
         // Remaining lines: list of numbers ending in -
         // There should be as many names as rows after the first line.
         // The first name has identity 0, the second 1 and so on
         // The number lists use those numbers to connect cities.
         // In the example below, city 0 (Cincinnati) connects to 
         // cities 2 (Cleveland), 3 (Chicago), 7 (not shown); city 1
         // (Columbus) connects to cities 0 (Cincinnati), 2 (Cleveland)
         // and 3 (Chicago), and so on.
         // Origin city is city 0, destination city is city count-1
         //---------------------------------------------------
         // Cincinnati Columbus Cleveland Chicago ... -
         // 2 3 7 -
         // 0 2 3 -
         // 0 3 6 -
         // 0 2 5 -
         // ...
         void readInput (char *filename);
         City *getOrigin() { return cities[0]; }
         City *getDestination() { return cities[count-1]; }
      };
      

    3. The above can be used in main.

      int main (int argc, char **argv) {
         if (argc != 2) {
            cout << "Usage: " << argv[0] << " \n";
            exit(0);
         }
      
         DataOrganizer dao;
         dao.readInput(argv[1]);
      
         // Set origin and destination cities 
         City *origin = dao.getOrigin();
         City *destin = dao.getDestination();
         City *city;
         Queue *q = new Queue ();  // Simulate simultaneity
      
         origin->setMark();
         q->enqueue(origin);
         while (!q->isEmpty()) {
            ...
         }
         cout << "No Route Between Selected Cities\n";
      }