///////////////////////////////////////////////////////////////////////////////////////////////////////////

Implement the following functions given in the starter code (the description of each function is given in the starter code).

Graph(int vertices);

~Graph();

void addEdge(int src, int dest);

void BFS(int startVertex);

bool isBipartite(int startVertex);

void DFSUtil(int startVertex);

void DFS(int startVertex);

void topologicalSortingUtil(int startVertex);

void topologicalSorting(int startVertex);

void removeEdge(int src, int dest);

bool isEdge(int src, int dest);

int getInDegree(int src);

void printAdjVertices(int src);

bool hasCommonAdjacent(int src, int dest);

void printGraph();

Note:

1. Make sure your functions work for both directed and undirected graphs.

2. Call the printGraph function after making any changes to the graph.

Input Format: You need to read from a file named input.txt. You do not need to do anything here since this format has already been implemented in the starter code.

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Sample input (from file)/output: You can use the sample graphs from slides to check the validity of your code.

Sample input (bipartite)

7

11

1 2

1 0

1 5

3 2

3 0

4 2

4 0

4 5

6 2

6 0

6 5

Output:

Start Vertex: 2

Yes

Sample input (bipartite)

7

12

1 2

1 0

0 2

1 5

3 2

3 0

4 2

4 0

4 5

6 2

6 0

6 5

Output:

Start Vertex: 3

No

Sample input (Topological sorting)

7

12

0 3

0 4

0 6

1 2

1 4

1 5

2 3

2 4

3 4

4 5

4 6

5 6

Output: 1-->2-->0-->3-->4-->5-->6-->

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Starter code:

#include using namespace std; class Graph { int numVertices, numEdges; list *adjLists; int * distance; //keep the distance of all vertices from a source vertex int * parent; //keep the parent of all vertices during a traversal bool directed; bool* visited; //keep track of the vertices that are visited int* discoveryTime; //keep track of the vertices as they are discovered int* finishTime; //keep track of the vertices as they are finished processing int * color; list finish; public: Graph(int vertices); ~Graph(); void addEdge(int src, int dest); void BFS(int startVertex); bool isBipartite(int startVertex); void DFSUtil(int startVertex); void DFS(int startVertex); void topologicalSortingUtil(int startVertex); void topologicalSorting(int startVertex); void removeEdge(int src, int dest); bool isEdge(int src, int dest); int getInDegree(int src); void printAdjVertices(int src); bool hasCommonAdjacent(int src, int dest); void printGraph(); }; Graph::Graph(int vertices) { numVertices = vertices; numEdges = 0; directed = false; adjLists = new list [vertices]; } void Graph::addEdge(int src, int dest) { //In class if(src<0 || src>=numVertices || dest<0 || dest>=numVertices) return; adjLists[src].push_back(dest); numEdges++; if(!directed) { adjLists[dest].push_back(src); } return; } void Graph::removeEdge(int src, int dest) { //write this function numEdges--; return; } bool Graph::isEdge(int src, int dest) { //returns true if (src,dest) is an edge, otherwise should return false } int Graph::getInDegree(int src) { //returns the degree of vertex src int inDegree = 0; list ::iterator it; for (int i=0; i::iterator it; //while() { //pop the top of the queue //note that the built in pop function doesn't return any value //so, call the built in front function of queue and then call the pop function } return; } //check bipartiteness of a graph bool Graph::isBipartite(int startVertex) { //This code has the same form as BFS //Initialize // make color[startVertex] = 1 and in sert startVertex in the Queue while()//queuue is not empty { //pop the top of the queue for() //all adjacent edges { //case 1: self loop or odd edge cycle of length 1 // that means currVertex == adjVertex then return false // case 2: An edge from currVertex to adjVertex exists and adjVertex is not colored // Assign alternate color to this adjacent v of u and push it in queue // case 3: both currVertex and adjVertex has the same color // that means an edge from currVertex to adjVertex exists and adjVertex // is colored with same color as currVertex. So, return false } } } void Graph::DFSUtil(int startVertex) { } // DFS traversal of the vertices reachable from startVertex // It uses recursive DFSUtil() void Graph::DFS(int startVertex) { // Mark all the vertices as not visited // Call the recursive helper function to print DFS traversal DFSUtil(startVertex); return; } void Graph::printGraph() { list ::iterator j; printf(" Number of vertices: %d, Number of edges: %d ", numVertices, numEdges); //complete in class for(int i = 0; i"<<*j; } cout<>nVertex; Graph g(nVertex); file>>nEdge; for(i = 0; i < nEdge; i++) { file>>u; file>>v; g.addEdge(u, v); } while (1) { cout<<" ----------------------"<>choice; switch(choice) { case 1: //int u, v; cout<<"Please enter the source and destination vertes of the edge"<>u >>v; g.addEdge(u, v); break; case 2: //remove edge break; case 3: //Find Edge break; case 4: //Get Degree of a vertex cout<<"Please enter the source vertex"<>u; cout<<"Indegree of "<>u; g.BFS(u); break; case 9: //DFS break; case 10: //check bipartiteness break; case 11: //Topological sorting break; default: cout<<" Enter correct option "; } } return 0; }