Implement Graph algorithm based on the starter code provided and test your algorithms on multiple graphs.You must implement a
Need help with this assignment?Get an original answer from a qualified tutor — from $10/page.
Get it written →Implement Graph algorithm based on the starter code provided and test your algorithms on multiple graphs.You must implement all the public functions in the starter code. You can (and should) write private functions to support the public functions. Some of the critical functions are:
- Constructors: Graph()
- Destructor: ~Graph()
- Helpers: contains, verticesSize, edgesSize, vertexDegree, getEdgesAsString
- Modifiers: add, connect, disconnect, readFile
- Algorithms: dfs, bfs, dijkstra, mstPrim
Run ./create-output.sh > output.txt 2>&1 and examine the output.txt file for any issues that need fixing
__MACOSX/._2022win343d-graph-samsyl916
2022win343d-graph-samsyl916/runit.sh
#!/bin/bash # shortcut to compile and run the program rm -f a.out g++ -g -std=c++11 -Wall -Wextra -Wno-sign-compare *.cpp ./a.out
2022win343d-graph-samsyl916/graph.cpp
#include "graph.h" #include <algorithm> #include <fstream> #include <functional> #include <iostream> #include <map> #include <queue> #include <set> #include <utility> #include <vector> using namespace std; // constructor, empty graph // directionalEdges defaults to true Graph::Graph(bool directionalEdges) {} // destructor Graph::~Graph() {} // @return total number of vertices int Graph::verticesSize() const { return 0; } // @return total number of edges int Graph::edgesSize() const { return 0; } // @return number of edges from given vertex, -1 if vertex not found int Graph::vertexDegree(const string &label) const { return 0; } // @return true if vertex added, false if it already is in the graph bool Graph::add(const string &label) { return true; } /** return true if vertex already in graph */ bool Graph::contains(const string &label) const { return true; } // @return string representing edges and weights, "" if vertex not found // A-3->B, A-5->C should return B(3),C(5) string Graph::getEdgesAsString(const string &label) const { return ""; } // @return true if successfully connected bool Graph::connect(const string &from, const string &to, int weight) { return true; } bool Graph::disconnect(const string &from, const string &to) { return true; } // depth-first traversal starting from given startLabel void Graph::dfs(const string &startLabel, void visit(const string &label)) {} // breadth-first traversal starting from startLabel void Graph::bfs(const string &startLabel, void visit(const string &label)) {} // store the weights in a map // store the previous label in a map pair<map<string, int>, map<string, string>> Graph::dijkstra(const string &startLabel) const { map<string, int> weights; map<string, string> previous; // TODO(student) Your code here return make_pair(weights, previous); } // minimum spanning tree using Prim's algorithm int Graph::mstPrim(const string &startLabel, void visit(const string &from, const string &to, int weight)) const { return -1; } // minimum spanning tree using Prim's algorithm int Graph::mstKruskal(const string &startLabel, void visit(const string &from, const string &to, int weight)) const { return -1; } // read a text file and create the graph bool Graph::readFile(const string &filename) { ifstream myfile(filename); if (!myfile.is_open()) { cerr << "Failed to open " << filename << endl; return false; } int edges = 0; int weight = 0; string fromVertex; string toVertex; myfile >> edges; for (int i = 0; i < edges; ++i) { myfile >> fromVertex >> toVertex >> weight; connect(fromVertex, toVertex, weight); } myfile.close(); return true; }
2022win343d-graph-samsyl916/graphtest.cpp
2022win343d-graph-samsyl916/graphtest.cpp
/**
* Testing BST - Binary Search Tree functions
*
* @author Yusuf Pisan
* @date 19 Oct 2019
*/
#include "graph.h"
#include < cassert >
#include < iostream >
#include < sstream >
#include < string >
using namespace std ;
// global value for testing
// NOLINTNEXTLINE
stringstream globalSS ;
// need to reset SS before calling this
void vertexPrinter ( const string & s ) { globalSS << s ; }
// need to reset SS before calling this
void edgePrinter ( const string & from , const string & to , int weight ) {
globalSS << "[" << from << to << " " << weight << "]" ;
}
// convert a map to a string so we can compare it
template < typename K , typename L >
static string map2string ( const map < K , L > & mp ) {
stringstream out ;
for ( auto & p : mp ) {
out << "[" << p . first << ":" << p . second << "]" ;
}
return out . str ();
}
void testGraphBasic () {
Graph g ;
assert ( g . add ( "a" ) && "add vertex a" );
assert ( g . add ( "b" ) && "add vertex b" );
assert ( g . add ( "c" ) && "add vertex c" );
assert ( g . add ( "d" ) && "add vertex d" );
assert ( g . add ( "e" ) && "add vertex e" );
assert ( ! g . add ( "b" ) && "b added twice" );
assert ( g . connect ( "a" , "b" , 10 ) && "connect a b" );
assert ( ! g . connect ( "a" , "b" , 50 ) && "duplicate connect a b" );
assert ( ! g . connect ( "a" , "a" , 1 ) && "connect a to itself" );
g . connect ( "a" , "d" , 40 );
g . connect ( "a" , "c" , 20 );
assert (( g . verticesSize () == 5 ) && "graph number of vertices" );
assert (( g . edgesSize () == 3 ) && "graph number of edges" );
assert (( g . vertexDegree ( "a" ) == 3 ) && "vertex number of edges" );
assert (( g . vertexDegree ( "c" ) == 0 ) && "no outgoing edges c" );
assert (( g . vertexDegree ( "xxx" ) == - 1 ) && "no edges for xxx" );
assert ( ! g . contains ( "xxx" ) && "xxx not in graph" );
assert ( g . contains ( "a" ) && "a in graph" );
// check that they are sorted based on edge end label
assert ( g . getEdgesAsString ( "a" ) == "b(10),c(20),d(40)" );
// disconnect non-existent edge/vertex
assert ( ! g . disconnect ( "a" , "e" ) && "disconnecting non-existent vertex" );
assert (( g . edgesSize () == 3 ) && "disconnected nonexisting" );
assert ( g . disconnect ( "a" , "c" ) && "a-c disconnect" );
assert (( g . edgesSize () == 2 ) && "number of edges after disconnect" );
assert (( g . vertexDegree ( "a" ) == 2 ) && "a has 2 edges" );
assert ( g . getEdgesAsString ( "a" ) == "b(10),d(40)" && "removing middle edge" );
}
void testGraph0DFS () {
cout << "testGraph0DFS" << endl ;
Graph g ;
if ( ! g . readFile ( "graph0.txt" )) {
return ;
}
assert ( g . contains ( "A" ) && "a in graph" );
assert ( g . contains ( "B" ) && "b in graph" );
assert ( g . contains ( "C" ) && "c in graph" );
assert ( g . getEdgesAsString ( "A" ) == "B(1),C(8)" );
assert ( g . getEdgesAsString ( "B" ) == "C(3)" );
assert ( g . getEdgesAsString ( "C" ). empty ());
g . dfs ( "A" , vertexPrinter );
assert ( globalSS . str () == "ABC" && "starting from A" );
globalSS . str ( "" );
g . dfs ( "B" , vertexPrinter );
assert ( globalSS . str () == "BC" && "starting from B" );
globalSS . str ( "" );
g . dfs ( "C" , vertexPrinter );
assert ( globalSS . str () == "C" && "starting from C" );
globalSS . str ( "" );
g . dfs ( "X" , vertexPrinter );
assert ( globalSS . str (). empty () && "starting from X" );
}
void testGraph0BFS () {
cout << "testGraph0BFS" << endl ;
Graph g ;
if ( ! g . readFile ( "graph0.txt" )) {
return ;
}
globalSS . str ( "" );
g . bfs ( "A" , vertexPrinter );
assert ( globalSS . str () == "ABC" && "starting from A" );
globalSS . str ( "" );
g . dfs ( "B" , vertexPrinter );
assert ( globalSS . str () == "BC" && "starting from B" );
globalSS . str ( "" );
g . dfs ( "C" , vertexPrinter );
assert ( globalSS . str () == "C" && "starting from C" );
globalSS . str ( "" );
g . dfs ( "X" , vertexPrinter );
assert ( globalSS . str (). empty () && "starting from X" );
}
void testGraph0Dijkstra () {
cout << "testGraph0Dijkstra" << endl ;
Graph g ;
if ( ! g . readFile ( "graph0.txt" )) {
return ;
}
map < string , int > weights ;
map < string , string > previous ;
tie ( weights , previous ) = g . dijkstra ( "A" );
// cout << "Dijkstra(A) weights is " << map2string(weights) << endl;
assert ( map2string ( weights ) == "[B:1][C:4]" && "Dijkstra(A) weights" );
// cout << "Dijkstra(A) previous is " << map2string(previous) << endl;
assert ( map2string ( previous ) == "[B:A][C:B]" && "Dijkstra(A) previous" );
tie ( weights , previous ) = g . dijkstra ( "B" );
assert ( map2string ( weights ) == "[C:3]" && "Dijkstra(B) weights" );
assert ( map2string ( previous ) == "[C:B]" && "Dijkstra(B) previous" );
tie ( weights , previous ) = g . dijkstra ( "X" );
assert ( map2string ( weights ). empty () && "Dijkstra(C) weights" );
assert ( map2string ( previous ). empty () && "Dijkstra(C) previous" );
}
void testGraph0NotDirected () {
cout << "testGraph0NotDirected" << endl ;
bool isDirectional = false ;
Graph g ( isDirectional );
if ( ! g . readFile ( "graph0.txt" )) {
return ;
}
globalSS . str ( "" );
g . bfs ( "A" , vertexPrinter );
assert ( globalSS . str () == "ABC" && "starting from A" );
globalSS . str ( "" );
g . dfs ( "B" , vertexPrinter );
assert ( globalSS . str () == "BAC" && "starting from B" );
globalSS . str ( "" );
g <spa
Get a plagiarism-free answer to this question
Send us your instructions and we’ll match you with the best writer in your subject.
- 100% human-written, zero AI
- Turnitin report included
- Confidential — we never share your data
- Free revisions & refunds
Your pal for every paper is one click away
Join 12,000+ students getting original, on-time papers with free Turnitin reports.
All Rights Reserved Terms and Conditions
College pals.com Privacy Policy 2010-2018