C++ dfs question reference? Copy your Graph:shortestWeightedPath method into the
ID: 3708652 • Letter: C
Question
C++ dfs question
reference?
Copy your Graph:shortestWeightedPath method into the box below, with the provided prototype. You may use any helper functions as needed, but they must be copied into the answer box. **Initialize weightedDistance member of the vertices to the maximum value for an integer before performing the algorithm** **The last test case in this question is checking the final weightedDistance's on each vertex after your function runs** You may assume that ALL other class methods are defined, correct, and available for you to call. Your answer should look like: void Graph::shortestheightedPath(std:: string startingCity, std::string endingCity) /I Your code here For example: Test Result Attempt to find a path without identifying districts g.shortestweightedPath("Boulder, "Boston") Please identify the districts before checking distances Answer: (penalty regime: 0 %) 1 void Graph: :shortestheightedPath(string startingCity, string endingCity) 3 4 uyour code here!Explanation / Answer
//main.cpp
#include <string>
#include "Graph.hpp"
#include "Graph.cpp"
using namespace std;
int main(int argc, char * argv[]){
//create an instance of the graph
Graph initGraph;
//stores cities for putting in edges
vector<string> listOfCities;
//the file we're opening is the first argument passed through
ifstream in_stream(argv[2]);
//check to see if opening worked.
if(in_stream.is_open()){
string currentLine = "";
//the first line is used to add vertices, additional lines will be used to add edges
int lineIndex = 0;
//get every line from the file
while(getline(in_stream, currentLine)){
//In each line, create a stringstream
stringstream splitLine(currentLine);
string currentWord = "";
//used so we can ignore certain words from the table
int wordIndex = 0;
//Now, go through every word in the stringstream, delimiting by comma
while(getline(splitLine, currentWord, ',')){
//The first line should just add vertices.
if(lineIndex == 0){
//skip 'dest/source'
if(wordIndex == 0){
wordIndex ++;
}
//add vertices to the graph
//add cities to our list for putting in edges
else{
initGraph.addVertex(currentWord);
listOfCities.push_back(currentWord);
}
}
//If the line index is greater than 0, we want to add edges
else{
//Skip the first word; we just want to get weights
if(wordIndex == 0){
wordIndex++;
}
//Now, add every edge
else{
//turn the weight to an int
int weight = stoi(currentWord);
if(weight > -1){
initGraph.addEdge(listOfCities[lineIndex-1], listOfCities[wordIndex - 1], weight);
}
//Increment the word index when we're done checking a word/weight
wordIndex++;
}
}
}
//increment line index when we're done reading one line
lineIndex++;
}
}
else{
cout<<"There was an error opening the file!"<<endl;
}
//initGraph.displayEdges();
//controls re-printing or exiting the menu
bool continueMenu = true;
while(continueMenu){
//Display a menu
cout << "======Main Menu======" << endl;
cout << "1. Print vertices" << endl;
cout << "2. Find districts" << endl;
cout << "3. Find shortest path" << endl;
cout << "4. Find shortest weighted path" << endl;
cout << "5. Quit" << endl;
//Get what the user wants to do
char userChoice;
cin>>userChoice;
//Print a list of the vertices and their adjacent vertices
if(userChoice == '1'){
initGraph.displayEdges();
}
//uses a depth first search to find districts
//prints nothing to console
else if(userChoice == '2'){
initGraph.assignDistricts();
}
//Uses breadth first search to find shortest unweighted path
else if(userChoice =='3'){
//clear the stream
cin.ignore();
string startCity, endCity;
//Prompt user for cities
cout<<"Enter a starting city:"<<endl;
getline(cin, startCity);
cout<<"Enter an ending city:"<<endl;
getline(cin, endCity);
//Call a function to use a breadth first search to find shortest path
initGraph.shortestPath(startCity, endCity);
}
//Uses dijikstra's to find shortest WEIGHTED path
else if(userChoice == '4'){
//clear the stream
cin.ignore();
string startCityDijikstra, endCityDijikstra;
//Prompt user for cities
cout<<"Enter a starting city:"<<endl;
getline(cin, startCityDijikstra);
cout<<"Enter an ending city:"<<endl;
getline(cin, endCityDijikstra);
//Call a function to use a breadth first search to find shortest path
initGraph.shortestWeightedPath(startCityDijikstra, endCityDijikstra);
}
//Exit the menu
else if(userChoice == '5'){
cout<<"Goodbye!"<<endl;
continueMenu = false;
}
else{
cout<<"Not a vaild choice!"<<endl;
}
}
return 0;
}
-----------------------------------------------------------------------------------------
//Graph.cpp
#include "Graph.hpp"
using namespace std;
//The constructor
Graph::Graph(){};
//THe destructor
Graph::~Graph(){};
//Adds a vertex with name 'name' to the vertices vector of the graph
void Graph::addVertex(std::string name){
//Check to see if the vertex already exists in the list
bool found = false;
for(int i = 0; i < vertices.size(); i++){
if(vertices[i].name == name){
found = true;
cout<<vertices[i].name<<" already in the graph."<<endl;
}
}
//If not found, create a new vertex and push it onto the vertices vector
if(!found){
vertex newVertex;
newVertex.name = name;
//Initialize districtID to -1, visited to false, and the ID is equal to the size of the vector
newVertex.districtID = -1;
newVertex.ID = vertices.size();
newVertex.visited = false;
vertices.push_back(newVertex);
}
}
//Adds an edge between two vectors with a given weight
void Graph::addEdge(std::string v1, std::string v2, int weight){
//Check to make sure both vertices exist and aren't the same.
for(int i = 0; i < vertices.size(); i++){
if(vertices[i].name == v1){
for(int j = 0; j < vertices.size(); j++){
if(vertices[j].name == v2 && i != j){
//Create a pointer and put it in the list of adjacent vertices
adjVertex adjacent;
adjacent.v = &vertices[j];
adjacent.weight = weight;
vertices[i].adj.push_back(adjacent);
}
}
}
}
}
//A function to display every vertex and the vertices it is adjacent to
void Graph::displayEdges(){
//Go through every vertex
for(int i = 0; i < vertices.size(); i++){
cout<<vertices[i].districtID<<":";
cout<<vertices[i].name<<"-->";
//Go through every adjacent vertex
for(int j = 0; j < vertices[i].adj.size(); j++){
cout<<vertices[i].adj[j].v -> name;
if(j != vertices[i].adj.size() - 1){
cout<<"***";
}
}
cout<<endl;
}
}
//Goes through connected components and assigns district IDs based on the component a vector belongs to
void Graph::assignDistricts(){
//an index for the districtID; only increments when a new, un-visited vector is reached
int districtIndex = 1;
for(int i = 0; i < vertices.size(); i++){
//If a vector hasn't been visited, go through its adjacency list and assign ID's
if(vertices[i].visited != true){
DFSLabel(vertices[i].name, districtIndex);
districtIndex++;
}
}
}
void Graph::DFSLabel(std::string starterCity, int distID){
vertex * vStart = findVertex(starterCity);
//mark the vertex as visited and set its districtID
vStart ->visited = true;
vStart ->districtID = distID;
//Go through the entire adjacency list
//For vertices that haven't been visited, set the district ID and make a recursive call
for(int i = 0; i < vStart -> adj.size(); i++){
if(vStart -> adj[i].v ->visited != true){
vStart ->adj[i].v ->districtID = distID;
DFSLabel(vStart ->adj[i].v ->name, distID);
}
}
}
//Search through the list of vertices to find the vertex of a given name
vertex * Graph::findVertex(std::string name){
//Iterate through every vertex and check their names
for(int i = 0; i < vertices.size(); i++){
if(vertices[i].name == name){
return &vertices[i];
}
}
//If not found, returns NULL
return NULL;
}
void Graph::shortestPath(std::string startingCity, std::string endingCity){
//Check to make sure both cities exist.
vertex * vStart = findVertex(startingCity);
vertex * vEnd = findVertex(endingCity);
if(vStart == NULL || vEnd == NULL){
cout<<"One or more cities doesn't exist"<<endl;
return;
}
//Check to make sure districts have been set
if(vStart ->districtID == -1 || vEnd ->districtID == -1){
cout<<"Please identify the districts before checking distances"<<endl;
return;
}
//Check to see if cities are in the safe district
if(vStart ->districtID != vEnd ->districtID){
cout<<"No safe path between cities"<<endl;
return;
}
//Now, perform a breadth first search to find shortest unweighted distance
for(int i = 0; i < vertices.size(); i++){
vertices[i].visited = false;
vertices[i].unweightedDistance = 2147483647;
vertices[i].weightedDistance = 2147483647;
}
vStart ->unweightedDistance = 0;
vStart ->parent = NULL;
//create a queue to enqueue and dequeue vertices
queue<vertex*> vQueue;
vQueue.push(vStart);
//Keep searching until the end city is found
while(vQueue.size() != 0){
//Find the front element
vertex * frontOfQueue = vQueue.front();
vQueue.pop();
//Search through the adjacency list of the current vertex
for(int i = 0; i < frontOfQueue ->adj.size(); i++){
if(frontOfQueue ->adj[i].v -> visited != true){
//Increment the distance by 1
frontOfQueue ->adj[i].v ->unweightedDistance = frontOfQueue ->unweightedDistance + 1;
//Set the parent for finding the actual path
frontOfQueue ->adj[i].v ->parent = frontOfQueue;
//Set visited to true so we don't come back
frontOfQueue ->adj[i].v ->visited = true;
//Push this vertex on to the queue
vQueue.push(frontOfQueue ->adj[i].v);
}
}
}
//Finally, use the parent pointers to print the shortest path
vertex * shortestCityParentTransverse = findVertex(endingCity);
cout<<shortestCityParentTransverse ->unweightedDistance<<", ";
//iterate through the parents, print out their names
for(int i = shortestCityParentTransverse ->unweightedDistance; i >= 0; i--){
cout<<shortestCityParentTransverse ->name;
if(i == 0){
//Ensure the final city has a distance of 0
shortestCityParentTransverse -> unweightedDistance = 0;
cout<<endl;
}
else{
cout<<", ";
}
shortestCityParentTransverse = shortestCityParentTransverse ->parent;
}
}
void Graph::shortestWeightedPath(std::string startingCity, std::string endingCity){
//Check to make sure both cities exist.
vertex * vStart = findVertex(startingCity);
vertex * vEnd = findVertex(endingCity);
if(vStart == NULL || vEnd == NULL){
cout<<"One or more cities doesn't exist"<<endl;
return;
}
//Check to make sure districts have been set
if(vStart ->districtID == -1 || vEnd ->districtID == -1){
cout<<"Please identify the districts before checking distances"<<endl;
return;
}
//Check to see if cities are in the safe district
if(vStart ->districtID != vEnd ->districtID){
cout<<"No safe path between cities"<<endl;
return;
}
//Now, use Dijikstra's algorithm to find the shortest WEIGHTED path
for(int i = 0; i < vertices.size(); i++){
vertices[i].visited = false;
vertices[i].unweightedDistance = 2147483647;
vertices[i].weightedDistance = 2147483647;
vertices[i].parent = NULL;
}
//Will store all solved vertices
vector<vertex*>solvedVertexList;
//Add the starting vertex as solved, mark as visited, set distance as 0
solvedVertexList.push_back(vStart);
vStart->visited = true;
vStart->weightedDistance = 0;
//Keep going until we solve the ending city
while(vEnd ->visited != true){
//minVertex will store the vertex with minimum distance
vertex * minVertex = NULL;
//stores the parent of the minimum vertex
vertex * parent = NULL;
//initialize min distance to max int value so that it will be replaced no matter what
int minDistance = 2147483647;
//Go through every vertex in the solved list
for(int i = 0; i < solvedVertexList.size(); i++){
//Go through the adjacency list of each vertex
for(int j = 0; j < solvedVertexList[i] ->adj.size(); j++){
//Only check adjacent vertices that haven't been solved
if(solvedVertexList[i]->adj[j].v ->visited != true){
//Find the distance back to that start
int distance = solvedVertexList[i]->weightedDistance + solvedVertexList[i]->adj[j].weight;
//if the distance of the adjacent vector is less than the min distance:
//set minDistance to new value, set the parent, and set the minVertex
if(distance < minDistance){
minDistance = distance;
minVertex = solvedVertexList[i]->adj[j].v;
parent = solvedVertexList[i];
}
}
}
}
//Finally, the vertex with the shortest distance is marked as solved and added to the list
minVertex ->weightedDistance = minDistance;
minVertex ->visited = true;
minVertex -> parent = parent;
solvedVertexList.push_back(minVertex);
}
//Print out the distance and the path
cout<<vEnd -> weightedDistance;
while(vEnd != NULL){
cout<<", "<<vEnd->name;
vEnd = vEnd -> parent;
}
cout<<endl;
}
------------------------------------------------------------------------------------------------------------------------------
//Graph.h
#ifndef SHORTESTWEIGHTEDPATH_GRAPH_H
#define SHORTESTWEIGHTEDPATH_GRAPH_H
#include<vector>
#include<iostream>
#include<fstream>
#include<string>
#include<stack>
#include<queue>
#include<sstream>
struct adjVertex;
struct vertex{
int ID;
vertex *parent;
std::string name;
int districtID;
bool visited;
int unweightedDistance;
int weightedDistance;
std::vector<adjVertex> adj;
};
struct adjVertex{
vertex *v;
int weight;
};
class Graph
{
public:
Graph();
~Graph();
void addEdge(std::string v1, std::string v2, int weight);
void addVertex(std::string name);
void displayEdges();
void assignDistricts();
// Breadth First Search
void shortestPath(std::string startingCity, std::string endingCity);
// Dijkstras
void shortestWeightedPath(std::string startingCity, std::string endingCity);
protected:
private:
std::vector<vertex > vertices;
vertex * findVertex(std::string name);
void DFSLabel(std::string startingCity, int distID);
};
#endif //SHORTESTWEIGHTEDPATH_GRAPH_H
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.