C++ Given a code for the graph and function prototypes (see Program2.cpp file) w
ID: 3820139 • Letter: C
Question
C++
Given a code for the graph and function prototypes (see Program2.cpp file) write the following functions:
1) add an edge
2) remove an edge
3) add a vertex
4) remove a vertex
######################### Program2.cpp ##########################
/* Source code was adapted from the class representation: http://www.algolist.net/Data_structures/Graph/Internal_representation */
#include <iostream>
#include <string>
using namespace std;
struct Graph {
Graph(int v) {
vertexCount = v;
adjacencyMatrix = new bool*[v];
for (int i = 0; i < vertexCount; i++) {
adjacencyMatrix[i] = new bool[v];
for (int j = 0; j < v; j++)
adjacencyMatrix[i][j] = false;
}
};
~Graph() {
for (int i = 0; i < vertexCount; i++)
delete[] adjacencyMatrix[i];
delete[] adjacencyMatrix;
};
bool** adjacencyMatrix;
int vertexCount;
};
void addEdge(Graph *g, int i, int j) {
//The code given below is for the undirected graph. Modify it to for the directed graph
if (i >= 0 && i < g->vertexCount && j > 0 && j < g->vertexCount) {
g->adjacencyMatrix[i][j] = true;
g->adjacencyMatrix[j][i] = true;
}
}
void removeEdge(Graph *g, int i, int j) {
//your code here
}
void removeVertex(Graph *g, int i) {
//your code here
}
void addVertex(Graph *g) {
// your code here
}
bool isEdge(Graph *g, int i, int j) {
if (i >= 0 && i < g->vertexCount && j > 0 && j < g->vertexCount)
return g->adjacencyMatrix[i][j];
else
return false;
}
void printGraph(Graph *g) {
cout << "Graph:" << endl;
for (int i = 0; i<g->vertexCount; i++) {
cout << "Edges from vertex " << i << ": ";
for (int j = 0; j < g->vertexCount; j++) {
if (isEdge(g, i, j))
cout << j << ", ";
}
cout << endl;
}
}
int main()
{
Graph *g = new Graph(5);
addEdge(g, 1, 4);
addEdge(g, 1, 2);
addEdge(g, 1, 3);
addEdge(g, 1, 0);
addEdge(g, 3, 2);
addEdge(g, 3, 1);
addEdge(g, 4, 1);
cout << "Original graph:" << endl;
printGraph(g);
removeEdge(g, 1, 4);
removeEdge(g, 2, 4);
cout << "Test removing edges:" << endl;
printGraph(g);
addVertex(g);
addEdge(g, 5, 0);
cout << "Test adding a vertex:" << endl;
printGraph(g);
removeVertex(g, 3);
cout << "Test removing a vertex:" << endl;
printGraph(g);
delete g;
system("pause");
return 0;
}
######################### Expected Output ##########################
Original graph:
Graph:
Edges from vertex 0:
Edges from vertex 1: 2, 3, 4,
Edges from vertex 2:
Edges from vertex 3: 1, 2,
Edges from vertex 4: 1,
Test removing edges:
Graph:
Edges from vertex 0:
Edges from vertex 1: 2, 3,
Edges from vertex 2:
Edges from vertex 3: 1, 2,
Edges from vertex 4: 1,
Test adding a vertex:
Graph:
Edges from vertex 0:
Edges from vertex 1: 2, 3,
Edges from vertex 2:
Edges from vertex 3: 1, 2,
Edges from vertex 4: 1,
Edges from vertex 5:
Test removing a vertex:
Graph:
Edges from vertex 0:
Edges from vertex 1: 2, 3,
Edges from vertex 2:
Edges from vertex 3:
Edges from vertex 4: 1,
Explanation / Answer
#include <iostream>
#include <string>
using namespace std;
struct Graph {
Graph(int v) {
vertexCount = v;
adjacencyMatrix = new bool*[v];
for (int i = 0; i < vertexCount; i++) {
adjacencyMatrix[i] = new bool[v];
for (int j = 0; j < v; j++)
adjacencyMatrix[i][j] = false;
}
};
~Graph() {
for (int i = 0; i < vertexCount; i++)
delete[] adjacencyMatrix[i];
delete[] adjacencyMatrix;
};
bool** adjacencyMatrix;
int vertexCount;
};
void addEdge(Graph *g, int i, int j) {
if (i >= 0 && i < g->vertexCount && j > 0 && j < g->vertexCount) {
g->adjacencyMatrix[i][j] = true;
g->adjacencyMatrix[j][i] = true;
}
}
void removeEdge(Graph *g, int i, int j) {
//your code here
}
void removeVertex(Graph *g, int i) {
}
void addVertex(Graph *g) {
}
bool isEdge(Graph *g, int i, int j) {
if (i >= 0 && i < g->vertexCount && j > 0 && j < g->vertexCount)
return g->adjacencyMatrix[i][j];
else
return false;
}
void printGraph(Graph *g) {
cout << "Graph:" << endl;
for (int i = 0; i<g->vertexCount; i++) {
cout << "Edges from vertex " << i << ": ";
for (int j = 0; j < g->vertexCount; j++) {
if (isEdge(g, i, j))
cout << j << ", ";
}
cout << endl;
}
}
int main()
{
Graph *g = new Graph(5);
addEdge(g, 1, 4);
addEdge(g, 1, 2);
addEdge(g, 1, 3);
addEdge(g, 1, 0);
addEdge(g, 3, 2);
addEdge(g, 3, 1);
addEdge(g, 4, 1);
cout << "Original graph:" << endl;
printGraph(g);
removeEdge(g, 1, 4);
removeEdge(g, 2, 4);
cout << "Test removing edges:" << endl;
printGraph(g);
addVertex(g);
addEdge(g, 5, 0);
cout << "Test adding a vertex:" << endl;
printGraph(g);
removeVertex(g, 3);
cout << "Test removing a vertex:" << endl;
printGraph(g);
delete g;
system("pause");
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.