CSC 270 Assignment 2 Due Wednesday, October 16 at 5:00pm in the box outside SF4306 ------ The Maze Problem ---------------- Your task is to find all the shortest paths through a graph. The graph represents a maze in which there are only horizontal and vertical edges that join adjacent points on an integer grid. You will find the shortest paths from the upper-left corner of the maze to the lower-right corner. Note that there can be more than one path which has the minimum length. You will write two programs: one will find the shortest paths using an ADJACENCY MATRIX graph representation; the other will find the shortest path using an ADJACENCY LIST graph representation. Both representations are described in Section 9.3 of the Readings. You will compare the performance of these representations on various graphs. For the adjacency matrix representation, you will use Floyd's algorithm (described in Section 9.9) to compute all-pairs shortest distances. This doesn't give shortest paths, though. To get the shortest paths between particular `source' and `destination' nodes, you must start at the destination node and follow edges backward through the graph until you reach the source node. In following an edge backward from a node x, you should always follow the edge that leads from x to another node y that has the shortest distance to the source (of all the nodes adjacent to x). Dijkstra's algorithm (described in Section 9.8) finds all shortest source-to-node distances usings an adjacency list representation. As with Floyd's algorithm, a further step is necessary to reconstruct the shortest paths. Your Assignment --------------- 1. Copy the C code into your directory: % cd % cp -r ~jstewart/csc270/maze . 2. Go into that directory and compile the files: % cd maze % make 3. Run the working maze program that I've provided: % draw maze1.dat % draw maze2.dat % working-mazem maze1.dat % working-mazem maze1.dat | draw maze1.dat % working-mazem maze1.dat 2 % working-mazem maze1.dat 2 | draw maze1.dat % working-mazem maze1.dat 99 | draw maze1.dat Note that the LINES (- and |) in the drawing indicate the maze, not the spaces between the lines as is the case with most maze drawings. Watch the newgroup in case bugs are found in working-mazem and a new (debugged) program is made available. 4. Run the two non-working maze programs that you just compiled. You should just get a short message for each. % mazem maze1.dat % mazel maze1.dat mazem is your shortest-paths program using an adjacency matrix (m). mazel is your shortest-paths program using an adjacency list (l). 5. Look at ALL the *.c and *.h files. Read ALL the comments at the tops of the files and ALL the comments at the tops of the functions. Understand what the global variables are for. 6. Add C code to the file shortest-matrix.c to output ONE shortest path using the adjacency matrix representation. The comments in that file explain what parameters you're given. Don't change the parameters of the output_shortest_paths function. You made add functions and global variables as necessary. You may create other *.c and *.h files if you wish, in which case you should also modify the Makefile. 7. Add C code to the file shortest-list.c to output ONE shortest path using the adjacency list representation. Don't change the parameters of the output_shortest_paths function. That function gets an adjacency matrix as one of its parameters and YOU must convert the adjacency matrix into an adjacency list representation BEFORE computing the shortest path. 8. Add more C code to shortest-matrix.c to output up to `num_paths' shortest paths, where num_paths is a parameter to the output_shortest_paths function. (If num_paths is 1, you should only output one shortest path.) 9. DO NOT modify shortest-list.c to output more than one shortest path for the adjacency list representation. It is sufficient to do it (in Step 8) for the adjacency matrix representation. Testing ------- You don't have to worry about bad user input, since that's handled in maze.c and read.c, which have been provided to you. Your programs should generate the same output as the working-mazem program that is provided. The only permissable difference is that your program may output the multiple shortest paths in a different order than working-mazem (but each individual path must have the nodes in the SAME order as the corresponding path generated by working-mazem). Run the `draw' program on your paths to see if they make sense. Warning: The input file can have weights associated with each edge. The read.c code will correctly store these weights in the adjacency matrix that it creates. Your own code had better deal with these weights correctly when finding the shortest paths. See read.c for the format of the input file. Run tests of your programs on different graphs using the different methods of storing the graph. Some graphs will be provided for you, but you should ALSO create your own. In each test, have the program output ONLY ONE shortest path. Use the shell's `time' feature to get running times of the different experiments. See the manual page on `time'. Usage is: % time working-mazem maze1.dat and the output give the number of `user seconds' (u) and `system seconds' (s). Report ------ 1. Describe, in clear English without pseudo-code, the algorithm you developed to determine all-shortest-paths once Floyd's algorithm had been run to compute all-pairs shortest distances. Your description should be sufficiently clear and detailed that the tutor could easily implement your algorithm. Poor or obscure English will be penalized. 2. Compare the two graph representations and their associated algorithms. You should consider the asymptotic `big-oh' analysis, the memory space requirements, and your experimental running times. Do your experiments really indicate that adjacency matrices are better for small, dense graphs and adjacency list are better for large sparse graphs? Explain. What to hand in --------------- Hand in on paper: 1. Your reports described above. 2. Listings of ALL the files that you modified. If you modified maze.c or read.c, highlight the sections that you modified. Do not highlight the sections of the shortest-*.c files that you modify. 3. Testing output. Each test should appear on a separate piece of paper and should include (a) the test graph as drawn by `draw', (b) the shortest path or paths that your algorithm found, as drawn by `draw', and (c) a brief written explanation of what your test tests. 4. Attach the sheet below to the front of your assignment. Hand in with the `submit' command: 5. All the files necessary to compile and run your two programs: mazem and mazel. This includes the Makefile, since the tutor will execute % make with the files that you submit. If the compilation fails, you lose marks. Do not include draw.c or draw.h. Do not submit multiple copies of your shortest-matrix.c which do single- and multiple-paths. Submit only the copy that does multiple paths. If you couldn't get multiple paths working, submit the single-path code. 6. All YOUR test graphs with names graph1, graph2, and so on. Each file should have a comment at the top (on lines starting with #) that explains what the graph tests. The tutor may execute % make % mazem graph1 % mazel graph1 so make sure that this works! To submit, use the command % submit -N a2 csc270h f1 f2 f3 ... where f1, f2, f3, ... are the files that you are submitting CSC 270, Assignment 2 Cover Page: due Wednesday, October 16 at 5:00pm Surname _______________________________ Given Names _______________________ Student Number ________________________ TA's name _____________________________ Tutorial location _________________ I declare that this assignment is my own work and is done in accordance with the University of Toronto Code of Behavior on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism described in the course policies. I discussed this assignment with the following people: ______________________________________________________ ______________________________________________________ ______________________________________________________ Signature ____________________________________________ GRADING Programs Adjacency matrix one path /5 Adjacency list one path /10 Adjacency matrix multiple paths /10 Style and comments /5 Testing /10 Report and Discussion Content /15 Style and readability /5 -------------- Total /65