A Nation Divided … by Zombies! Solution

Admit it, we all love zombies. Maybe it’s because they don’t actually exist, and we don’t actually have to worry about navigating a life among the undead. But, imagine for a second an alternate universe where they do exist and they have attacked – creating mayhem throughout the country, knocking down communications towers and taking control of bridges and highways. One could imagine a resourceful zombie coalition making it impossible to travel between major cities, isolating human survivors in small districts around the country with no safe means of reaching other districts. The US would become a collection of small outposts, where cities within a district could be reached from within the district, and district residents would need to be careful about travel even within their district. Knowing the shortest path between cities to avoid being attacked would be paramount for survival. 

 

What your program needs to do:

 

Build a graph. There is a file on Moodle called zombieCities.txt that contains the

names of 10 cities and the distances between them stored as an adjacency matrix. Cities that still have roads connecting them that aren’t controlled by zombies have a positive distance in the file. Cities that have been cutoff from each other have a -1 as their distance. When the user starts the program, read in the cities and distances from the text file and build a graph where each city is a vertex, and the adjacent cities are stored in an adjacency list for each vertex. For this assignment, you will not need to use the actual distance, only the fact that there is an edge connecting

two cities. For the next assignment, you will need the distances, so it is probably

best just to set that up now.

 

Use a command-line argument to handle the filename.

 

For example, this data:

 

Boston           Boulder         Chicago Boston                             0               2000                 982 Boulder                    2000                     0                    -1 Chicago                       982                    -1                      0

 

would generate this graph:

 

 

The vertices in the graph are Boston, Boulder, and Chicago. The adjacent vertices for

Boston are Boulder and Chicago. The adjacent vertex for Boulder is Boston, and the

adjacent vertex for Chicago is Boston.

 

Display a menu. Once the graph is built, your program should display a menu with

the following options:

1.   Print vertices

2.   Find districts

3.   Find shortest path

4.   Quit

 

Menu Items and their functionality:  

1.   Print vertices. If the user selects this option, the vertices and adjacent vertices should be displayed. The district ID should also be included in the display. (There is more about what the district ID is in the Find Districts menu item.)

 

An example of how the output should be formatted is shown here:

1:Boston-Boulder**Chicago

1:Boulder-Boston

1:Chicago-Boston

 

The 1 shown is the district ID. District IDs should all be initialized to -1. If you

call print vertices before finding districts, your display would look like:

-1:Boston-Boulder**Chicago

-1:Boulder-Boston

-1:Chicago-Boston

 

2.   Find districts. If the user selects this option, you need to do a breadth-first

search of the graph to determine the connected cities in the graph, and assign those cities the same district ID. The connected cities are the vertices that are connected, either directly by an edge, or indirectly through another vertex. For example, in the Boulder, Boston, Chicago graph shown above, these three cities are all connected even though there isn’t an edge connecting Chicago and Boulder. There is a path between these two cities that goes through Boston. 

 

In your graph, add a parameter to each vertex to store a district ID. The ID

should be an integer, 1 to n, where n is the number of districts discovered in

the graph, you will not know this value ahead of time. To get the correct, expected district ID for each vertex, make sure you read in the zombieCities.txt file in order so that your vertices are set up in alphabetical order. 

 

When assigning district IDs, start at the first vertex and find all vertices connected to that vertex. This is district 1. Next, find the first vertex alphabetically that is not assigned to district 1. This vertex is the first member of district 2, and you can repeat the breadth-first search to find all vertices connected to this vertex. Repeat this process until all vertices have been assigned to a district.

 

You do not need to print anything for this menu option. To verify that district

IDs have been assigned, call print vertices again.

 

3.   Find shortest path. If the user selects this option, they should be prompted for the names of two cities. Your code should first determine if they are in the same district. If the cities are in different districts, print “No safe path between cities”. If the cities are in the same district, run a breadth-first

search that returns the number of edges to traverse along the shortest path, and the names of the vertices along the path. For example, to go from Boulder to Chicago in the example graph, you would print:

 

2, Boulder, Boston, Chicago

 

You will need to include a distance parameter in each vertex. There are

multiple approaches to storing the path and you are welcome to use any approach that works for you. Some options include storing the parent for each vertex visited on the search path, or storing the path information in an array or queue and reconstruct the path from that data. There is more information about storing the path information in an array in your book. 

 

How to submit your assignment

To submit your work, zip all files together and submit them to COG as

Assignment12.zip. If you do not get your assignment working on COG, you will have

the option of a grading interview.  

 

Additional information

There is sample code on moodle showing how to use vectors and add vertices and

edges to a graph. There is also code showing how to use the built-in C++ queue class that will make it easier to do the breadth-first search. The files are labeled GraphIntro.zip and Lecture32STLcpp.

 

For more information on Vectors, there is a great tutorial here: 

http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4027/C-Tutorial-A- Beginners-Guide-to-stdvector-Part-1.htm

 

Appendix A – cout statements

1.   Print menu

 

cout << "======Main Menu======" << endl;

cout << "1. Print vertices" << endl;

cout << "2. Find districts" << endl;

cout << "3. Find shortest path" << endl;

cout << "4. Quit" << endl;

 

2.   Print vertices

 

cout<< vertices[i].district

<<":"<<vertices[i].name<<"--";

for each adjacent vertex:

cout<<vertices[i].adj[j].v-name;

if (j != vertices[i].adj.size()-1)

cout<<"***";

 

3.   Find districts

 

Nothing to print.

 

4.   Find shortest path

 

cout << "Enter a starting city:" << endl;

cout << "Enter an ending city:" << endl;

 

One or both cities not found:

cout << "One or more cities doesn't exist" << endl;

 

Cities in different districts:

cout << "No safe path between cities" << endl;

 

Districts not set yet:

cout << "Please identify the districts before checking distances" << endl;

 

Algorithm successful:

cout << edgesTraversed;

for all cities in path

cout << "," << path[j]-name;

cout << endl;

 

  

5.   Quit

cout << "Goodbye!" << endl;