Project - Graph Traversal
1 Overview
This project requires you to model the problem below as a graph and then use a known graph algorithm to solve the problem (you can pick any algorithm you want).
You must traverse a field of arrows (red or blue). You must find a route from the arrow in the top left corner to the bulls-eye in the bottom right corner. You must follow the direction that the arrows point, and you can only stop on the other colored arrow. For example, start on red, then chose a blue arrow (in the direction that the red arrow is pointing), then from the blue arrow chose a red arrow in the direction the blue arrow is pointing. Continue in this fashion until you find the bulls-eye in the bottom right corner. You may find your-self in a loop and continuously visiting the same arrows. You must find the correct path.
2 Report
You must include a report with your project. It will include the team members names along with their contribution to the project, programming language used (C++ or Java), detailed instructions on how to compile and run your program, and you must also answer the following questions.
a) What type of graph did you use for the problem and how did you construct the graph (what do the vertices, edges, etc. correspond to)?
b) Which algorithm did you use? Describe it in pseudocode.
c) What is the time complexity of your algorithm?
You must implement the programming aspect of this project in either C++ or Java. The only rules for your program are that it must take a text file as input, and write the results of the program to a text file as output. The name of the input and output files need to be given to the program as command line parameters. For example: GraphTraversal input.txt output.txt
Input file format
Your program should read its input from a file with the following format. The input begins with two positive characters on a line indicating the number of rows r and columns c of the maze, respectively. The next r lines contain the color and directional information for each arrow in the maze. Each line has c values, where each value represents the color of the arrow by the direction of the arrow (N, E, S, W, NE, SE, SW, or NW). The color codes R and B represent red and blue, respectively, while the direction codes represent north, east, south, west, northeast, southeast, southwest, or northwest, respectively. The bulls-eye is represented by the letter O. You may assume that the bulls-eye will always be in the bottom-right corner of the maze.
| 8 |
8 |
|
|
|
|
|
|
| R-E |
Ft-SE |
B-S |
B-SW |
R-S |
Ft-SW |
Ft-S |
Ft-S |
| B-E |
R-S |
B-SE |
R-E |
B-SE |
B-S |
B-W |
Ft-SW |
| R-N |
B-W |
B-SW |
Ft-SE |
Ft-NE |
B-SW |
B-W |
Ft-W |
| R-SE |
Ft-SE |
B-SW |
Ft-SE |
Ft-S |
B-NW |
R-E |
B-NW |
| B-NE |
R-W |
Ft-S |
B-S |
B-E |
B-NE |
B-NW |
Ft-NW |
| R-S |
B-SE |
R-SE |
Ft-SE |
R-NW |
R-NE |
B-E |
R-W |
| R-NE |
B-W |
B-SE |
R-E |
R-E |
B-E |
B-NW |
Ft-SW |
| B-NE |
R-E |
B-N |
Ft-NE |
B-NE |
B-N |
B-NW |
0 |
Output file format
You must write the output file in the following format. The output will consist of a path from the top left square to the bottom right square (bulls-eye). Write a single line consisting of a sequence of moves, separated by spaces. Each move should be represented by the number of spaces to move and the direction, with no spaces in between. The direction should be represented using N, E, S, W, NE, SE, SW, and NW, as in the input. The sequence of moves must solve the maze from the input. You will be given multiple mazes to test, along with the solutions so you can check your answers.
For example, if your first 3 moves take you 3 spaces east, 3 spaces southwest, and 4 spaces southeast, your output should begin as follows:
3E 3SW 4SE