Project 3

Due Thursday July 26 at 6 p.m.

Please note that all code for this assignment must be written in C++.

To compile C++, your source file must end in the suffix ".cpp", and you will use the comiler g++ instead of gcc. You should use all the same flags with g++ that you did with gcc.

For example: g++ -ansi -Wall -pedantic -c myfile.cpp

Your code will be graded on both its correctness and its elegence. So please take the time to try to come up with short and easy to understand solutions. Please read the programming guides on the Assignments page.

Please consult the directory ~hsc/classes/270/examples/C++ on CDF. Some of the examples may prove useful in solving these problems.

1. Queues, Part 2 (20%)

This problem is a continuation of the queue problem from Project 2. In this problem, you will convert your queue program of that assignment to C++, and you will add some additional features.

Because we are now using C++, you should implement your queue as a class. However, you should still use the idea of abstract data types and place your queue functions in a separate file from the main program.

You queue should have the following functions:

1. void insert(int element);
   This function adds element to the queue.
2. int remove();
   This function returns the first element on the queue and removes that element from the queue.
3. int peek();
   This routine returns the first element on the queue, but it does not remove the element from the queue.

In addition, the queue constructor should accept a size and create a queue of the necessary size. Your queue should be implemented as a circular array. Your queue class definition should be placed into queues.h, and the implementation should be placed into queues.cpp.

Because queues are now implemented as objects, we can create more than one queue. You will take advantage of this in the main program.

You are to write a routine which accepts user input and manipulates two queues. The queues will be named "A" and "B". The size of A is 10 and the size of B is 8. Call this program use_queues.cpp. As before, the acceptable user inputs are "insert" followed by a value, "remove", and "peek". In addition, each input will contain the name of the queue. The response to "insert" is either "Ok." or "Queue is full." The response to "peek" and "remove" is either a value or "Queue is empty." If an invalid queue name is used, the response should be "Invalid queue."

Here is a sample execution:

eddie% use_queues
insert A 4
Ok.
insert B 5
Ok.
peek A
4
peek C
Invalid queue.
remove A
4
remove A
Queue is empty.
remove B
5

Submit the following files electronically: use_queues.cpp, queues.h, queues.cpp.

An intersting modification to your queue program would be to make your queues so that they will work with any data type, not just integers. To do this, you should use the template feature of C++. Because we have not covered templates, this modification is strictly optional, but it will make your program a little nicer and possibly make your life easier when we do the final project.

2. Shortest Path (80%)

For this problem, you will write a program which accepts the description of a directed graph, and then accepts pairs of vertices from the user. For each pair of vertices, the program will output the length of the shortest path followed by the path.

You will write this problem in pieces.

1. Write the files graph.cpp and graph.h which implements the abstract data type graph as a class. The abstract data type should store the graph as either an adjacency list or as an adjacency matrix, and the graph should store a length for each edge.

   The abstract type should include functions to add edges, to return whether two vertices are adjacent, and to indicate the length of such an edge.

2. Write the files shortest_path.cpp and shortest_paths.h which will implement a shortest paths algorithm. The code should take a graph and two vertices and output the shortest path from the first vertex to the second and the length of the path. If no such path exists, it is to return an error.

   You are free to implement this method anyway you wish. You may use either Dijkstra's algorithm or the All-pair Shortest Paths algorithm. To make the program efficient, you should not recalculate a shortest path. If you are using Dijkstra, you should only run the algorithm once for each vertex and store the results. Likewise, if you are using the All-pairs algorithm, you should only run it once.

3. Write the file find_path.cpp which inputs a graph description of a directed graph, then inputs pairs of vertices from the user. For each pair of vertices, the program will call shortest_paths from part 2 and then will output both the length of the shortest path and the path found.

   To input the graph, the first element of the input will be the number of vertices. We will label the vertices 0 to n-1 where n is the number of vertices. Following the number of vertices, the input will consist of a series of edges. Each edge is represented by three numbers. The first number represents the from vertex, the second number represents the to vertex and the third number represents the length of the edge. The program will continue reading edges until a -1 is encountered indicating the end of the graph description.

   After the graph description, the program will prompt the user for two vertices, output the length of the shortest path between those two vertices, and then output the path, if such a path exists. The program will then query the user for two more vertices and repeat until the user enters a negative vertex number terminating the program.

   Here is a sample execution:

   eddie% find_path
   5
   0 1 10
   0 3 5
   1 2 1
   1 3 2
   2 4 4
   3 1 3
   3 2 9
   3 4 2
   4 0 7
   4 2 6
   -1
   
   Enter two vertices >> 0 2
   The shortest path has length 9.
   The path is 0 3 1 2
   
   Enter two vertices >> -1
   Bye!
   

   The program should print "No path exists" if is impossible to get from the first vertex to the second.

   You should submit the following files: graph.cpp, graph.h, shortest_path.cpp, shortest_path.h, find_path.cpp.

   ---

   3. Street Directions (Extra Credit)

   In this problem, you will take the code you wrote for part 2 and implement a street guide.

   To represent the map, each intersection will be a vertex and each segment of street will be an edge. Note that some streets may be one way streets so we will use a directed graph.

   We will use the same method of input as we did for part 2, but besides a from vertex, to vertex, and length, each edge will also have single word labels indicating the street name, the direction it travels, and the street numbers of the buildings on that block.

   For example, this could be our graph.

   9
   0 1 9 Bloor East 200 100
   1 0 9 Bloor West 100 200
   1 2 5 Bloor East 100 50
   2 1 6 Bloor West 50 100
   3 4 4 Harbord East 200 100
   4 3 3 Harbord West 100 200
   4 5 3 Hoskin East 100 1
   5 4 3 Hoskin West 1 100
   6 7 7 College East 200 100
   7 6 7 College West 100 200
   7 8 5 College East 100 50
   8 7 6 College West 50 100
   0 3 7 Spadina South 500 400
   3 0 7 Spadina North 500 500
   3 6 5 Spadina South 400 300
   6 3 5 Spadina North 300 400
   1 4 10 St-George South 500 400
   4 1 10 St-George North 400 500
   4 7 10 St-George South 400 300
   7 4 10 St-George North 300 400
   2 5 1 Queens-Park-W South 100 50
   5 8 2 Queens-Park-W South 50 1
   8 2 3 Queens-Park-E North 1 100
   -1
   

   In this example, the edge from vertex 2 to vertex 1 is labelled "Bloor", the direction of travel is "West", the length of the edge is 6, and the buildings are numbered from 50 to 100 as we traverse the edge.

   After reading in the map/graph, the program should prompt the user for two addresses. For example, here is some sample input:

   Enter the source address >>> 470 St-George
   Enter the destination address >>> 85 College
   

   The program will find the intersections closest to the source and destination, find the shortest path between those intersections, and output the directions. The closest intersection is determined by the street address.

   North on St-George
   East on Bloor
   South on Queens-Park-W
   West on College
   

   Note that we included the edge from our original address to the source intersection because our source address was not on the first edge of the shortest path. However, our destination address was on the final edge of the shortest path.

   Also note that the shortest path follows two consecutive edges labelled "Queens-Park-W" with direction "South". Because the edges have identical labels and directions, the direction for the second of the two edges was not included in the output.

   After printing the directions, the program should prompt the user for two more addresses and continue until the end of input. If the user enters an illegal address, for example unknown street name or address number outside the range given, the program should print the message "Illegal address." and prompt the user for two more addresses.

   Your program should make use of the graph.cpp and shortest_path.cpp modules you wrote for part 2, without modifying them.

   Place your code in a file called street_guide.cpp, and submit it electronically.