There is a file 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 arent 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. You will not need to use the actual distance, only the fact that there is an edge connecting two cities.

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:Print vertices, Find districts, Find shortest path, Quit

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

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 isnt 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.

Appendix A cout statements

Print menu

 cout  
Print vertices
 
 cout 
 cout 
 cout 
Find districts Nothing to print.
 
Find shortest path
 
 cout  
One or both cities not found:
 
 cout  
Cities in different districts:
 
 cout  
Districts not set yet:
 
 cout  
Algorithm successful:
 
 cout  
 cout name; cout  
Quit
 
cout  
text file
 
cities,Atlanta,Boston,Boulder,Cheyenne,Chicago,Cleveland,Disneyland,Key West,Miami,New Orleans,New York,Portland,San Francisco,Seattle,Yakima Atlanta,0,-1,-1,-1,-1,-1,-1,-1,663,487,-1,-1,-1,-1,-1 Boston,-1,0,-1,-1,982,640,-1,-1,-1,-1,215,-1,-1,-1,-1 Boulder,-1,-1,0,-1,1130,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 Cheyenne,-1,-1,-1,0,-1,-1,-1,-1,-1,-1,-1,1162,-1,-1,1095 Chicago,-1,982,1130,-1,0,344,-1,-1,-1,-1,-1,-1,-1,-1,-1 Cleveland,-1,640,-1,-1,344,0,-1,-1,-1,-1,-1,-1,-1,-1,-1 Disneyland,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1,989,408,-1,-1 Key West,-1,-1,-1,-1,-1,-1,-1,0,159,-1,-1,-1,-1,-1,-1 Miami,663,-1,-1,-1,-1,-1,-1,159,0,864,-1,-1,-1,-1,-1 New Orleans,487,-1,-1,-1,-1,-1,-1,-1,864,0,-1,-1,-1,-1,-1 New York,-1,215,-1,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1 Portland,-1,-1,-1,1162,-1,-1,989,-1,-1,-1,-1,0,635,173,185 San Francisco,-1,-1,-1,-1,-1,-1,408,-1,-1,-1,-1,635,0,-1,-1 Seattle,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,173,-1,0,142 Yakima,-1,-1,-1,1095,-1,-1,-1,-1,-1,-1,-1,185,-1,142,0 
 
graph.cpp - creates the functions defined in graph.h, you must add to this cpp file for the functionality needed
 
#include "Graph.h"
 
#include 
 
#include 
 
 
 
using namespace std;
 
 
 
template
 
Graph::Graph()
 
{
 
}
 
template
 
Graph::~Graph()
 
{
 
 //dtor
 
}
 
template
 
void Graph::addEdge(T v1, T v2, int weight){
 
 
 
 for(int i = 0; i  
 if(vertices[i].name == v1){
 
 for(int j = 0; j  
 if(vertices[j].name == v2 && i != j){
 
 adjVertex av;
 
 av.v = &vertices[j];
 
 av.weight = weight;
 
 vertices[i].adj.push_back(av);
 
 //add edge in the other direction
 
 //vertices[i].adj.push_back(av);
 
 //another vertex for edge in other direction
 
 //adjVertex av2;
 
 //av2.v = &vertices[i];
 
 //av2.weight = weight;
 
 //vertices[j].adj.push_back(av2);
 
 }
 
 }
 
 }
 
 }
 
}
 
template
 
void Graph::addVertex(T n){
 
 bool found = false;
 
 for(int i = 0; i  
 if(vertices[i].name == n){
 
 found = true;
 
 cout 
 }
 
 }
 
 if(found == false){
 
 vertex v;
 
 v.name = n;
 
 vertices.push_back(v);
 
 }
 
}
 
template
 
void Graph::displayEdges(){
 
 //loop through all vertices and adjacent vertices
 
 for(int i = 0; i  
 cout";
 
 for(int j = 0; j  
 coutname 
 }
 
 cout 
 }
 
}
 
main.cpp - runs the graph.cpp functions, creates the menu, etc. You must also create this file.
 
graph.h - this defines everything
 
#ifndef GRAPH_H #define GRAPH_H #include #include template struct vertex; template struct adjVertex{ vertex *v; int weight; }; template struct vertex{ int ID; T name; int district; bool visited; int distance; std::vector> adj; }; template struct queueVertex{ int distance; std::vector*> path; }; template class Graph { public: int count = 0; // used to give each city a number/ID Graph(); ~Graph(); void addEdge(T v1, T v2, int weight); void addVertex(T name); void displayEdges(); void assignDistricts(); void BFTraversalLabel(T startingCity, int distID); void shortestPath(T startingCity,T endingCity); vertex * findVertex(T name); protected: private: std::vector> vertices; }; #include "Graph.cpp" #endif // GRAPH_H 
  Use a command-line argument to handle the filename. For example, this data Boulder Chicago Boston 982 2000 Boston Boulder 2000 Chicago 982 would generate this graph: Boston Boulder Chicago