In this programming assignment, you are expected to implement a graph using the following header:

class Graphs_P3

{

private: //Graph data structure here or create another class to implement it

?? public:

void insertVertex(int vertex); //inserts new vertex in graph

void insertEdge(int from, int to, int weight); //inserts new edge in graph

bool isEdge(int from, int to); //returns true if there is an edge between the vertices from and to

int getWeight(int from, int to); //returns the weight of the edge between the vertices from and to

vector getAdjacent(int vertex); //return a vector of integers representing vertices adjacent to vertex

void printDijkstra(int source); //prints result of running Dijkstra's algorithm with source vertex

void printGraph(); //prints graph in a format sorted by ascending vertex and edge list

};

You are expected to write code for each of the functions as well as implement the graph. A sample int main() function that invokes your graph is provided and you can test it on two test cases. Make sure you do not change any code in the main() function.

Composition of main() Method (How we Test your code):

Input:

8 - Line 1 indicates the number of operations you will be performing or the number of lines that follow

1 5 - Each line's first integer indicates operation; 1 here means insertVertex() and this follows input to the operation - 5

1 6 - insertVertex(6)

2 5 6 50 - 2 is insertEdge. Therefore, operation is insertEdge(5,6,50)

3 6 5 - 3 is isEdge. Therefore, operation is isEdge(6,5)

4 5 6 - 4 is getWeight. Therefore, operation is getWeight(5,6)

5 5 - 5 is getAdjacent. Therefore, operation is getAdjacent(5)

6 5 - 6 is printDijkstra. Therefore, operation is printDijkstra(5)

7 - 7 is printGraph. Therefore, operation is printGraph()

Output:

Functions insertVertex and insertEdge have no output.

0 - isEdge (6,5) returns false

50 - getWeight (5,6) returns 50

6 - getAdjacent(5) returns adjacent vertices in sorted order based on name.

V D P - printDijkstra(5) prints the graph in the format as explained below after this section

6 50 5-6 For this graph, there is only one vertex, 6 from 5, with distance 50 and path from source 5.

5 6 - printGraph() prints the graph in the format: V EdgeList in ascending order of vertices and their respective edge lists

6 This graph has 2 vertices 5, 6. So print vertex (1 per line) and in that line print the edges it is connected to in sorted order

Output for Dijkstra's Algorithm explained:

Implement a method to perform Dijkstra's Algorithm to find the shortest path from the source vertex to all other vertices. The output should be a string of the following format

V D P

1 10 0-1

2 8 0-2

3 18 0-1-3

4 25 0-1-3-5-4

5 20 0-1-3-5

The first line is the heading V D P. This stands for vertex, distance, and path. There is a row for each vertex. The row lists the vertex, the distance from the source vertex to that vertex, and path from the source to that vertex.

Note:

The maximum number of vertices can be set to 50. We will create tests with up to 50 vertices. Include a commentary as a separate file in canvas. Discuss your graph implementation, why you chose it, and the computational complexity of the operations. Discuss the computational complexity of Dijkstra's Algorithm. Discuss any additional data structures used to implement Dijkstra's algorithm (e.g. priority queue). Discuss what you learned from this assignment and what you would do differently if you had to do it over.

2. Here is a handy way to set an integer to "infinity":

???????????#include

???????????int a = std::numeric_limits::max();

Sample Input 1:

8 1 5 1 6 2 5 6 50 3 6 5 4 5 6 5 5 6 5 7

Sample Output 1:

0 50 6 V D P 6 50 5-6 5 6 6

Sample Input 2:

10 1 1 1 2 1 3 1 4 2 1 2 3 2 2 3 7 2 2 4 5 2 3 4 15 2 4 1 4 7

Sample Output 2:

1 2 2 3 4 3 4 4 1

Sample Input 3:

10 1 1 1 2 1 3 1 4 2 1 2 3 2 2 3 7 2 2 4 5 2 3 4 15 2 4 1 4 6 1

Sample Output 3:

V D P 2 3 1-2 3 10 1-2-3 4 8 1-2-4

Sample Input 4:

10 1 1 1 2 1 3 1 4 2 1 2 3 2 2 3 7 2 2 4 5 2 3 4 15 2 4 1 4 5 2

Sample Output 4:

3 4 

class Graphs_P3 { private: // Graph data structure here public: void insertVertex(int vertex); //inserts new vertex in graph void insertEdge(int from, int to, int weight); //inserts new edge in graph bool isEdge(int from, int to); //returns true if there is an edge between the vertices from and to int getWeight(int from, int to); //returns the weight of the edge between the vertices from and to vector getAdjacent(int vertex); //return an array of integers representing vertices adjacent to vertex void printDijkstra(int source); //prints result of running Dijkstra algorithm with source vertex void printGraph(); //prints graph in a format sorted by ascending vertex and edge list };

int main() { //DO NOT CHANGE THIS FUNCTION. CHANGE YOUR IMPLEMENTATION CODE TO MAKE IT WORK int noOfLines, operation, vertex, to, fro, weight,source,j; vector arr; int arrSize; Graphs_P3 g; cin>>noOfLines; for(int i=0;i>operation; switch(operation) { case 1: cin>>vertex; g.insertVertex(vertex); break; case 2: cin>>fro; cin>>to; cin>>weight; g.insertEdge(fro,to,weight); break; case 3: cin>>fro; cin>>to; cout<>fro; cin>>to; cout<>vertex; arr=g.getAdjacent(vertex); arrSize = arr.size(); j=0; while(j>source; g.printDijkstra(source); cout<<" "; break; case 7: g.printGraph(); cout<<" "; break; } } }