C++ Please complete the given code Given a code for the graph and function proto

Question

C++

Please complete the given code

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);
bool isEdge(Graph *g, int i, int j);
void removeEdge(Graph *g, int i, int j);
void removeVertex(Graph *g, int i);
void addVertex(Graph *g);
void printGraph(Graph *g);

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[i][i] = true;
}
}
void removeEdge(Graph *g, int i, int j) {
if(i>0 && i<g->vertexCount && j>0 && j<g->vertexCount)
{
g->adjacencyMatrix[i][j]=false;
}
}
void removeVertex(Graph *g, int i) {
//your code here
for (int j = 0; j < g->vertexCount; j++) {
        removeEdge(g,i,j);
}
g->vertexCount--;
}

void addVertex(Graph *g) {
   Graph *temp = new Graph(g->vertexCount+1);
   for (int i = 0; i<g->vertexCount; i++) {
   for (int j = 0; j < g->vertexCount; j++) {
   if (isEdge(g, i, j))
       addEdge(temp,i,j);
   }
   }
   *g=*temp;
}
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;
return 0;
}

Online URL for testing : http://ideone.com/xg7l4Y

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.