Consider a data communication network that must route data packets (email, MP3 files, or video files, for example). Such a network consists of routers connected by physical cables or links. A router can act as a source, a destination, or a forwarder of data packets. We can model a network as a graph with each router corresponding to a vertex and the link or physical connection between two routers corresponding to a pair of directed edges between the vertices.
A network that follows the OSPF (Open Shortest Path First) protocol routes packets using Dijkstra’s shortest path algorithm. The criteria used to compute the weight corresponding to a link can include the time taken for data transmission, reliability of the link, transmission cost, and available bandwidth. Typically each router has a complete representation of the network graph and associated information available to it.
For the purposes of this project, each link has associated with it the transmission time taken for data to get from the vertex at one end to the vertex at the other end. You will compute the best path using the criterion of minimizing the total time taken for data to reach the destination. The shortest time path minimizes the sum of the transmission times of the links along the path.
The network topology can change dynamically based on the state of the links and the routers. For example, a link may go down when the corresponding cable is cut, and a vertex may go down when the corresponding router crashes. In addition to these transient changes, changes to a network occur when a link is added or removed.
Consider a very simplified example of a network at UNCC, with vertices at Belk Gym, Woodward Hall, College of Education, Duke Hall, Grigg Hall, and College of Health and Human Services. See Figure 1 for an illustration. For this example, the shortest time (or fastest) path from Belk (Gym) to (College of) Education is: Belk–Duke–Education with a total transmission time of 0.9 milliseconds.
Figure 1: An example network graph. Each link shown represents two directed edges. Shown next to each link are the associated transmission times of its two edges in milliseconds.
You have five tasks in this project: building the initial graph, updating the graph to reflect changes, finding the shortest path between any two vertices in the graph based on its current state, printing the graph, and finding reachable sets of vertices. These are described in turn.
Building the Graph
Your program should run from the command-line:
where network.txt is a file that contains the initial state of the graph. (Other names besides network.txt may be used, so you cannot hard-code this.) The format of the file is quite simple. Each link representing two directed edges is listed on a line, and is specified by the names of its two vertices followed by the transmission time. Vertices are simply strings (vertex names with no spaces) and the transmission times are floating point numbers. For the above example, the file will look like:
Belk Grigg 1.2
Belk Health 0.5
Duke Belk 0.6
Belk Woodward 0.25
Woodward Grigg 1.1
Grigg Duke 1.6
Health Woodward 0.7
Health Education 0.45
Woodward Education 1.3
Duke Education 0.3
Woodward Duke 0.67
For each input link, add two directed edges, one in each direction.
Changes to the Graph
Input about changes to the graph, requests for shortest paths, and requests to print the graph will come as input queries to be read from the standard input. Here are queries indicating changes to the graph.
addedge tailvertex headvertex transmit time — Add a single directed edge from tailvertex to headvertex. Here headvertex and tailvertex are the names of the vertices and transmit time is a float specifying the transmission time of the edge. If a vertex does not exist in the graph already, add it to the graph. If the edge is already in the graph, change its transmission time. Important note: This can enable two vertices to be connected by a directed edge in one direction and not the other, or enable the transmission times in the two directions to be different.
deleteedge tailvertex headvertex — Delete the specified directed edge from the graph. Do not remove the vertices. If the edge does not exist, do nothing. Note: This may cause two vertices to be connected by a directed edge in one direction, but not the other.
edgedown tailvertex headvertex — Mark the directed edge as “down” and therefore unavailable for use. The response to an edgedown (or edgeup) query should mark only the specified directed edge as “down” (or “up”). So its companion directed edge (the edge going in the other direction) should not be affected.
edgeup tailvertex headvertex — Mark the directed edge as “up”, and available for use. Its previous transmission time should be used.
vertexdown vertex — Mark the vertex as “down”. None of its edges can be used. Marking a vertex as “down” should not cause any of its incoming or outgoing edges to be marked as “down”. So the graph can have “up” edges going to and leaving from a “down” vertex. However a path through such a “down” vertex cannot be used as a valid path.
vertexup vertex — Mark the vertex as “up” again.
Finding the Shortest Path
The query for finding the shortest path will look like path from_vertex to_vertex
where from_vertex and to_vertex are names of vertices. This should compute the shortest time path from from_vertex to to_vertex using Dijkstra’s algorithm and based on the current state of the graph.
The most difficult task is the implementation of Dijkstra’s algorithm, and especially the priority queue (as a min binary heap).
The output must be the vertices along the shortest path, followed by the total transmission time. For example, with our example graph and no changes to the state of the graph, the query path Belk Education should yield as output
Belk Duke Education 0.9
The simple query print
must print the contents of the graph. Vertices must be printed in alphabetical order and the outward edge for each vertex must be printed in alphabetical order. For the example graph, the output should be
When a vertex is down, append the word DOWN after the vertex. When an edge is down, append the word DOWN after the edge.
Since the states of the vertices and edges may change with time, it is useful to know the set of vertices reachable from each vertex by valid paths. You must develop and implement an algorithm that identifies for each vertex, the set of all its reachable vertices. You should not use the shortest distance algorithm implemented above to obtain the set of reachable vertices. Important: Additionally, you must describe your algorithm and justify its running time, using “O” notation, in the comments for this algorithm in your submitted code.