//////////////////////////////////////////////////////////// READ THE PROBLEM //
ID: 3919922 • Letter: #
Question
//////////////////////////////////////////////////////////// READ THE PROBLEM /////////////////////////////////////////////////////////////
or don't bother
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<int> 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 <limits>
int a = std::numeric_limits<int>::max();
Sample Input 1:
Sample Output 1:
Sample Input 2:
Sample Output 2:
Sample Input 3:
Sample Output 3:
Sample Input 4:
Sample Output 4:
Code Challenge — Write a program, test using stdin ? stdout
Time Limit: 30 seconds
Memory Limit: 256 MB
...............................................................................................................................................................................
ONLY IMPLEMENT CLASS METHODS!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
DO NOT CHANGE MAIN FUNCTION AT ALL!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
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<int> 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<int> arr;
int arrSize;
Graphs_P3 g;
cin>>noOfLines;
for(int i=0;i<noOfLines;i++)
{
cin>>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<<g.isEdge(fro,to)<<" ";
break;
case 4:
cin>>fro;
cin>>to;
cout<<g.getWeight(fro,to)<<" ";
break;
case 5:
cin>>vertex;
arr=g.getAdjacent(vertex);
arrSize = arr.size();
j=0;
while(j<arrSize)
{
cout<<arr[j]<<" ";
j++;
}
cout<<" ";
break;
case 6:
cin>>source;
g.printDijkstra(source);
cout<<" ";
break;
case 7:
g.printGraph();
cout<<" ";
break;
}
}
}
Explanation / Answer
ONLY IMPLEMENT CLASS METHODS:-
1. void Graphs_P3::insertVertex(int key){
// Check if the vertex already exists in our Vertice collection
for (int i = 0; i < verticesList.size(); i++){
if (verticesList[i]->getKey() == key ){
std::cout << "Vertex with key "" << key << "" already present" << std::endl;
throw std::runtime_error(" You've tried to inesert a vertex with a key that already exists in Graph. ");
// return false;
return;
}
}
// Add it to the list otherwise
Vertex *newVert = new Vertex( key );
verticesList.push_back(newVert);
// return true;
return;
}
2. void Graphs_P3::insertEdge( int fromVertexKey, int toVertexKey, int weight){
int v1_loc = -1;
int v2_loc = -1;
for (int i = 0; i < verticesList.size(); i++){
if (verticesList[i]->getKey() == fromVertexKey ){
v1_loc = i;
}
if (verticesList[i]->getKey() == toVertexKey ){
v2_loc = i;
}
}
if ( ( (v1_loc == -1) || (v2_loc == -1) ) ){
std::cout << "At least one of the two vertices entered does not exist in Graph." << std::endl;
// return false;
return;
}
verticesList[v1_loc]->addDepartingEdge( verticesList[v2_loc], weight );
return;
}
3. bool Graphs_P3::isEdge( int fromVertexKey, int toVertexKey){
for (int i = 0; i < verticesList.size(); i++){
if (verticesList[i]->getKey() == fromVertexKey ){
return verticesList[i]->isAdjacentTo( toVertexKey );
}
}
return false;
}
4. int Graphs_P3::getWeight( int fromVertexKey, int toVertexKey ){
if ( !( isEdge( fromVertexKey, toVertexKey ) ) ){
throw std::runtime_error("You tried to get the weight of an edge that doesn't exist. Bye. : ) ");
}
return getVertex( fromVertexKey )->weightTo( toVertexKey );
}
5. Vertex* Graphs_P3::getVertex( int key){
for (int i = 0; i < verticesList.size(); i++){
if (verticesList[i]->getKey() == key ){
return verticesList[i];
}
}
std::cout << "Vertex with key "" << key << "" doesn't exist" << std::endl;
return NULL;
}
6. std::vector<int> Graphs_P3::getAdjacent( int fromVertexKey){
std::vector<int> adjacentVerticesKey;
// Look for the Vertex Key in verticesList
for (int i = 0; i < this->verticesList.size(); i++){
if (verticesList[i]->getKey() == fromVertexKey ){
// if we find it create a vector object and fill it with the keys
std::map< int, Vertex::edgeObj> adjList = verticesList[i]->getAdjacencyList();
for ( auto &objPair : adjList ){
adjacentVerticesKey.push_back(objPair.first);
}
std::sort( adjacentVerticesKey.begin(), adjacentVerticesKey.end());
return adjacentVerticesKey;
}
}
throw std::runtime_error(" You tried to access a non-existing object. You can do better!!! Bye. : ) ");
}
7. void Graphs_P3::printDijkstra( int source ){
// Do some initilizing:
// Create a vector for the vertices whose minimum path to source has been finalized
std::vector<int> sptSet;
// Create a map to easily record the distances, < verticeKey , distance >
std::map< int , distObj* > distances;
// Priority queue that manages how we consider which node to visit next
std::priority_queue < int, std::vector<int>, std::greater<int> > nexts;
// Initialize the distances: 0 for source, infinity for all others
for ( auto &vertexObj : verticesList){
if (vertexObj->getKey() == source){
distObj* dObj = new distObj;
distances[ vertexObj->getKey() ] = dObj;
distances[ vertexObj->getKey() ]->from = NULL;
distances[ vertexObj->getKey() ]->distance = 0;
}
else{
distObj* dObj = new distObj;
distances[ vertexObj->getKey() ] = dObj;
distances[ vertexObj->getKey() ]->from = NULL;
distances[ vertexObj->getKey() ]->distance = std::numeric_limits<int>::max();
}
}
// Push source to the priority queue to get the ball rolling
nexts.push( source );
// This condition is meant to mean: "while sptSet doesn't contain all the vertices in verticesList"
// There is a difference between that and the condition below, and so I want to point that out.
//while ( sptSet.size() != this->verticesList.size() ){
// another condition that can evaluate similarly to the actual condition we want, but is notably different
while ( !nexts.empty() ){
int currentKey = nexts.top();
nexts.pop();
// Vertex* currentVertexObj = this->getVertex( currentKey );
// Get all keys adjacent to currentKey
std::vector<int> adjacentToCurrent = this->getAdjacent( currentKey );
// debugging
//for ( int i = 0; i < adjacentToCurrent.size(); i++){
// std::cout << adjacentToCurrent[i];
//}
// for all the 'adjacentToCurrent' keys we just got, update their min distance by comparing it's current distance to ( 'the distance of the current key from source' + 'the weight between the edge connecting currentKey and the adjacentKey being considered')
for ( int i = 0; i < adjacentToCurrent.size(); i++){
int adjKey = adjacentToCurrent[i];
nexts.push( adjKey );
int newDist = distances[ currentKey ]->distance + getWeight( currentKey, adjKey );
if ( newDist < distances[ adjKey ]->distance ){
distances[ adjKey ]->from = currentKey;
distances[ adjKey ]->distance = newDist;
}
}
// we've confirmed the min distance from source to currentKey, now we can add it to sptSet ( the set of verticeKeys with finalized min-distances)
sptSet.push_back( currentKey );
}
//Once we've completed the minimum distance mapping, it's time to print
// Print Algoirthm
// For each key in sptSet starting from the second key:
/*
1. Call a function that takes two arguments, a key and a stack, ( and distances as well I guess).
x. This function will recursively build a stack that can be printed to give the correct path to a key passed in.
Base Case:
(*distances[ key ].from == NULL)
( key == source )
if this is true that means we reached source which means we should print our stack.
Recursive Case:
if the base case isn't met:
push key to the stack, and make a recursive call where the 'key' argument is *distances[ key ].from
2. Print:
Take the top of the stack and print it, with a "-" behind the top, if the stack is empty after you pop the top, print but without the "-".
*/
std::cout << "V D P" << std::endl;
for ( int i = 1; i < sptSet.size(); i++ ){
std::cout << sptSet[i] << " " << distances[ sptSet[i] ]->distance << " ";
std::stack<int> pathStack;
getPath( sptSet[i], &pathStack, distances);
}
// std::cout << "I should've returned by now.";
return;
}
8. void Graphs_P3::printGraph(){
std::cout << "Printing Graph..." << std::endl;
for ( auto &vertex : this->verticesList){
std::cout << vertex->getKey() << " ";
for ( auto &adjacentVertex : this->getAdjacent( vertex->getKey() ) ){
std::cout << adjacentVertex << " ";
}
}
return;
// std::cout << " Keys:" << std::endl;
//for (int i = 0; i < this->verticesList.size(); i++){
// std::cout << " " << this->verticesList[i]->getKey() << std::endl;
// this->verticesList[i]->printAdjacencyList();
//}
}
Please let em know in case of any clarifications required. Thanks!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.