Description
PROGRAM DESCRIPTION
In this C++ program, you will use concepts from Chapter 9 to read data from a file so that you can construct a weighted directed graph data structure in a “modified” adjacency list format. Your graph will support the following operations: (1) printing the adjacency list, (2) printing the single-source shortest path to all vertexes using Dijkstra’s algorithm, (3) printing the indegree of each vertex, and (4) printing a topological sort of the graph.
REQUIREMENTS
-
You will prompt for and read in a data file that is used to build the weighted directed graph data structure.
-
The input format of the file is as files: one line per vertex, where the first element (a character) is the vertex for that entry. The optional remaining elements are organized by any number of distance (an integer) and vertex (a character) pairs, such B 6 D 5 E, which shows the data for the vertex B, connected to vertex D through a distance of 9 and E through a distance of 5.
o All vertexes in the weighted directed graph, whether or not they have outgoing paths, will be given in the data file, so some lines will consist of only the vertex for that entry.
o All edges will be positive.
o Note that the graph may be unconnected or may have vertexes that cannot be reached (you may see this in your single-source shortest path or topological sort algorithms).
o Your code must read graphs of arbitrary size from a file – you may not assume a maximum number of vertexes nor the values/order of the vertexes.
-
You are initially given the base Vertex class that you may add to as follows:
#include <map>
using namespace std;
class Vertex
{
public:
Vertex();
~Vertex();
private:
char name;
map<char, int> adj;
bool known;
int dist;
char path;
int indegree;
};
-
Exit Program
> 2
Enter Source Vertex (char) for Shortest Path: E Single-Source Shortest Path from E:
Warning: Not All Vertices May Be Reached.
Warning: Not All Vertices May Be Reached.
Warning: Not All Vertices May Be Reached.
Warning: Not All Vertices May Be Reached.
E->E:0
Enter option choice 1 – 5:
-
Print Adjacency List
-
Print Single-Source Shortest Path
-
Print Indegree of Each Vertex
-
Print Topological Sort of Graph
-
Exit Program
> 3
Indegree of Each Vertex: A : 0
B : 1
C : 2
D : 2
E : 3
Enter option choice 1 – 5:
-
Print Adjacency List
-
Print Single-Source Shortest Path
-
Print Indegree of Each Vertex
-
Print Topological Sort of Graph
-
Exit Program
> 4
Topological Sort of Graph: A->B->D->C->E Enter option choice 1 – 5:
-
Print Adjacency List
-
Print Single-Source Shortest Path
-
Print Indegree of Each Vertex
-
Print Topological Sort of Graph
-
Exit Program
> 5
Terminating Program…
SUBMISSION:
-
You will electronically submit your source code file(s) and a README file where you explain all the information required for the grader to grade your program (i.e., how to compile and run it, an example, how you did it, etc.) to the Project 3 dropbox in Canvas by the due date.
5
