Description
Objective: The objective of this project is to demonstrate understanding of, and competence using, graph algorithms as discussed in lectures. On a data set you have already seen
that represents road distances you will you will be asked to answer some initially basic graph
queries culminating in measuring the distance between two specified nodes.
I will run your program twice: firstly on a small dataset and then on a very large dataset
that will test the efficiency of your choice of data structures and algorithms. The assignment
counts for 90% of your semester grade so it will be marked out of 90. For reference the
marking scheme is given below.
Category Query Marks
File submitted 5
Clean compilation 15
Order and Size (n, m) 1 10
Degree:
– Largest 2 5
– Average 3 5
Neighbors:
– edge-distance 1 4 5
– edge-distance k 5 15
Distance:
– Shortest Path 6 15
– Shortest Edge Count 7 15
Total 90
Table 1: Marking scheme for assignment.
Your job: The road data will be given to you in two files, country.osm.graph and
country.osm.xyz. These will be exactly as the format of those referred to in Lab06’s
write-up. With these data you should answer the questions above.
Data Format: The data in the .xyz file comprises x-y coordinates1 where the i
th line
represents the coordinates of vertex i. After comment lines at the top of country.osm.graph
1Actually, z values, too, but you can ignore it.
1
the first line of useful data specifies the number of nodes and edges in the road network.
The remainder of that file is made up of edge lists: one for each vertex, in the order 1 to n.
Note that some vertices might have no neighbors.
The data was pulled from OpenStreetMap – hence the .osm in the file names – and, they
appear to be all undirected. That is, both of the edges (u, v) and (v, u) are listed, once on
u’s adjacency list and again, later, on v’s.
You should represent your graph in the formatz representation. That is, instead of
thinking of representing the graph as n n × n-matrix where almost all of the entries are
unused, use formatz. Each vertex can store its neighbors as a linked list and since every
vertex will have some neighbors you can do this with a vector. So the graph is represented
as a vector of linked lists `a la formatz.
You should then open for reading the files country.osm.graph and country.osm.xyz
where country will have been read from standard input (the keyboard). Be prepared for
this string to be a file path such as something like /home/cs4115/labs/lab06/italy, to
which you would append .osm.graph and .osm.xyz.
Graph Queries: Having read the graph and represented it internally you are now ready
to answer the above questions. Some queries require input, either a vertex (for the two
“Neighbors” and “Distance” queries) and an additional value k for collecting vertices edgedistance k away. Read these as ints from stdin as you need them. So the input to the
program could be
/home/cs4115/labs/lab06/italy
34 # vertex 34
27 4 # nbrs of vertex 27, 4 hops away
29 11 # SP(29,11)
38 6 # SP(38,6) but by edges, not xy dist
Some points regarding the expected output. You should
answer them in the exact order you see above with no directions from the user
no extraneous output text2
, just the facts
for outputs requiring floating point values (average degree and shortest path are the
only two) please round them to 6 decimal places
for outputs requiring lists (neighbors, etc.) please order the output smallest to largest
– sorry, handin again.
Useful Resources: Very soon I will make available my solutions to the outstanding labs
as you could draw on these. I will also post sample input / output for comparison.
Good luck.
2
I’m hoping to automate the grading of these using something akin to handin.
2