[Solved] CMPS101 Assignment 2-a Graph ADT and associated operations in C

The purpose of this assignment is to implement a Graph ADT (for an Undirected Graph) and associatedoperations in C. This project will utilize your List ADT from PA1, so and make sure your List is workingproperly. Begin by reading the handout Graphs.pdf file thats on ResourcesGeneral Resources, as wellas appendices B.4 and B.5 from the text and class Lectures 8 and 9.The Adjacency List representation of a Graph consists of an array of Lists. Weve discussed thisrepresentation in Lectures 8 and 9. You will create a Graph ADT that represents a graph as an array ofLists. Each vertex will be associated with an integer label in the range 1 to numVertices, wherenumVertices is the number of vertices in the graph.Your client program will use this Graph ADT to perform various operations on the Graph that aredescribed below. The client program using your Graph ADT will be called GraphProperties, and willtake two command line arguments (here % denotes the unix prompt):% GraphProperties input_file output_fileFor PA2, you are to write a makefile that creates the executable file, called GraphProperties, similar to themakefile that you used for PA1. Include a clean utility in your makefile.2Input and Output File FormatsThe first line of the input file describes the graph, and the other lines describe operations to be performedon the graph. Most of these operations simply print values returned by functions implemented in a GraphADT that you will implement in Graph.c and Graph.h, similar to the List.c and List.h files that you usedin PA1.The first line starts with an integer that well call numVertices that tells you the number of vertices in thegraph. The rest of that line gives pair of distinct numbers in the range 1 to numVertices, separated by aspace. These numbers are the vertices for an edge. There is a comma between numVertices and the firstedge, and a comma between edges. Well also put a space after each comma for readability. Heres anexample that represents the undirected graph on Slide 12 of Lecture 8:4, 1 3, 3 2, 3 4, 4 2Note that the same graph could be represented by each of the following input lines:4, 3 1, 3 2, 4 3, 4 24, 3 1, 3 2, 1 3, 4 3, 4 2, 4 3even though the last graph has edge {1, 3} and edge {4, 3} appearing twice. (Edges {1, 3} and {3, 1} arethe same edge.)The rest of the lines in the input file that correspond to graph operations on operands. Each line beginswith a keyword, which is followed by the operands. You should output the entire input line into theoutput file as a separate line. That line should be followed by another line that just has the result of theoperation. If an input line does not follow one of the specified formats, the output on the second lineshould just say ERROR, and processing of the input file should continue. For example, its an error if theoperation isnt one of the legal operations (capitalization matters), or if the operation has the wrongnumber of operands, or if an operand thats supposed to be a vertex isnt a number between 1 andnumVertices.So the output file should always have twice as many lines as the input file (not counting the line thatdescribes the graph). For example, if an input file has 7 lines, the first of which is the graph, then theoutput should have 12 lines in it, containing each graph operation lines, each followed immediately by theresult of that operation (or ERROR).Here are the operation tokens, their operands, and descriptions of the results. As we mentioned, most ofthese operations simply print values returned by functions implemented in the Graph ADT that you willimplement in Graph.c and Graph.h. But PathExists is a little more interesting; well outline itsimplementation later in this file.3 PrintGraph takes no operands. It prints out the current graph, in the same format as an input line.But it should not print out an edge twice. Do this by only printing edge {u, v} only when u < v. GetOrder takes no operands. It returns the total number of vertices in the current graph. GetSize takes no operands. It returns the total number of edges in the current graph. GetNeighborCount takes a vertex u as operand. It returns the number of vertices that are neighbors ofu in the current graph. PathExists takes a pair of vertices u and v as operands, and outputs YES if there is a path from u to vin the current graph, and NO otherwise. A description of how to perform PathExists using a recursivesearch appears at the end of this file. (Yes, if the operands u and v are the same vertex, there is a pathfrom u to v, so the output will be YES.)4Example: For an input file that consists of the following lines:4, 3 1, 3 2, 1 3, 4 3, 4 2, 4 3PrintGraphGetSizePathExists 1 4PathExists 3GetNeighborCount 4GetNeighborCount 5GetNeighborCount 3the output file should be:PrintGraph4, 1 3, 3 2, 3 4, 4 2GetSize4PathExists 1 4YESPathExists 3ERRORGetNeighborCount 42GetNeighborCount 5ERRORGetNeighborCount 33Your Graph ADT will be implemented in files Graph.c and Graph.h. Graph.c defines a struct calledGraphObj, and Graph.h will define a type called Graph that points to this struct. (You might want to rereadthe C material in the two ADT handouts that are posted under ResourcesGeneral Resources, andreview the Queue and Stack examples that are posted under ResourcesQueueExample andResourcesStackExample.)Your GraphObj struct is required to have the following fields: numVertices, the number of vertices in the graph, called the order of the graph. numEdges, the number of edges in the graph, called the size of the graph. An array of Lists, whose jth element contains the neighbors of vertex j. This is the Adjacency Listfor vertex j. Youll use your List ADT from PA1 to represent the Adjacency List for each vertex. An array of int values whose jth element indicates whether a vertex has been visited in the currentsearch. You will define constants UNVISITED, INPROGRESS and ALLDONE in the fileGraph.h. Usage of these constants in PathExists is explained below.Since indexes of C arrays begin at 0, you might choose to use arrays that have length numVertices +1, butonly use indices 1 through numVertices. Thats so that array indices can be directly identified with vertexnumbers (and index 0 is ignored). Of course, if you prefer to have arrays of length numVertices, ratherthan numVertices + 1,that works, as long as you always remember to look at position j-1 when youreaccessing information about vertex j.5Your Graph ADT should export the following operations through the file Graph.h:/*** Constructors-Destructors ***/Graph newGraph(int numVertices);// Returns a Graph that points to a newly created GraphObj representing a graph which has// n vertices and no edges.void freeGraph(Graph* pG);// Frees all dynamic memory associated with its Graph* argument, and sets// *pG to NULL./*** Access functions ***/int getOrder(Graph G);// Returns the order of G, the number of vertices in G.int getSize(Graph G);// Returns the size of G, the number of edges in G.int getNeighborCount(Graph G, int v);// Returns the number of neighbors that vertex v has in G. Returns -1 if v is not a legal vertex.List getNeighbors(Graph G, int v);// Returns a list that has all the vertices that are neighbors of u. There is no input operation// that corresponds to getNeighbors./*** Manipulation procedures ***/int addEdge(Graph G, int u, int v);// Adds v to the adjacency list of u and u to the adjacency list of v, if that edge doesnt// already exist. If the edge does already exist, does nothing. Used when edges are entered.// Returns 0 if u and v are legal vertices, otherwise returns -1.void unvisitAll(Graph G);// Marks all vertices of the graph as UNVISITED.int getMark(Graph G, int u);// Returns the mark for vertex u, which will be UNVISITED, INPROGRESS or ALLDONE.void setMark(Graph G, int u, int theMark);// Sets the mark for vertex u to be theMark.// theMark must be UNVISITED, INPROGRESS or ALLDONE.int PathExistsRecursive(Graph G, int w, int v)// Described below; returns FOUND or NOTFOUND, which are (different) constants./*** Other operations ***/void printGraph(FILE* out, Graph G);// Prints the Graph G in the same format as an input line, so all that a client need to do is a single// call to PrintGraph(). But it should not print out an edge twice. Achieve this by only printing// the edge for {j, k} when j < k.6In addition to the above prototypes, Graph.h will define the type Graph, as well as #define constant macrosUNVISITED, INPROGRESS and ALLDONE; these should be different integers, used as marks.Graph.h will also have #define constants FOUND and NOTFOUND, which should also be differentintegers.What does GraphProperties.c do?GraphProperties reads in the first line of the input file, and uses newGraph() and addEdge() to create agraph that corresponds to that line, as described above. When it reads in a subsequent line whoseoperation token is one of GetOrder, GetSize or GetNeighborCount, it calls the corresponding function inGraph.c (using the graph that was read in as the graph argument), and outputs the value returned. Obviousrequirements about number of operands should be checked in GraphProperties.c; obvious requirementsabout operand values in should be checked in Graph.c, as we already mentioned. (If G isnt a graph, yourprogram has a bug, and should exit.) The PrintGraph function in Graph.c that is exported in Graph.hdoesnt return a value; it just prints the Graph.void PathExists(Graph G, int u, int v), which is in GraphProperties.c, has a graph and a pair of vertices uand v as its arguments, and determines whether or not there is a path from u to v, printing YES if there is apath and NO if there isnt. Heres an informal description of how to write PathExists using the GraphADT.Youll need to have a function int PathExistsRecursive(G,w,v) in Graph.c in order to execute PathExists.PathExistsRecursive determines whether there is a path from w to v, taking advantage of marks thatindicated which vertices are UNVISITED, so that we dont repeat work or get stuck in cycles.int PathExistsRecursive(G,w,v)If w=v THEN RETURN(FOUND)setMark(G,w,INPROGRESS)FOR EACH vertex x on the getNeighbors(G,w) ListtheMark = getMark(G,x).IF theMark is UNVISITEDtheFoundValue = PathExistsRecursive(G,x,v)IF theFoundValue is FOUNDreturn(FOUND)// Found a path to w, so no need to continue// Finished processing all of xs neighbors without finding vsetMark(G,w,ALLDONE)RETURN(NOTFOUND)Now that we have PathExistsRecursive(G,v), heres what PathExists(G,u,v) does:unvisitAll(G) // No vertices have been visited yettheFoundValue = PathExistsRecursive(G,u,v) )IF theFoundValue is FOUNDOUTPUT YESELSE OUTPUT NOAs usual, the result of PathExists (which will be YES or NO) should be output on a separate line,immediately after the input file line that requested graph operation PathExists.