Starting from:
$29
Homework 8 Graphs/A Nation Divided.... By ZOMBIES!
# Graphs
## A Nation Divided.... By ZOMBIES!
Imagine for a second an alternate universe where zombies 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 the website called zombieCities.txt that contains the names of 10
cities and the distances between them stored as an **adjacency matrix**. *Be sure to
test with additional example data files!*
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.
*Use a command-line argument to read in the filename.*
For example, this data: (Note: see zombieCities.txt for actual data file format)
```
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.
The driver program Zombieland.cpp will make calls to discover the districts and
print the connected cities.
**Find districts**. 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 how many districts 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.
**Print vertices**. The vertices and adjacent vertices should be displayed. The
district ID should also be included in the display and the first value.
An example of how the output should be formatted is shown here:
```
1:Boston--Boulder (2000 miles)***Chicago (982 miles)
1:Boulder-Boston (2000 miles)
1:Chicago-Boston (982 miles)
```
The 1 shown is the district ID.
Example run using the zombieCities.txt example data file:
```
./a.out zombieCities.txt
... Reading in Atlanta -- Miami -- 663
... Reading in Atlanta -- New Orleans -- 487
... Reading in Boston -- Chicago -- 982
... Reading in Boston -- Cleveland -- 640
... Reading in Boston -- New York -- 215
... Reading in Boulder -- Chicago -- 1130
... Reading in Cheyenne -- Portland -- 1162
... Reading in Cheyenne -- Yakima -- 1095
... Reading in Chicago -- Boston -- 982
... Reading in Chicago -- Boulder -- 1130
... Reading in Chicago -- Cleveland -- 344
... Reading in Cleveland -- Boston -- 640
... Reading in Cleveland -- Chicago -- 344
... Reading in Disneyland -- Portland -- 989
... Reading in Disneyland -- San Francisco -- 408
... Reading in Key West -- Miami -- 159
... Reading in Miami -- Atlanta -- 663
... Reading in Miami -- Key West -- 159
... Reading in Miami -- New Orleans -- 864
... Reading in New Orleans -- Atlanta -- 487
... Reading in New Orleans -- Miami -- 864
... Reading in New York -- Boston -- 215
... Reading in Portland -- Cheyenne -- 1162
... Reading in Portland -- Disneyland -- 989
... Reading in Portland -- San Francisco -- 635
... Reading in Portland -- Seattle -- 173
... Reading in Portland -- Yakima -- 185
... Reading in San Francisco -- Disneyland -- 408
... Reading in San Francisco -- Portland -- 635
... Reading in Seattle -- Portland -- 173
... Reading in Seattle -- Yakima -- 142
... Reading in Yakima -- Cheyenne -- 1095
... Reading in Yakima -- Portland -- 185
... Reading in Yakima -- Seattle -- 142
1:Atlanta--Miami (663 miles)***New Orleans (487 miles)
2:Boston--Chicago (982 miles)***Cleveland (640 miles)***New York (215 miles)
2:Boulder--Chicago (1130 miles)
3:Cheyenne--Portland (1162 miles)***Yakima (1095 miles)
2:Chicago--Boston (982 miles)***Boulder (1130 miles)***Cleveland (344 miles)
2:Cleveland--Boston (640 miles)***Chicago (344 miles)
3:Disneyland--Portland (989 miles)***San Francisco (408 miles)
1:Key West--Miami (159 miles)
1:Miami--Atlanta (663 miles)***Key West (159 miles)***New Orleans (864 miles)
1:New Orleans--Atlanta (487 miles)***Miami (864 miles)
2:New York--Boston (215 miles)
3:Portland--Cheyenne (1162 miles)***Disneyland (989 miles)***San Francisco
(635 miles)***Seattle (173 miles)***Yakima (185 miles)
3:San Francisco--Disneyland (408 miles)***Portland (635 miles)
3:Seattle--Portland (173 miles)***Yakima (142 miles)
3:Yakima--Cheyenne (1095 miles)***Portland (185 miles)***Seattle (142 miles)
```
### Additional information
There is sample code on the website 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 under the
Lectures tab and labeled GraphExample.tar and CppQueueExample.cpp.
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-ABeginners-Guide-to-stdvector-Part-1.htm
## A Nation Divided.... By ZOMBIES!
Imagine for a second an alternate universe where zombies 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 the website called zombieCities.txt that contains the names of 10
cities and the distances between them stored as an **adjacency matrix**. *Be sure to
test with additional example data files!*
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.
*Use a command-line argument to read in the filename.*
For example, this data: (Note: see zombieCities.txt for actual data file format)
```
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.
The driver program Zombieland.cpp will make calls to discover the districts and
print the connected cities.
**Find districts**. 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 how many districts 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.
**Print vertices**. The vertices and adjacent vertices should be displayed. The
district ID should also be included in the display and the first value.
An example of how the output should be formatted is shown here:
```
1:Boston--Boulder (2000 miles)***Chicago (982 miles)
1:Boulder-Boston (2000 miles)
1:Chicago-Boston (982 miles)
```
The 1 shown is the district ID.
Example run using the zombieCities.txt example data file:
```
./a.out zombieCities.txt
... Reading in Atlanta -- Miami -- 663
... Reading in Atlanta -- New Orleans -- 487
... Reading in Boston -- Chicago -- 982
... Reading in Boston -- Cleveland -- 640
... Reading in Boston -- New York -- 215
... Reading in Boulder -- Chicago -- 1130
... Reading in Cheyenne -- Portland -- 1162
... Reading in Cheyenne -- Yakima -- 1095
... Reading in Chicago -- Boston -- 982
... Reading in Chicago -- Boulder -- 1130
... Reading in Chicago -- Cleveland -- 344
... Reading in Cleveland -- Boston -- 640
... Reading in Cleveland -- Chicago -- 344
... Reading in Disneyland -- Portland -- 989
... Reading in Disneyland -- San Francisco -- 408
... Reading in Key West -- Miami -- 159
... Reading in Miami -- Atlanta -- 663
... Reading in Miami -- Key West -- 159
... Reading in Miami -- New Orleans -- 864
... Reading in New Orleans -- Atlanta -- 487
... Reading in New Orleans -- Miami -- 864
... Reading in New York -- Boston -- 215
... Reading in Portland -- Cheyenne -- 1162
... Reading in Portland -- Disneyland -- 989
... Reading in Portland -- San Francisco -- 635
... Reading in Portland -- Seattle -- 173
... Reading in Portland -- Yakima -- 185
... Reading in San Francisco -- Disneyland -- 408
... Reading in San Francisco -- Portland -- 635
... Reading in Seattle -- Portland -- 173
... Reading in Seattle -- Yakima -- 142
... Reading in Yakima -- Cheyenne -- 1095
... Reading in Yakima -- Portland -- 185
... Reading in Yakima -- Seattle -- 142
1:Atlanta--Miami (663 miles)***New Orleans (487 miles)
2:Boston--Chicago (982 miles)***Cleveland (640 miles)***New York (215 miles)
2:Boulder--Chicago (1130 miles)
3:Cheyenne--Portland (1162 miles)***Yakima (1095 miles)
2:Chicago--Boston (982 miles)***Boulder (1130 miles)***Cleveland (344 miles)
2:Cleveland--Boston (640 miles)***Chicago (344 miles)
3:Disneyland--Portland (989 miles)***San Francisco (408 miles)
1:Key West--Miami (159 miles)
1:Miami--Atlanta (663 miles)***Key West (159 miles)***New Orleans (864 miles)
1:New Orleans--Atlanta (487 miles)***Miami (864 miles)
2:New York--Boston (215 miles)
3:Portland--Cheyenne (1162 miles)***Disneyland (989 miles)***San Francisco
(635 miles)***Seattle (173 miles)***Yakima (185 miles)
3:San Francisco--Disneyland (408 miles)***Portland (635 miles)
3:Seattle--Portland (173 miles)***Yakima (142 miles)
3:Yakima--Cheyenne (1095 miles)***Portland (185 miles)***Seattle (142 miles)
```
### Additional information
There is sample code on the website 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 under the
Lectures tab and labeled GraphExample.tar and CppQueueExample.cpp.
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-ABeginners-Guide-to-stdvector-Part-1.htm
1 file (5.4KB)
