C++ only. Just the program only. Can you also fix my header file and the implementation file, please? Thank you.

PROBLEM STATEMENT: Create a graph ADT that will consist of a set of vertices and a set of weighted edges. An enhanced user-friendly version of this program could be used for a variety of applications like managing travel routes for sales, people with vertices representing customer locations and edges representing the travel routes between locations with their associated costs

CODE: The Graph ADT must use an Adjacency List representation for the graph. The included struct and class definitions assume that the STL Vector class (which must be used) is being used for the Graph vertex list, with a linked edge list hanging off each vector cell (for each vertex).

Supply a client program that demonstrates that your Graph ADT class works correctly for both an undirected graph and a directed graph. It should be menu-driven. Input files provided.

Graphs.h

#ifndef GRAPHS_H #define GRAPHS_H

template // V is the vertex class; W is edge weight class struct edgeRep { V name; // Vertex name W weight; // Edge weight };

template struct vertex // Array cell structure for graph { typedef edgeRep edge; V name; // Vertex name int visited; // Used during traversal, Breadth-First or Depth-First List edgelist; // Pointer to edge list };

template class Graph { protected: vertex G[MAX]; // Main graph array for adjacency list representation // protected member functions

public: Graph(); // Constructor // . . . other constructors ~Graph(); // Destructor //Predicates: int isVertex(V& v); // Tests whether v is a vertex in the graph int isUniEdge(V& v1, V& v2); // Tests whether edge in graph int isBiDirEdge(V& v1, V& v2);// Tests whether edge (v1,v2) in graph // The following functions return -1 for failure, non-neg for success int AddVertex(V& v); // Adds vertex with name v to the graph, if v is not already in // graph, and returns the index where the vertex is stored. int DeleteVertex(V& v); // Deletes vertex with name v from the graph, if v is in the graph. // If there are any edges incident on the vertex, these edges // are deleted also. int AddUniEdge(V& v1, V& v2, W& wt); // Adds the directed edge to the graph; adds the vertices // to the graph if the vertices are not already part of the graph int void DeleteUniEdge(V& v1, V& v2); // Deletes the directed edge (any weight) from the graph, if // it is in the graph. The vertices are not deleted from the graph, // only the edge. int AddBiDirEdge(V& v1, V& v2, W& wt); // Adds the bi-directional edge (v1,v2,wt) to the graph; adds the // vertices to the graph if the vertices are not already part of // the graph int DeleteBiDirEdge(V& v1, V& v2); // Deletes the bi-directional edge (v1,v2) (any weight) from the // graph, if it is in the graph. The vertices are not deleted from // the graph, only the edge. void SimplePrintGraph(); // Prints the list of vertices in the graph, and for each vertex, // prints the list of edges in proper parenthesized notation, namely // (v1,v2,wt) or . NOTE: This is not a traversal. double ShortestDistance(V& v1, V& v2) // returns the shortest distance from vertex 1 to vertex 2 // Must implement the Dijkstra code as provided in class void GetGraph(); // Retrieves a graph from a special file and sets up the adjacency // list for the graph. I am supplying 1 such files.The program // will be able to read any graph that is in the same format: // graph node followed by any adjacent nodes with followed by distance/wieigh // to the node.The adjacency entry is terminated by # void BFTraversal(V& v); // Performs Breadth First Traversal with trace information printed void DFTraversal(V& v); //Performs a recursive Depth First Traversal of the graph starting at //specified vertex(parameter); prints trace information.

}

#endif // !GRAPHS_H

graphs2.txt - uses a directed graph (digraph)

Atlanta Houston 650 Washington 600 # Austin Dallas 200 Houston 300 # Buffalo New_York 450 Newark 500 # Chicago Denver 550 New_York 950 # Dallas Austin 200 Chicago 1500 # Denver Atlanta 800 Chicago 550 # Houston Atlanta 650 # Newark # New_York Chicago 950 Buffalo 450 # Washington Atlanta 600 Dallas 700 #

graphs3.txt - uses an undirected graph

Atlanta Houston 650 Washington 600 # Austin Dallas 200 Houston 300 # Buffalo New_York 450 Newark 500 # Chicago Denver 550 New_York 950 # Dallas Austin 200 Chicago 1500 # Denver Atlanta 800 Chicago 550 # Houston Atlanta 650 # Newark Atlanta 1100 # New_York Chicago 950 Buffalo 450 # Washington Atlanta 600 Dallas 700 #

implementation.cpp

#include #include

using namespace std;

template inline Graph::Graph() { G = new vertex(); }

template Graph::~Graph() { G = NULL; }

template int Graph::isVertex(V& v) { for (int i = 0; i < MAX; i++) { if (G[i] == v) return 1; } return 0; }

template int Graph::isUniEdge(V& v1, V& v2) { for (int i = 0; i < MAX; i++) { if (v2 != v1) { return 1; } } return 0; }

template int Graph::isBiDirEdge(V& v1, V& v2) { for (int i = 0; i < MAX; i++) { if (v2 == v1) { return 1; } } return 0; }

template int Graph::AddVertex(V& v) { G.push(v); return 1; }

template int Graph::DeleteVertex(V& v) { for (int i = 0; i < MAX; i++) { if (G[i] == v1) { G[i] == NULL; return 1; } } return 0; }

template int Graph::AddUniEdge(V& v1, V& v2, W& wt) { for (int i = 0; i < MAX; i++) { if (G[i] == NULL) { G[i] = v1; G[i + 1] = v2; return 1; } } return 0; }

template int Graph::DeleteUniEdge(V& v1, V& v2) { for (int i = 0; i < MAX; i++) { if (G[i] == v1) { G[i] == NULL; return 1; } } return 0; }

template int Graph::AddBiDirEdge(V& v1, V& v2, W& wt) { for (int i = 0; i < MAX; i++) { if (G[i] == NULL) { G[i] = v2; G[i + 1] = v1; return 1; } } return 0; }

template int Graph::DeleteBiDirEdge(V& v1, V& v2) { for (int i = 0; i < MAX; i++) { if (G[i] == v2) { G[i] == NULL; return 1; } } return 0; }

template void Graph::SimplePrintGraph() { cout << "Graph: " << endl; for (int i = 0; i < MAX; i++) { cout << G[i] << " -> "; } cout << endl; }

template double Graph::ShortestDistance(V& v1, V& v2) { int dist[V];

bool sptSet[V]; for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; dist[src] = 0; for (int count = 0; count < V - 1; count++) { int u = minDistance(dist, sptSet); sptSet[u] = true; for (int v = 0; v < V; v++) if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } displayGraph(dist); }

template void Graph::GetGraph() { for (int i = 0; i < MAX; i++) { cout << G[i] << " -> "; } cout << endl; }

template void Graph::BFTraversal(V& v) { bool* visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; list queue; visited[s] = true; queue.push_back(s); list::iterator i; while (!queue.empty()) { s = queue.front(); cout << s << " "; queue.pop_front(); for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } }

template void Graph::DFSUtil(int v, bool visited[]) { visited[v] = true; cout << v << " "; list::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) DFSUtil(*i, visited); }

template void Graph::DFTraversal(V& v) { bool* visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false;

DFSUtil(v, visited); }