Using C++ finish the code given.

* Write method createWeightedGraph() in weightedGraphType.h to create a weighted graph from an input file. * Complete method breadthFirstTraversal() * Compile exercise1.cpp and graphType.cpp

* Write method createWeightedGraph() in weightedGraphType.h to create a weighted graph from an input file. * Complete method breadthFirstTraversal() * Compile exercise1.cpp and graphType.cpp

input1.txt (intput file - paste this into notepad/notepad++) -----------------------------------------------------------------------------------------------------------------------

1 3 0 2 3 1 3 0 1 2 4 3

0 3 -999 5 -999 3 0 2 4 -999 -999 2 0 1 -999 5 4 1 0 2 -999 -999 -999 2 0

------------------------------------------------------------------------------------------------------------------------

//weightedGraphType.h //(must be implemented)

#include #include #include #include #include #include "graphType.h"

using namespace std;

class weightedGraphType : public graphType

{

public:

void createWeightedGraph(istream &input);

//Function to create the graph and the weight matrix.

//Postcondition: The graph using adjacency lists and

// its weight matrix is created.

void breadthFirstTraversal();

//Function to perform the breadth first traversal of

//the entire graph.

//Postcondition: The vertices of the graph are printed

// using the breadth first traversal algorithm.

void shortestPath(int vertex);

//Function to determine the weight of a shortest path

//from vertex, that is, source, to every other vertex

//in the graph.

//Postcondition: The weight of the shortest path from vertex

// to every other vertex in the graph is determined.

void printShortestDistance(int vertex);

//Function to print the shortest weight from the vertex

//specified by the parameter vertex to every other vertex in

//the graph.

//Postcondition: The weight of the shortest path from vertex

// to every other vertex in the graph is printed.

void printWeights();

weightedGraphType(int size = 0);

//Constructor

//Postcondition: gSize = 0; maxSize = size;

// graph is an array of pointers to linked lists.

// weights is a two-dimensional array to store the weights

// of the edges.

// smallestWeight is an array to store the smallest weight

// from source to vertices.

~weightedGraphType();

//Destructor

//The storage occupied by the vertices and the arrays

//weights and smallestWeight is deallocated.

protected:

int **weights; //pointer to create weight matrix

int *smallestWeight; //pointer to create the array to store

//the smallest weight from source to vertices

};

void weightedGraphType::createWeightedGraph(istream &input)

{

/* CODE HERE */

}

void weightedGraphType::breadthFirstTraversal()

{

queue q;

bool *visited;

visited = new bool[gSize];

for (int i = 0; i < gSize; i++) {

visited[i] = false;

}

for (int i = 0; i < gSize; i++) {

if (visited[i]) {

/* CODE HERE */

}

/* CODE HERE */

cout << i << " ";

while (!q.empty()) {

int u;

/* CODE HERE */

for (auto& v : graph[u]) {

if (visited[v]) {

/* CODE HERE */

}

/* CODE HERE */

cout << v << " ";

}

}

}

cout << endl;

delete [] visited;

}

void weightedGraphType::shortestPath(int vertex)

{

bool *weightFound = new bool[gSize];

for (int j = 0; j < gSize; j++) {

/* CODE HERE */

}

weightFound[vertex] = true;

smallestWeight[vertex] = 0;

for (int i = 0; i < gSize - 1; i++) {

int minWeight = INT_MAX;

int v;

for (int j = 0; j < gSize; j++) {

if (/* CODE HERE */

smallestWeight[j] < minWeight) {

/* CODE HERE */

minWeight = smallestWeight[v];

}

}

weightFound[v] = true;

for (int j = 0; j < gSize; j++) {

if (/* CODE HERE */

minWeight + weights[v][j] < smallestWeight[j]) {

/* CODE HERE */

}

}

}

delete [] weightFound;

}

void weightedGraphType::printShortestDistance(int vertex)

{

cout << "Source Vertex: " << vertex << endl;

cout << "Shortest distance from source to each vertex." << endl;

cout << "Vertex Shortest_Distance" << endl;

for (int j = 0; j < gSize; j++)

cout << setw(4) << j << setw(12) << smallestWeight[j] << endl;

cout << endl;

}

void weightedGraphType::printWeights()

{

for (int i = 0; i < gSize; i++) {

for (int j = 0; j < gSize; j++) {

if (weights[i][j] == INT_MAX) {

cout << "-\t";

} else {

cout << weights[i][j] << "\t";

}

}

cout << endl;

}

cout << endl;

}

weightedGraphType::weightedGraphType(int size) : graphType(size)

{

weights = new int*[size];

for (int i = 0; i < size; i++)

weights[i] = new int[size];

smallestWeight = new int[size];

}

weightedGraphType::~weightedGraphType()

{

for (int i = 0; i < gSize; i++)

delete [] weights[i];

delete [] weights;

delete smallestWeight;

}

-------------------------------------------------------------------------------------------------------------------------------------

//exercise1.cpp

#include #include "weightedGraphType.h"

using namespace std;

int main(int argc, const char * argv[]) { ifstream input("input1.txt"); int size = 0; string line; while (getline(input, line) && !line.empty()) { size++; } input.clear(); input.seekg(0); weightedGraphType graph(size); graph.createWeightedGraph(input); input.close();

graph.printGraph(); graph.printWeights(); cout << "Number of vertices: " << graph.getgSize() << endl << endl;

cout << "Breadth first traversal: "; graph.breadthFirstTraversal(); cout << endl;

return 0; }

--------------------------------------------------------------

//graphType.h

#ifndef graphType_h #define graphType_h

#include

class graphType { public: bool isEmpty() const; //Function to determine whether the graph is empty. //Postcondition: Returns true if the graph is empty; // otherwise, returns false. void clearGraph(); //Function to clear graph. //Postcondition: The memory occupied by each vertex // is deallocated. void printGraph() const; //Function to print graph. //Postcondition: The graph is printed. void addEdge(int u, int v); //Function to add edge to undirected graph int getgSize() const; //Add function to print Euler Walk as a series of nodes graphType(int size = 0); //Constructor //Postcondition: gSize = 0; maxSize = size; // graph is an array of pointers to linked lists. ~graphType(); //Destructor //The storage occupied by the vertices is deallocated. protected: int maxSize; //maximum number of vertices int gSize; //current number of vertices std::list *graph; private: //utility functions: check for vertices of odd degree //test if edge is a bridge };

#endif /* Graph_h */

-------------------------------------------------------------------------------------------------------------

graphType.cpp

#include #include #include #include "graphType.h"

using namespace std;

template static inline bool contains(std::list &l, const T &v) { return std::find(l.begin(), l.end(), v) != l.end(); }

graphType::graphType(int size) { maxSize = size; gSize = 0; graph = new list[size]; }

graphType::~graphType() { delete [] graph; }

int graphType::getgSize() const { return gSize; }

bool graphType::isEmpty() const { return gSize == 0; }

void graphType::clearGraph() { for (int index = 0; index < gSize; index++) graph[index].clear(); gSize = 0; } //end clearGraph

void graphType::addEdge(int u, int v) { if(graph[u].empty()) gSize++; if(graph[v].empty()) gSize++; if (!contains(graph[u], v)) graph[u].push_back(v); if (!contains(graph[v], u)) graph[v].push_back(u); }

void graphType::printGraph() const { for (int index = 0; index < gSize; index++) { cout << "[" << index << "] "; for (auto v : graph[index]) cout << v << " "; cout << endl; } cout << endl; } //end printGraph