Design
Report
I create the RoadMap class for the road map system and the Vertex class, Edge class, Road class to model the vertex, edge, and road respectively.
The vertex type and event type are represented as enum. All the API function is defined in class RoadMap.
The RoadMap class contains fields: vertexes, edges and roads. The vertexes is a map from string to Vertex which can allow efficient retrieving vertex by label.
In the function trip(fromVertex, toVertex) in class RoadMap, I choose Dijkstra algorithm to compute the shortest path. Because the edge weight in the graph is non-negative and Dijkstra is a efficient algorithm for the single source shortest path computing. The weight used in the trip function is the edge length, we can also use length/speedLimit as the weight.
The Vertex class contains fields: label, type. For the purpose of computing shortest path in the trip function, it also contains fields neighbors, distance and pre. The neighbors a vector of all edges from this vertex to other vertex. Distance is the distance from source vertex and pre is the previous vertex in the path.
The Edge class contains contains fields: from, to, speedLimit, length, event.
Test
To test the system. I also write the test codes in test.cpp. It uses the retrieve API to read data from input file. And compute the shortest path using trip API and print the path to the standard output. In the last, it outputs the data to storedmap.txt using store API. Since retrieve API will invoke vertex API, addVertex function, addEdge function and edgeEvent function, so all functions are covered in the test.
Case2.txt different from the case1.txt is that some edge have road closure event, so
this will test whether the system considers road closure event in computing shortest path.
Case3.txt different from the case1.txt is that there is no path between some two vertexes. This will test empty path.
Since the algorithm used is deterministic, so there is no deviation for the same input file.