CS 32, Fall 2017

Programming Assignment 2

Due: Monday November 27, 11:59pm
Worth: 100 points

PA2 can be done either in two-people teams or individually. Be sure to type your name(s) in a comment at the top of each source code file you submit. And if you are a team, then properly form a group for this project in the submit.cs system.

1. [70 points] Define, implement and test a class named wtdgraph as a derived class of graph (from PA1) to solve the first part of the problem suggested in Chapter 15 Programming Project 5 (p. 780) of the Data Structures textbook by Main and Savitch. You must begin with your graph.h and graph.cpp files from PA1, and you must create a new file named wtdgraph.h for this assignment. Specifically:
   1. Edit graph.h (and possibly graph.cpp) as follows:
      • In graph.h, mark the destructor and the resize function as virtual functions. The reason for doing so will be discussed in lecture. Define them as follows:

                virtual ~graph();
                virtual void resize(size_t new_allocation);

        (Where size_t is actually std::size_t of course.)
      • Assuming your class graph has a private variable to store the current allocation, make this variable available to derived classes somehow. Our solution has a protected access method for that purpose, and because it is implemented inline, there was no need to make any changes to our graph.cpp file.
      • You may make other changes to class graph if necessary, as long as you do not eliminate any existing parts of its public interface. Our solution did not require any other changes though.
   2. Write both the definition of class wtdgraph and its implementation in wtdgraph.h (no need to pretend we are hiding information by implementing in a separate file this time). Here are some specifications and hints for wtdgraph.h:
      • Use a "macro guard" to prevent multiple inclusions of this header file in an application (i.e., #ifndef WTDGRAPH_H ...).
      • The class header must be exactly the following:

            template <class Item>
            class wtdgraph : public graph<Item>

      • You will need to devise a way to store the edge weights. Caution: a huge 2-dimensional array on the free store probably won't work for large graphs (such an array of size_t weights is much larger than the array of bool values you are probably using to keep track of the edges' existence now). You may use any of the standard library tools. We used a dynamic array of map objects in our solution, where the map at position i held the indexes and weights of vertex i's neighbors.
      • Define all the same constructors that are defined in the base class. Also define a destructor and assignment operator in class wtdgraph.
      • You can just inherit many of the graph member functions (i.e., no need to even mention them in wtdgraph), but you will need to redefine some functions. In our solution we redefined add_edge (see below), remove_edge and resize, in addition to the constructors, destructor and assignment operator.
      • The add_edge function needs a third parameter now, so it can be passed an edge weight, but you should give a default value of 0 to this parameter as in the following:

                void add_edge(size_t source, size_t target,
                              size_t weight = 0);

      • Add a new member function that provides access to an edge's weight as follows:

                size_t edge_weight(size_t source,
                                   size_t target) const;

        The precondition for this function is that is_edge(source, target) returns true. Use assert to verify it.
      • Remember: implement the functions below the class definition in wtdgraph.h
   3. Compile and test your class at CSIL (by connecting remotely is okay). We strongly suggest you create your own test program, so that you can individually test each of your functions. When you are ready for more comprehensive tests, you may try out the non-interactive test program that we will use to grade this part of your project, wtdexam.cpp. Compile it as follows (and heed any warning messages):

      g++ -std=c++11 -Wall -o wtdexam wtdexam.cpp

      Give a test number, 1 to 5, as a command line argument when you run it (like graphexam from PA1).
2. [30 points] Write a new file named paths.cpp to implement the function named shortest as it is defined in paths.h. This problem is a slight variation of the second part of Programming Project 5 (p. 780), a single function that finds both the shortest distances and shortest paths from a source vertex to all other vertices to which the source is connected. The graph vertex labels will always be type string, so this is not a template function.
   1. Implement Dijkstra's shortest-distance algorithm that is described on pp. 765-775 of the Data Structures textbook by Main and Savitch. Begin implementing function shortest by filling the vector named distances with the shortest distances from the start vertex to every vertex in the graph. Specifically: (1) distances[start] should be 0; (2) if vertex v is reachable from the start vertex, then distances[v] should be the shortest distance from start to v; and (3) if there is no path from start to v, then distances[v] should be set to INF (the constant defined in paths.h to represent infinity).
   2. Implement Dijkstra's shortest-path algorithm that is described on pp. 775-776 of the same textbook. Finish implementing function shortest to fill the vector named paths with lists of vertex numbers representing paths from the start vertex to other vertices. If there is no path from vertex start to vertex v, then paths[v] is an empty list. Otherwise, paths[v] is a list of vertex numbers ordered to show the path from start to v, inclusive.
   Feel free to write helper functions in paths.cpp. We had one to find the closest vertex, for example.

   Compile and test your implementation at CSIL. Again you would benefit from writing your own test program, but you can also try out the non-interactive test program we'll use to grade this part of your project, pathsexam.cpp. This application processes airport routes stored in two files: "airports.txt" has one airport code per line; and "routes.txt" has one line for each route, where each line contains the starting and ending airport codes followed by the distance in miles between them. You can easily create small, sample airports and routes files to test your code. When ready for larger tests, here are actual data for U.S. airports and associated routes. Compile the application as follows:

   g++ -std=c++11 -Wall -o pathsexam pathsexam.cpp paths.cpp

   Give a test number, 1 or 2, and a starting airport code as command line arguments when you run it. For example, the following command will execute test number 2 for LAX:

   ./pathsexam 2 LAX

   Also expect lots of output for most starting airports if you use the U.S. data files.
   P.S. Ask the instructor to demonstrate his world airport data during lecture.

3. You will turn in all of wtdgraph.h, paths.cpp, graph.h and graph.cpp. From our class page at https://submit.cs.ucsb.edu/, click the "Make Submission" button next to PA2, or use the following command from a CS terminal:

   ~submit/submit -p 868 graph.cpp graph.h paths.cpp wtdgraph.h

   Be sure to wait for the results of all tests. If you score 100/100, and you've followed all of the other rules, then you'll earn full credit.

---

Prepared 11/6/2017 by Michael Costanzo