****** Please use visual studio C++. I posted the assignment and the code that n

Question

****** Please use visual studio C++. I posted the assignment and the code that needs to be completed. Please make sure you look t the assignment In order to complete it. Please comment as wel for me to understand the code. Thank you.*******

Program 1- Graphs - 100 points Given a code for the graph and function prototypes (see Program 1.cpp file and Lecture #14) write the following functions: 1) add an edge (55 points) 2) remove an edge (25 points) 3) add a vertex (25 points) 4) remove a vertex (25 points)

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) //method for directed graph...to add a edge from i to 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;// edge from i to j... for directed graph..
// g->adjacencyMatrix[j][i] = true;// removing reverse edge
}
}

void removeEdge(Graph *g, int i, int j)//code to remove edge from i to j..
{
//your code here
   if (i >= 0 && i < g->vertexCount && j >= 0 && j < g->vertexCount) {
g->adjacencyMatrix[i][j] = false;// removing edge from i to j... for directed graph..
// g->adjacencyMatrix[j][i] = false;// removing reverse edge for undirectd graph..
}

}

void removeVertex(Graph *g, int n) {
//your code here

   if(n<g->vertexCount)
   {
   for(int i =n ;i<g->vertexCount-1;i++)
   {
       for(int j=0;j<g->vertexCount;j++)
       {
           g->adjacencyMatrix[i][j]=g->adjacencyMatrix[i+1][j];//updating rows  
       }
              
   }
  
   for(int i =n ;i<g->vertexCount-1;i++)
   {
       for(int j=0;j<g->vertexCount;j++)
       {
           g->adjacencyMatrix[j][i]=g->adjacencyMatrix[j][i+1];//updating columns  
       }
              
   }
   //decreasing vertexcount
   g->vertexCount--;
   //vertex removed...
   }

}

void addVertex(Graph *g) {
// your code here

   Graph *f = new Graph(g->vertexCount+1);//creating new graph with adding a vertex
  
   //now copying of edges in g to f...
   for(int i = 0;i<g->vertexCount;i++)
   {
       for(int j=0;j<g->vertexCount;j++)
       {
           if(g->adjacencyMatrix[i][j]==true)//if there is edge then
           {
               addEdge(f,i,j);//adding edge
           }  
       }  
   }
   g = f;//updating graph with new graph...

}

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, 3, 2);
printGraph(g);
//removeEdge(g, 1, 4);
//removeEdge(g, 2, 4);
addVertex(g);
printGraph(g);
delete g;
system("pause");
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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