On a data set you have already seen that represents road distances you will be asked to answer some initially basic graph

queries culminating in measuring the distance between two specified nodes.

Dataset will be tested: 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.

Order and Size (n, m)

Degree:

- Largest

- Average

Neighbors:

- edge-distance 1

- edge-distance k

Distance:

- Shortest Path

- Shortest Edge Count

The road data will be given to you in two files, country.osm.graph and

country.osm.xyz. With these data you should answer the questions above.

Data Format: The data in the .xyz file comprises x-y coordinates1 where the ith line represents the coordinates of vertex i.

After comment lines at the top of country.osm.graph

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 I 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 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

/****/****/****/****/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

Please tell me how to answer at least a half. How should I code this?