C++ Program Help! Implement a graph class using linked lists ( a dynamic array t
ID: 3569924 • Letter: C
Question
C++ Program Help!
Implement a graph class using linked lists ( a dynamic array that stores vertices and, for each vertex, a linked list of edge nodes ).
The class should have the following methods:
A constructor
A copy constructor
A destructor
An addVertex method
An addEdge method
A deleteVertex method
A deleteEdge method
An isFull and isEmpty methods
A makeEmpty method
A getWeightmethod that returns the weight of an edge
A getVertices given a vertex v it returns a queue of vertices adjacent to v
A resetVisited
A setVertexVisited
A bool method called isVisited
Remember to include a Visited array in your data members.
Write a menu-driven program to THOROUGHLY check your class and all the methods included in your program. You can choose the data type for the list. Allow the user to continue with operations as long as he/she wants to.
Your program should check if an operation is possible ( ex: check if list is empty before attempting to delete an item; check if list is full before attempting to insert an item)
Your program should have the following methods:
A DFS method to perform a Depth First Search from a given vertex
A BFS method to perform a Breadth First Search from a given vertex
A shortestPath method that print the shortest path from a given vertex v to any other vertex
Additional methods that will make your program more structured.
send the program to steve9413@hotmail.com and I will rate the best answer.
Explanation / Answer
Program:
/*File; Graph.h*/
#ifndef GRAPH_H
#define GRAPH_H
#include <cstddef>
#include <list>
#include <deque>
#include <algorithm>
#include <iostream>
#define VSIZE_STEP 5
struct Vertex {
std::list<struct Edge> adj;
bool visited;
Vertex();
};
class Graph {
private:
// Note: vertices are identified by their index in the verts array (so 0=first vertex)
size_t vsize;
Vertex *verts;
size_t nverts;
size_t nedges;
public:
typedef size_t vxid;
Graph(); //constructor
Graph(const Graph &g); //copy constructor
~Graph(); //destructor
// Overload stream insertion operator to display vertices and edges (adjacent vertices)
friend std::ostream &operator<<(std::ostream &os, const Graph &g);
// 'Add' num vertices (increase number of vertices and increase size if full), returns new total number of vertices
vxid addVertex(unsigned int num);
// Add directed edge from v1 to v2, returns false if v1 or v2 do not exist
bool addEdge(vxid v1, vxid v2, unsigned int weight);
// Remove a vertex, returns false if v does not exist
bool deleteVertex(vxid v);
// Remove directed edge from v1 to v2, returns false if v1 or v2 do not exist
bool deleteEdge(vxid v1, vxid v2);
// Accessors
size_t getNumVertices();
size_t getNumEdges();
// Returns whether or not graph is at capacity (will need reallocation if another vertex is added)
bool isFull();
// Returns whether or not graph has any vertices
bool isEmpty();
// Deletes all vertices
void makeEmpty();
// Return the weight of the directed edge from v1 to v2 or 0 if no such edge exists
unsigned int getWeight(vxid v1, vxid v2);
// Gets a queue of the vertices adjacent to v
std::deque<vxid> getVertices(vxid v);
// Sets vertex v to not visited, returns false if there is no such vertex
bool resetVisited(vxid v);
// Sets all vertices to not visited
void resetAllVisited();
// Sets vertex v to visited, returns false if there is no such vertex
bool setVertexVisited(vxid v);
// Returns whether or not a vertex is visited
bool isVisited(vxid v);
};
struct Edge {
Graph::vxid vto;
unsigned int weight;
Edge(Graph::vxid vto, unsigned int w);
};
#endif
/*File: Graph.cpp */
#include "Graph.h"
Graph::Graph() {
vsize = VSIZE_STEP;
verts = new Vertex[vsize];
nverts = 0;
nedges = 0;
}
Graph::Graph(const Graph &g) {
vsize = g.vsize;
verts = new Vertex[g.vsize];
std::copy(g.verts, g.verts + g.nverts, verts);
nverts = g.nverts;
nedges = g.nedges;
}
Graph::~Graph() {
delete[] verts;
}
std::ostream &operator<<(std::ostream &os, const Graph &g) {
os << "Vertex ID ---> Adjacent Vertex {Weight}, ... ";
for (size_t i = 0; i < g.nverts; ++i) {
os << i << " ---> ";
for (std::list<Edge>::iterator j = g.verts[i].adj.begin(); j != g.verts[i].adj.end(); ++j) {
os << j->vto << "{" << j->weight << "}" << ((std::next(j, 1) != g.verts[i].adj.end()) ? ", " : "");
}
os << " ";
}
return os;
}
Vertex::Vertex() {
visited = false;
}
Edge::Edge(Graph::vxid v, unsigned int wt) {
vto = v;
weight = wt;
}
Graph::vxid Graph::addVertex(unsigned int num) {
if (nverts + num >= vsize + 1) { //resize vertex array
size_t newSize = vsize + ((num + nverts - vsize) / (unsigned int)VSIZE_STEP + ((num + nverts - vsize) % (unsigned int)VSIZE_STEP != 0)) * VSIZE_STEP;
Vertex *rv = new Vertex[newSize];
std::copy(verts, verts + nverts, rv);
delete[] verts;
verts = rv;
vsize = newSize;
}
return nverts += num;
}
bool Graph::addEdge(vxid v1, vxid v2, unsigned int weight) {
if (v1 >= nverts || v2 >= nverts)
return false;
// Check to see if this edge already exists (if it does just change the weight)
bool exists = false;
for (std::list<Edge>::iterator i = verts[v1].adj.begin(); i != verts[v1].adj.end(); ++i) {
if (i->vto == v2) {
i->weight = weight;
exists = true;
break;
}
}
if (!exists) {
Edge newEdge(v2, weight);
verts[v1].adj.push_back(newEdge);
++nedges;
}
return true;
}
bool Graph::deleteVertex(vxid v) {
if (v >= nverts)
return false;
// Delete edges directed to vertex, update ids in edges
for (size_t i = 0; i < nverts; ++i) {
if (i != v) {
std::list<Edge>::iterator j;
bool found = false;
for (j = verts[i].adj.begin(); j != verts[i].adj.end(); ++j) {
if (j->vto == v) {
found = true;
break;
} else if (j->vto > v) {
--j->vto;
}
}
if (found)
verts[i].adj.erase(j);
}
}
// Delete the vertex
for (size_t i = v; i < nverts - 1; ++i)
verts[i] = verts[i + 1];
--nverts;
return true;
}
bool Graph::deleteEdge(vxid v1, vxid v2) {
if (v1 >= nverts || v2 >= nverts)
return false;
bool del = false;
std::list<Edge>::iterator i;
for (i = verts[v1].adj.begin(); i != verts[v1].adj.end(); ++i) {
if (i->vto == v2) {
del = true;
break;
}
}
if (del) {
verts[v1].adj.erase(i);
--nedges;
}
return del;
}
size_t Graph::getNumVertices() {
return nverts;
}
size_t Graph::getNumEdges() {
return nedges;
}
bool Graph::isFull() {
return (nverts == vsize);
}
bool Graph::isEmpty() {
return (nverts == 0);
}
void Graph::makeEmpty() {
delete[] verts;
vsize = VSIZE_STEP;
verts = new Vertex[vsize];
nverts = 0;
nverts = 0;
nedges = 0;
}
unsigned int Graph::getWeight(vxid v1, vxid v2) {
if (v1 >= nverts || v2 >= nverts)
return 0;
unsigned int weight = 0;
for (std::list<Edge>::iterator i = verts[v1].adj.begin(); i != verts[v1].adj.end(); ++i) {
if (i->vto == v2) {
weight = i->weight;
break;
}
}
return weight;
}
std::deque<Graph::vxid> Graph::getVertices(vxid v) {
std::deque<Graph::vxid> vts;
if (v >= nverts)
return vts;
std::list<Edge> vasd = verts[v].adj;
for (std::list<Edge>::iterator i = verts[v].adj.begin(); i != verts[v].adj.end(); ++i)
vts.push_back(i->vto);
return vts;
}
bool Graph::resetVisited(vxid v) {
if (v >= nverts)
return false;
verts[v].visited = false;
return true;
}
void Graph::resetAllVisited() {
for (size_t i = 0; i < nverts; ++i)
verts[i].visited = false;
}
bool Graph::setVertexVisited(vxid v) {
if (v >= nverts)
return false;
verts[v].visited = true;
return true;
}
bool Graph::isVisited(vxid v) {
return verts[v].visited;
}
/* File:GraphTest.cpp*/
#include <iostream>
#include <deque>
#include "Graph.h"
using namespace std;
void depthFirstSearch(Graph g, Graph::vxid v);
void breadthFirstSearch(Graph g, Graph::vxid v);
void shortestPath(Graph g, Graph::vxid v1, Graph::vxid v2);
int main() {
Graph g;
int vertex, edge, choice, weight;
int vertex1, vertex2;
char ch;
do {
cout << endl;
cout << "Welcome to Graph exercise practice." << endl;
cout << "----------------Menu--------------" << endl;
cout << "1. To add vertex." << endl;
cout << "2. To add edge." << endl;
cout << "3. To delete a vertex." << endl;
cout << "4. To delete an edge. " << endl;
cout << "5. To print the graph details." << endl;
cout << "6. To view the details of depth first search." << endl;
cout << "7. To view the details of breadth first search." << endl;
cout << "8. To find the shortest path." << endl;
cout << endl;
cout << "Enter your choice: ";
cin >> choice;
switch (choice)
{
case 1:
cout << "Enter the number of vertices of the graph to construct: ";
cin >> vertex;
g.addVertex(vertex);
cout << g;
break;
case 2:
cout << "Enter the weight of the edge: ";
cin >> weight;
cout << "Enter the initial vertex of the edge: ";
cin >> vertex1;
cout << "Enter the end vertex of the edge: ";
cin >> vertex2;
g.addEdge(vertex1, vertex2, weight);
cout << g;
break;
case 3:
cout << "Enter a vertex to be deleted: ";
cin >> vertex;
cout << "Delete Vertex " << vertex << " ";
g.deleteVertex(vertex);
cout << g;
break;
case 4:
cout << "Enter an initial vertex of edge to be deleted:";
cin >> vertex1;
cout << "Enter an end vertex of edge to be deleted:";
cin >> vertex1;
cout << "Delete Edge " << vertex1 << " --> " << vertex2 << " ";
g.deleteEdge(5, 3);
cout << g;
break;
case 5:
cout << g;
break;
case 6:
cout << "Enter the vertex: ";
cin >> vertex;
depthFirstSearch(g, vertex);
cout << " ";
break;
case 7:
cout << "Enter the vertex: ";
cin >> vertex;
breadthFirstSearch(g, vertex);
cout << " ";
break;
case 8:
cout << "Enter the starting vertex: ";
cin >> vertex1;
cout << "Enter the end vertex: ";
cin >> vertex2;
shortestPath(g, vertex1, vertex2);
cout << endl;
break;
default:
cout << "Please enter the choice correctly." << endl;
}
cout << " Would you like to continue? Press Y for yes." << endl;
cin >> ch;
} while (ch == 'y' || ch == 'Y');
system("pause");
return 0;
}
void depthFirstSearch(Graph g, Graph::vxid v) {
cout << "Enumerating vertices with depth first search starting at " << v << " ";
g.resetAllVisited();
deque<Graph::vxid> search;
search.push_back(v);
Graph::vxid cv;
while (!search.empty()) {
cv = search.back();
search.pop_back();
if (!g.isVisited(cv)) {
cout << cv << " ";
g.setVertexVisited(cv);
deque<Graph::vxid> adj = g.getVertices(cv);
search.insert(search.end(), adj.begin(), adj.end());
}
}
cout << " ";
g.resetAllVisited();
}
void breadthFirstSearch(Graph g, Graph::vxid v) {
cout << "Enumerating vertices with breadth first search starting at " << v << " ";
g.resetAllVisited();
deque<Graph::vxid> search;
search.push_back(v);
g.setVertexVisited(v);
cout << v << " ";
Graph::vxid cv;
while (!search.empty()) {
cv = search.front();
search.pop_front();
deque<Graph::vxid> adj = g.getVertices(cv);
for (deque<Graph::vxid>::iterator i = adj.begin(); i != adj.end(); ++i) {
if (!g.isVisited(*i)) {
cout << *i << " ";
g.setVertexVisited(*i);
search.push_back(*i);
}
}
}
cout << " ";
g.resetAllVisited();
}
// Uses Dijkstra's algorithm to determine shortest path from vertex1 to vertex2
void shortestPath(Graph g, Graph::vxid v1, Graph::vxid v2) {
cout << "Shortest path from " << v1 << " to " << v2 << ": ";
deque<Graph::vxid> search;
Graph::vxid n = g.getNumVertices();
unsigned int *dist = new unsigned int[n];
Graph::vxid *path = new Graph::vxid[n];
for (Graph::vxid i = 0; i < n; ++i) {
dist[i] = (unsigned int)-1;
//path[i] = 0;
search.push_back(i);
}
dist[v1] = 0;
Graph::vxid cv;
unsigned int other;
while (!search.empty()) {
deque<Graph::vxid>::iterator i, min = search.begin();
for (i = search.begin(); i != search.end(); ++i) {
if (dist[*i] < dist[*min]) {
min = i;
}
}
cv = *min;
search.erase(min);
if (cv == v2)
break;
deque<Graph::vxid> adj = g.getVertices(cv);
for (deque<Graph::vxid>::iterator i = adj.begin(); i != adj.end(); ++i) {
other = dist[cv] + g.getWeight(cv, *i);
if (other < dist[*i]) {
dist[*i] = other;
path[*i] = cv;
}
}
}
search.clear();
for (Graph::vxid i = v2; i != v1; i = path[i]) {
search.push_front(i);
}
search.push_front(v1);
for (deque<Graph::vxid>::iterator i = search.begin(); i != search.end(); ++i)
cout << *i << " ";
delete[] dist;
delete[] path;
}
Sample Output:
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 1
Enter the number of vertices of the graph to construct: 5
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 --->
1 --->
2 --->
3 --->
4 --->
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 2
Enter the weight of the edge: 2
Enter the initial vertex of the edge: 1
Enter the end vertex of the edge: 2
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 --->
1 ---> 2{2}
2 --->
3 --->
4 --->
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 2
Enter the weight of the edge: 5
Enter the initial vertex of the edge: 0
Enter the end vertex of the edge: 1
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 ---> 1{5}
1 ---> 2{2}
2 --->
3 --->
4 --->
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 2
Enter the weight of the edge: 14
Enter the initial vertex of the edge: 2
Enter the end vertex of the edge: 3
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 ---> 1{5}
1 ---> 2{2}
2 ---> 3{14}
3 --->
4 --->
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 2
Enter the weight of the edge: 5
Enter the initial vertex of the edge: 2
Enter the end vertex of the edge: 4
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 ---> 1{5}
1 ---> 2{2}
2 ---> 3{14}, 4{5}
3 --->
4 --->
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 2
Enter the weight of the edge: 4
Enter the initial vertex of the edge: 2
Enter the end vertex of the edge: 1
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 ---> 1{5}
1 ---> 2{2}
2 ---> 3{14}, 4{5}, 1{4}
3 --->
4 --->
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 2
Enter the weight of the edge: 13
Enter the initial vertex of the edge: 3
Enter the end vertex of the edge: 4
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 ---> 1{5}
1 ---> 2{2}
2 ---> 3{14}, 4{5}, 1{4}
3 ---> 4{13}
4 --->
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 2
Enter the weight of the edge: 30
Enter the initial vertex of the edge: 4
Enter the end vertex of the edge: 1
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 ---> 1{5}
1 ---> 2{2}
2 ---> 3{14}, 4{5}, 1{4}
3 ---> 4{13}
4 ---> 1{30}
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 5
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 ---> 1{5}
1 ---> 2{2}
2 ---> 3{14}, 4{5}, 1{4}
3 ---> 4{13}
4 ---> 1{30}
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 6
Enter the vertex: 2
Enumerating vertices with depth first search starting at 2
2 1 4 3
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 7
Enter the vertex: 1
Enumerating vertices with breadth first search starting at 1
1 2 3 4
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 8
Enter the starting vertex: 0
Enter the end vertex: 4
Shortest path from 0 to 4:
0 1 2 4 Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 8
Enter the starting vertex: 2
Enter the end vertex: 4
Shortest path from 2 to 4:
2 4 Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 3
Enter a vertex to be deleted: 0
Delete Vertex 0
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 ---> 1{2}
1 ---> 2{14}, 3{5}, 0{4}
2 ---> 3{13}
3 ---> 0{30}
Would you like to continue? Press Y for yes.
y
Welcome to Graph exercise practice.
----------------Menu--------------
1. To add vertex.
2. To add edge.
3. To delete a vertex.
4. To delete an edge.
5. To print the graph details.
6. To view the details of depth first search.
7. To view the details of breadth first search.
8. To find the shortest path.
Enter your choice: 4
Enter an initial vertex of edge to be deleted:3
Enter an end vertex of edge to be deleted:4
Delete Edge 4 --> 4
Vertex ID ---> Adjacent Vertex {Weight}, ...
0 ---> 1{2}
1 ---> 2{14}, 3{5}, 0{4}
2 ---> 3{13}
3 ---> 0{30}
Would you like to continue? Press Y for yes.
d
Press any key to continue . . .
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.