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;
};
1
For example, you may add a copy constructor, a move constructor, a copy or move assignment operator =, in addition to any methods, such as accessors and mutators, but you may not modify or remove any of the given private data members. The adjacency list for each vertex is supported by the map class that contains the adjacent vertex (a character) and its distance (an integer). It is expected that you will have a Vertex.h and a Vertex.cpp file for your implementation of the Vertex class.
-
You will display a menu with the following options in a loop until the user enters the proper value to exit the menu (and the program):
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
>
All other options will result in an error message followed by the menu choices again.
-
For the single-source shortest path, you will implement Dijkstra’s algorithm for weighted shortest path without negative edges.
-
-
For the topological sort of the graph, you will implement topological sort algorithm in the textbook (and lecture notes) based on the indegree.
-
-
Your code should be well documented in terms of comments. For example, good comments in general consist of a header (with your name, course section, date, and brief description), comments for each variable, and commented blocks of code.
-
Your program will be graded based largely on whether it works correctly on the CSE machines (e.g., cse01, cse02, …, cse06), so you should make sure that your program compiles and runs on a CSE machine.
-
You should contact your instructor if there is any question about what is being asked for.
-
This is an individual programming assignment that must be the sole work of the individual student. Any instance of academic dishonesty will result in a grade of “F” for the course, along with a report filed into the Academic Integrity Database.
S
AMPLE OUTPUT (input shown in bold green):
The results in the following sample output are based on the input file:
A9B2D5C
B6D5E
2
C 5 E
D4C4E
E
This data represents the following weighted, directed graph:
$
more in1.txt
A9B2D5C
B6D5E
C 5 E
D4C4E
E
$ ./a.out
Enter the name of the input file: in1.txt
File in1.txt successfully loaded into graph.
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
-
1
Adjacency List:
-
: ->(B,9)->(C,5)->(D,2)
-
: ->(D,6)->(E,5)
-
: ->(E,5)
-
: ->(C,4)->(E,4)
-
:
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
-
2
Enter Source Vertex (char) for Shortest Path: A Single-Source Shortest Path from A: A->A:0
3
-
->B:9
-
->C:5
-
->D:2
-
->D->E:6
Enter option choice 1 – 5:
(1) Print Adjacency List
(2) Print Single-Source Shortest Path
(3) Print Indegree of Each Vertex
(4) Print Topological Sort of Graph
(5) Exit Program > 2
Enter Source Vertex (char) for Shortest Path: B Single-Source Shortest Path from B:
Warning: Not All Vertices May Be Reached.
-
->B:0
-
->D->C:10
-
->D:6
-
->E:5
Enter option choice 1 – 5:
(1) Print Adjacency List
(2) Print Single-Source Shortest Path
(3) Print Indegree of Each Vertex
(4) Print Topological Sort of Graph
(5) Exit Program > 2
Enter Source Vertex (char) for Shortest Path: C Single-Source Shortest Path from C:
Warning: Not All Vertices May Be Reached.
Warning: Not All Vertices May Be Reached.
Warning: Not All Vertices May Be Reached.
-
->C:0
C->E:5
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
-
2
Enter Source Vertex (char) for Shortest Path: D Single-Source Shortest Path from D: Warning: Not All Vertices May Be Reached.
Warning: Not All Vertices May Be Reached.
-
->C:4 D->D:0 D->E:4
Enter option choice 1 – 5:
(1) Print Adjacency List
(2) Print Single-Source Shortest Path
(3) Print Indegree of Each Vertex
(4) Print Topological Sort of Graph
4
-
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
