Implement Graph algorithm based on the starter code provided and test your algorithms on multiple graphs.You must implement a
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
Collepals.com Plagiarism Free Papers
Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.
Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS
Why Hire Collepals.com writers to do your paper?
Quality- We are experienced and have access to ample research materials.
We write plagiarism Free Content
Confidential- We never share or sell your personal information to third parties.
Support-Chat with us today! We are always waiting to answer all your questions.
All Rights Reserved Terms and Conditions
College pals.com Privacy Policy 2010-2018