[Solved] CMPS101 Assignment 3-Directed Graph (digraph)

The purpose of this assignment is to implement an ADT for a Directed Graph (digraph) and associatedoperations in C. PA3 will utilize your List ADT once again, and some parts of this project will look veryfamiliar if you completed PA2. You should read the Graphs.pdf file handout thats onResourcesGeneral Resources, as well as appendices B.4 and B.5 from CLRS, Chapter 22 of CLRS, andclass Lectures 8, 9, 15, etc.The Adjacency List representation of a digraph also consists of an array of Lists; this representation wasdiscussed in Lectures 8 and 9. However, the edges in a digraph are directed (like one-way streets); theremay be an edge (3, 1) between vertex 3 and vertex 1 although there is no edge (1, 3) between vertex 1 andvertex 3. You will create a Digraph ADT that represents a directed graph as an array of Lists. As in PA2,each vertex is associated with an integer label in the range 1 to numVertices, where numVertices is thenumber of vertices in the digraph.Your client program will use this Digraph ADT to perform various operations on the digraph that aredescribed below. The client program using your Digraph ADT will be called DigraphProperties, andwill take two command line arguments (here % denotes the unix prompt):% DigraphProperties input_file output_fileFor PA3, you are to write a makefile that creates the executable file, called DigraphProperties, similar tothe makefiles that you used for PA1 and PA2. Include a clean utility in your makefile.2Input and Output File FormatsThe first line of the input file describes the digraph, and the other lines describe operations to beperformed on the digraph. Most of these operations simply print values returned by functionsimplemented in a Digraph ADT that you will implement in Digraph.c and Digraph.hThe first line starts with an integer that well call numVertices that tells you the number of vertices in thedigraph. 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. All edgesare directed. Heres an example that represents digraph on Slide 14 of Lecture 8:4, 1 3, 2 4, 3 4, 4 3, 3 2Note that the same digraph could be represented by each of the following input lines:4, 3 2, 4 3, 1 3, 3 4, 2 44, 3 2, 4 3, 1 3, 3 4, 2 4, 1 3even though the edge (1, 3) appears in the last digraph twice.However, the following digraph is different:4, 3 2, 4 3, 1 3, 3 4, 2 4, 3 1because edges {1, 3} and {3, 1} are different edges.The rest of the lines in the input file that correspond to digraph 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 digraph). For example, if an input file has 7 lines, the first of which is the digraph, then theoutput should have 12 lines in it, containing each digraph operation lines, each followed immediately bythe result of that operation (or ERROR).As in PA2: If the digraph in the first line of the input file is illegal, then you should just print out thatfirst line, followed by another line with the word ERROR on it. Do not process any subsequent lines inthe input file. Whats an illegal digraph? A digraph is illegal if the number of vertices isnt positive, or ifan edge specifies a vertex that doesnt exist in the digraph. For example, if there are 6 vertices, bothvertex 0 and vertex 7 are illegal. Also, there shouldnt be any self-loop edges between a vertex anditself, so an edge (3, 3) would also make the digraph illegal.3Here are the operation tokens, their operands, and descriptions of the results. All of these operationssimply print values returned by functions implemented in the Digraph ADT that you will implement inDigraph.c and Digraph.h. PrintDigraph takes no operands. It prints out the current digraph, in the same format as an input line.Each edge should be printed out exactly once, following the same format as the input line for thedigraph, starting with the number of vertices, then a comma, then the edges.For PA3, you must print the edges sorted by source and then by destination. If u < v, print all theedges whose source is vertex u before all the edges whose source is vertex v. Also, if (u, v1) and(u, v2) are edges, and v1 < v2, print (u, v1) before (u, v2).Strong suggestion: Keep the destinations for each vertex as a sorted list. That will make it easy toprint out all the edges in the current digraph sorted as described. GetOrder takes no operands. It returns the total number of vertices in the current digraph. GetSize takes no operands. It returns the total number of edges in the current digraph. GetOutDegree takes a vertex u as operand. It returns the number of vertices that are outgoingneighbors of u in the current digraph. The out degree of a vertex u is the number of vertices v suchthat (u, v) is an edge in the digraph. AddEdge takes two vertices u and v as operands. It adds the edge (u, v) to the current digraph. If thatedge didnt exist in the current digraph, it returns 0. If that edge already existed in the current digraph,it returns 1, since no action was taken. (This is not treated as an error.) DeleteEdge takes two vertices u and v as operands. It deletes the edge (u, v) from the current digraph.If that edge already existed in the current digraph, it returns 0. If that edge didnt exist in the currentdigraph, it returns 1, since no action was taken. (This is not treated as an error.) Distance takes a pair of vertices u and v as operands, and outputs the distance from u to v in thecurrent digraph, and INF if there is no path from u to v. Of course, this must be a directed path. Yes,if the operands u and v are the same vertex, then there is a path from u to v that has no edges in it, sothe output will be 0. The distance from u to v is the length of the shortest path from u to v. Acyclic takes no operands. It outputs YES if the current digraph is acyclic, and NO otherwise. TopoSort takes no operands. It outputs a topological sort of the current digraph, if the current digraphis acyclic. (There may be more than one correct topological sort.) However, if the digraph is notacyclic, it outputs IMPOSSIBLE.4Example: For an input file that consists of the following lines:4, 1 3, 2 4, 3 4, 4 3, 3 2PrintDigraphGetSizeDistance 1 4Distance 3 1AcyclicTopoSortGetOutDegree 4GetOutDegree 5DeleteEdge 2 4AcyclicDeleteEdge 1 2DeleteEdge 3 2AddEdge 1 2AcyclicTopoSortthe output file should be:PrintDigraph4, 1 3, 2 4, 3 2, 3 4, 4 3GetSize5Distance 1 42Distance 3 1INFAcyclicNOTopoSortIMPOSSIBLEGetOutDegree 41GetOutDegree 5ERRORDeleteEdge 2 40AcyclicNODeleteEdge 1 21DeleteEdge 4 30AddEdge 1 20AcyclicYESTopoSort1 3 2 45Your Digraph ADT will be implemented in files Digraph.c and Digraph.h. Digraph.c defines a structcalled DigraphObj, and Digraph.h should define a type called Digraph that points to this struct.Your DigraphObj struct is required to have the following fields. It is okay for you to have other fields, butyou should document them in your README file. numVertices, the number of vertices in the digraph, called the order of the digraph. numEdges, the number of edges in the digraph, called the size of the digraph. An array of Lists, whose jth element contains the outgoing neighbors (destinations) from sourcevertex j, the vertices k such that (j, k) is an edge in the digraph.. This is the outgoing AdjacencyList for vertex j. Youll use your List ADT from PA1 and PA2 to represent the outgoingAdjacency List for each vertex. We strongly suggest that you keep the outgoing neighbors insorted order, to make printing the digraph simpler. Other arrays similar to the marks that you used in PA2. Youll have to determine yourselves whatarrays (if any) youll need for PA3.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.6Your Digraph ADT should export the following operations through the file Digraph.h:/*** Constructors-Destructors ***/Digraph newDigraph(int numVertices);// Returns a Digraph that points to a newly created DigraphObj representing a digraph which has// n vertices and no edges.void freeDigraph(Digraph* pG);// Frees all dynamic memory associated with its Digraph* argument, and sets// *pG to NULL./*** Access functions ***/int getOrder(Digraph G);// Returns the order of G, the number of vertices in G.int getSize(Digraph G);// Returns the size of G, the number of edges in G.int getOutDegree(Digraph G, int u);// Returns the number of outgoing neighbors that vertex u has in G, the number of vertices v such// that (u, v) is an edge in G. Returns -1 if v is not a legal vertex.List getNeighbors(Digraph G, int u);// Returns a list that has all the vertices that are outgoing neighbors of vertex u, i.e.,// a list that has all the vertices v such that (u, v) is an edge in G.// There is no input operation that corresponds to getNeighbors./*** Manipulation procedures ***/int addEdge(Digraph G, int u, int v);// Adds v to the adjacency list of u, if that edge doesnt already exist.// If the edge does already exist, does nothing. Used when edges are entered or added.// Returns 0 if (u, v) is a legal edge, and the edge didnt already exist.// Returns 1 if (u, v) is a legal edge and the edge did already exist.// Returns -1 if (u, v) is not a legal edge.int deleteEdge(Digraph G, int u, int v);// Deletes v from the adjacency list of u, if that edge exists.// If the edge doesnt exist, does nothing. Used when edges are deleted.// Returns 0 if (u, v) is a legal edge, and the edge did already exist.// Returns 1 if (u, v) is a legal edge and the edge didnt already exist.// Returns -1 if (u, v) is not a legal edge.You probably will want to have other functions in Digraph.c/Digraph.h that are similar to the unvisitAll,getMark and setMark functions in PA). But youll have to figure out what those functions are yourselves.7/*** Other operations ***/void printDigraph(FILE* out, Digraph G);// Outputs the digraph G in the same format as an input line, including the number of vertices// and the edges. The edges should be in sorted order, as described above.void distance(FILE* out, Digraph G, int u, int v);// Outputs the distance between vertices u and v if there is a directed path between them in the// digraph. Otherwise, outputs INFvoid acyclic(FILE* out, Digraph G);// Outputs YES if the digraph is acyclic. Otherwise, outputs NO.void topoSort(FILE* out, Digraph G);// Outputs a topological sort of the digraph. If the digraph is not acyclic, outputs IMPOSSIBLE.In addition to the above prototypes, Digraph.h will define the type Digraph, as well as #define constantmacros for constants that you decide that you need to implement the functions described above.8What does DigraphProperties.c do?DigraphProperties reads in the first line of the input file, and uses newDigraph() and addEdge() to create adigraph that corresponds to that line, as described above. When it reads in a subsequent line whoseoperation token is one of GetOrder, GetSize or GetOutDegree, it calls the corresponding function inDigraph.c (using the digraph that was read in as the digraph argument), and outputs the value returned.For other operations tokens (Distance, Acyclic, TopoSort), it calls the corresponding function in Digraph.cwhich performs its own output. Obvious requirements about number of operands should be checked inDigraphProperties.c; obvious requirements about operand values in should be checked in Digraph.c. (If Gisnt a digraph, your program has a bug, and should exit.)About distance: Find the distance between two vertices of a digraph using BFS. See Section 22.2 ofCLRS.About acyclic: A digraph is acyclic if and only if a DFS of the digraph produces no back edges, asdescribed in Section 22.3 of CLRS. Youll have to figure out how to implement this.About topological sort: Topological sort using DFS was discussed in Lecture 16 (February 15). SeeSection 22.4 of CLRS.