Starting from:
$30
CMPS 101-01 Assignment 4 Solved
The purpose is to continue work with an ADT for a Directed Graph (digraph) and associated operations in C. Once again, you may utilize your List ADT, and many parts of this project will look very familiar if you completed PA3. However unlike PA3, involves Strongly Connected Components, as described in Lectures 17 and 18, and in Chapter 22 of CLRS.
As in PA3, 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 the number of vertices in the digraph. In PA3, you used this representation to identify outgoing neighbors of each vertex; perhaps in PA4 you’ll also want to identify incoming neighbors of each vertex on additional lists.
Your client program will use your Digraph ADT to perform various operations on the digraph that are described below. The client program using your Digraph ADT will once again be called
DigraphProperties, and will take two command line arguments (here %denotes the unix prompt):
% DigraphProperties input_file output_file
For PA4, you again need to write a makefile that creates the executable file, called DigraphProperties, similar to the makefiles that you used for previous Programming Assignments. Include a clean utility in your makefile.
Input and Output File Formats
The first line of the input file describes the digraph, and the other lines describe operations to be performed on the digraph. No line is more than 1000 characters long, and you should assume that all lines end with \n (newline). Most of these operations simply print values returned by functions implemented in a Digraph ADT that you will implement in Digraph.c and Digraph.h
The first line starts with an integer that we’ll call numVertices that tells you the number of vertices in the digraph. The rest of that line gives pair of distinct numbers in the range 1 to numVertices, separated by a space. These numbers are the vertices for an edge. There is a comma between numVertices and the first edge, and a comma between edges. We’ll also put a space after each comma for readability. All edges are directed. Here’s an example that represents digraph on Slide 14 of Lecture 8:
4, 1 3, 2 4, 3 4, 4 3, 3 2
Note that the same digraph could be represented by each of the following input lines:
4, 3 2, 4 3, 1 3, 3 4, 2 4
4, 3 2, 4 3, 1 3, 3 4, 2 4, 1 3
even 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 1
because 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 begins with a keyword, which is followed by the operands. You should output the entire input line into the output file as a separate line. That line should be followed by another line that just has the result of the operation. If an input line does not follow one of the specified formats, the output on the second line should just say ERROR, and processing of the input file should continue. For example, it’s an error if the operation isn’t one of the legal operations (capitalization matters), or if the operation has the wrong number of operands, or if an operand that’s supposed to be a vertex isn’t a number between 1 and numVertices.
So the output file should always have twice as many lines as the input file (not counting the line that describes the digraph). For example, if an input file has 7 lines, the first of which is the digraph, then the output should have 12 lines in it, containing each digraph operation lines, each followed immediately by the result of that operation (or ERROR).
As in PA2 and PA3: If the digraph in the first line of the input file is illegal, then you should just print out that first line, followed by another line with the word ERROR on it. Do not process any subsequent lines in the input file. What’s an illegal digraph? A digraph is illegal if the number of vertices isn’t positive, or if an edge specifies a vertex that doesn’t exist in the digraph. For example, if there are 6 vertices, both vertex 0 and vertex 7 are illegal. Also, there shouldn’t be any “self-loop” edges between a vertex and itself, so an edge (3, 3) would also make the digraph illegal.
Here are the operation tokens, their operands, and descriptions of the results. All of these operations simply print values returned by functions implemented in the Digraph ADT that you will implement in Digraph.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 the digraph, starting with the number of vertices, then a comma, then the edges.
For PA4, you must print the edges sorted by source and then by destination. If u < v, print all the edges 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 to print 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 outgoing neighbors of u in the current digraph. The out degree of a vertex u is the number of vertices v such that (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 that edge didn’t 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 didn’t exist in the current digraph, it returns 1, since no action was taken. (This is not treated as an error.)
• GetCountSCC takes no operands. It outputs the number of Strongly Connected Components in the current digraph.
• GetNumSCCVertices take a vertex u as operand. It outputs the number of vertices (including u) that are in the same Strongly Connected Component as u.
• InSameSCC takes two vertices u and v as operands. It outputs YES if u and v are in the same Strongly Connected Component of the current digraph, and NO if u and v are not in the same Strongly Connected Component of the current digraph. A vertex is always in the same Strongly Connected Components as itself.
Example: For an input file that consists of the following lines:
4, 1 3, 2 4, 3 4, 4 3, 3 2
GetSize GetCountSCC
GetNumSCCVertices 4
GetOutDegree 4
GetOutDegree 5
PrintDigraph
GetNumSCCVertices
InSameSCC 2 4
DeleteEdge 2 4
InSameSCC 2 4
GetCountSCC
AddEdge 2 1
GetCountSCC
InSameSCC 2
the output file should be:
PrintDigraph
4, 1 3, 2 4, 3 2, 3 4, 4 3
GetSize
5
GetCountSCC
2
GetNumSCCVertices
ERROR
GetNumSCCVertices 4
3
GetOutDegree 4
1
GetOutDegree 5
ERROR
InSameSCC 2 4
YES
DeleteEdge 2 4
0
InSameSCC 2 4
NO
GetCountSCC
3
AddEdge 2 1
0
GetCountSCC
1
InSameSCC 2
ERROR
Your Digraph ADT will be implemented in files Digraph.c and Digraph.h. Digraph.c defines a struct called 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, but you 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 source vertex j, the vertices k such that (j, k) is an edge in the digraph.. This is the outgoing Adjacency
List for vertex j. You’ll use your List ADT from PA1 and PA2 to represent the outgoing Adjacency List for each vertex. We strongly suggest that you keep the outgoing neighbors in sorted order, to make printing the digraph simpler.
• Other arrays, including potentially both marks and other Lists. You’ll have to determine yourselves what arrays (if any) you’ll need for PA4.
Since indexes of C arrays begin at 0, you might choose to use arrays that have length numVertices +1, but only use indices 1 through numVertices. That’s so that array indices can be directly identified with vertex numbers (and index 0 is ignored). Of course, if you prefer to have arrays of length numVertices, rather
than numVertices + 1,that works, as long as you always remember to look at position j-1 when you’re accessing information about vertex j.
Your 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.
int getCountSCC(Digraph G);
// Returns the number of Strongly Connected Components in G.
int getNumSCCVertices(Digraph G, int u);
// Returns the number of vertices (including u) that are in the same Strongly Connected Component // as u in G.. Returns -1 if u is not a legal vertex.
int inSameSCC (Digraph G, int u, int v);
// Returns 1 if u and v are in the same Strongly Connected Component of G, and returns 0 if u and v // are not in the same Strongly Connected Component of the current digraph.
// A vertex is always in the same Strongly Connected Component as itself. // Returns -1 if u is not a legal vertex.
/*** Manipulation procedures ***/
int addEdge(Digraph G, int u, int v);
// Adds v to the adjacency list of u, if that edge doesn’t 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 didn’t 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 doesn’t 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 didn’t 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 you’ll have to figure out what those functions are yourselves.
/*** 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.
In addition to the above prototypes, Digraph.h will define the type Digraph, as well as #define constant macros for constants that you decide that you need to implement the functions described above.
What does DigraphProperties.c do?
DigraphProperties reads in the first line of the input file, and uses newDigraph() and addEdge() to create a digraph that corresponds to that line, as described above. When it reads in a subsequent line whose operation token is one of GetOrder, GetSize, GetOutDegree, GetCountSCC, GetNumSCCVertices, or InSameSCC, it calls the corresponding function in Digraph.c (using the digraph that was read in as the digraph argument). It outputs the value returned, except for InSameSCC, which should output YES or NO. And if the return value indicates that there was an illegal parameter (e.g., if vertex arguments are not legal vertices), it should output ERROR.
Obvious requirements about number of operands should be checked in DigraphProperties.c; obvious requirements about operand values in should be checked in Digraph.c. (If G isn’t a digraph, your program has a bug, and should exit.) The printDigraph function in Digraph.c, which is called when the input operand is PrintDigraph, doesn’t return a value; it just prints the Digraph
As in PA3, 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 the number of vertices in the digraph. In PA3, you used this representation to identify outgoing neighbors of each vertex; perhaps in PA4 you’ll also want to identify incoming neighbors of each vertex on additional lists.
Your client program will use your Digraph ADT to perform various operations on the digraph that are described below. The client program using your Digraph ADT will once again be called
DigraphProperties, and will take two command line arguments (here %denotes the unix prompt):
% DigraphProperties input_file output_file
For PA4, you again need to write a makefile that creates the executable file, called DigraphProperties, similar to the makefiles that you used for previous Programming Assignments. Include a clean utility in your makefile.
Input and Output File Formats
The first line of the input file describes the digraph, and the other lines describe operations to be performed on the digraph. No line is more than 1000 characters long, and you should assume that all lines end with \n (newline). Most of these operations simply print values returned by functions implemented in a Digraph ADT that you will implement in Digraph.c and Digraph.h
The first line starts with an integer that we’ll call numVertices that tells you the number of vertices in the digraph. The rest of that line gives pair of distinct numbers in the range 1 to numVertices, separated by a space. These numbers are the vertices for an edge. There is a comma between numVertices and the first edge, and a comma between edges. We’ll also put a space after each comma for readability. All edges are directed. Here’s an example that represents digraph on Slide 14 of Lecture 8:
4, 1 3, 2 4, 3 4, 4 3, 3 2
Note that the same digraph could be represented by each of the following input lines:
4, 3 2, 4 3, 1 3, 3 4, 2 4
4, 3 2, 4 3, 1 3, 3 4, 2 4, 1 3
even 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 1
because 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 begins with a keyword, which is followed by the operands. You should output the entire input line into the output file as a separate line. That line should be followed by another line that just has the result of the operation. If an input line does not follow one of the specified formats, the output on the second line should just say ERROR, and processing of the input file should continue. For example, it’s an error if the operation isn’t one of the legal operations (capitalization matters), or if the operation has the wrong number of operands, or if an operand that’s supposed to be a vertex isn’t a number between 1 and numVertices.
So the output file should always have twice as many lines as the input file (not counting the line that describes the digraph). For example, if an input file has 7 lines, the first of which is the digraph, then the output should have 12 lines in it, containing each digraph operation lines, each followed immediately by the result of that operation (or ERROR).
As in PA2 and PA3: If the digraph in the first line of the input file is illegal, then you should just print out that first line, followed by another line with the word ERROR on it. Do not process any subsequent lines in the input file. What’s an illegal digraph? A digraph is illegal if the number of vertices isn’t positive, or if an edge specifies a vertex that doesn’t exist in the digraph. For example, if there are 6 vertices, both vertex 0 and vertex 7 are illegal. Also, there shouldn’t be any “self-loop” edges between a vertex and itself, so an edge (3, 3) would also make the digraph illegal.
Here are the operation tokens, their operands, and descriptions of the results. All of these operations simply print values returned by functions implemented in the Digraph ADT that you will implement in Digraph.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 the digraph, starting with the number of vertices, then a comma, then the edges.
For PA4, you must print the edges sorted by source and then by destination. If u < v, print all the edges 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 to print 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 outgoing neighbors of u in the current digraph. The out degree of a vertex u is the number of vertices v such that (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 that edge didn’t 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 didn’t exist in the current digraph, it returns 1, since no action was taken. (This is not treated as an error.)
• GetCountSCC takes no operands. It outputs the number of Strongly Connected Components in the current digraph.
• GetNumSCCVertices take a vertex u as operand. It outputs the number of vertices (including u) that are in the same Strongly Connected Component as u.
• InSameSCC takes two vertices u and v as operands. It outputs YES if u and v are in the same Strongly Connected Component of the current digraph, and NO if u and v are not in the same Strongly Connected Component of the current digraph. A vertex is always in the same Strongly Connected Components as itself.
Example: For an input file that consists of the following lines:
4, 1 3, 2 4, 3 4, 4 3, 3 2
GetSize GetCountSCC
GetNumSCCVertices 4
GetOutDegree 4
GetOutDegree 5
PrintDigraph
GetNumSCCVertices
InSameSCC 2 4
DeleteEdge 2 4
InSameSCC 2 4
GetCountSCC
AddEdge 2 1
GetCountSCC
InSameSCC 2
the output file should be:
PrintDigraph
4, 1 3, 2 4, 3 2, 3 4, 4 3
GetSize
5
GetCountSCC
2
GetNumSCCVertices
ERROR
GetNumSCCVertices 4
3
GetOutDegree 4
1
GetOutDegree 5
ERROR
InSameSCC 2 4
YES
DeleteEdge 2 4
0
InSameSCC 2 4
NO
GetCountSCC
3
AddEdge 2 1
0
GetCountSCC
1
InSameSCC 2
ERROR
Your Digraph ADT will be implemented in files Digraph.c and Digraph.h. Digraph.c defines a struct called 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, but you 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 source vertex j, the vertices k such that (j, k) is an edge in the digraph.. This is the outgoing Adjacency
List for vertex j. You’ll use your List ADT from PA1 and PA2 to represent the outgoing Adjacency List for each vertex. We strongly suggest that you keep the outgoing neighbors in sorted order, to make printing the digraph simpler.
• Other arrays, including potentially both marks and other Lists. You’ll have to determine yourselves what arrays (if any) you’ll need for PA4.
Since indexes of C arrays begin at 0, you might choose to use arrays that have length numVertices +1, but only use indices 1 through numVertices. That’s so that array indices can be directly identified with vertex numbers (and index 0 is ignored). Of course, if you prefer to have arrays of length numVertices, rather
than numVertices + 1,that works, as long as you always remember to look at position j-1 when you’re accessing information about vertex j.
Your 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.
int getCountSCC(Digraph G);
// Returns the number of Strongly Connected Components in G.
int getNumSCCVertices(Digraph G, int u);
// Returns the number of vertices (including u) that are in the same Strongly Connected Component // as u in G.. Returns -1 if u is not a legal vertex.
int inSameSCC (Digraph G, int u, int v);
// Returns 1 if u and v are in the same Strongly Connected Component of G, and returns 0 if u and v // are not in the same Strongly Connected Component of the current digraph.
// A vertex is always in the same Strongly Connected Component as itself. // Returns -1 if u is not a legal vertex.
/*** Manipulation procedures ***/
int addEdge(Digraph G, int u, int v);
// Adds v to the adjacency list of u, if that edge doesn’t 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 didn’t 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 doesn’t 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 didn’t 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 you’ll have to figure out what those functions are yourselves.
/*** 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.
In addition to the above prototypes, Digraph.h will define the type Digraph, as well as #define constant macros for constants that you decide that you need to implement the functions described above.
What does DigraphProperties.c do?
DigraphProperties reads in the first line of the input file, and uses newDigraph() and addEdge() to create a digraph that corresponds to that line, as described above. When it reads in a subsequent line whose operation token is one of GetOrder, GetSize, GetOutDegree, GetCountSCC, GetNumSCCVertices, or InSameSCC, it calls the corresponding function in Digraph.c (using the digraph that was read in as the digraph argument). It outputs the value returned, except for InSameSCC, which should output YES or NO. And if the return value indicates that there was an illegal parameter (e.g., if vertex arguments are not legal vertices), it should output ERROR.
Obvious requirements about number of operands should be checked in DigraphProperties.c; obvious requirements about operand values in should be checked in Digraph.c. (If G isn’t a digraph, your program has a bug, and should exit.) The printDigraph function in Digraph.c, which is called when the input operand is PrintDigraph, doesn’t return a value; it just prints the Digraph
1 file (190.8KB)
