Description
The purpose of this assignment is to implement a Graph ADT (for an Undirected Graph) and associated
operations in C. This project will utilize your List ADT from PA1, so and make sure your List is working
properly. Begin by reading the handout Graphs.pdf file that’s on ResourcesàGeneral Resources, as well
as 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. We’ve discussed this
representation in Lectures 8 and 9. You will create a Graph ADT that represents a graph as an array of
Lists. Each vertex will be associated with an integer label in the range 1 to numVertices, where
numVertices is the number of vertices in the graph.
Your client program will use this Graph ADT to perform various operations on the Graph that are
described below. The client program using your Graph ADT will be called GraphProperties, and will
take two command line arguments (here % denotes the unix prompt):
% GraphProperties input_file output_file
For PA2, you are to write a makefile that creates the executable file, called GraphProperties, similar to the
makefile that you used for PA1. Include a clean utility in your makefile.
2
Input and Output File Formats
The first line of the input file describes the graph, and the other lines describe operations to be performed
on the graph. Most of these operations simply print values returned by functions implemented in a Graph
ADT that you will implement in Graph.c and Graph.h, similar to the List.c and List.h files that you used
in PA1.
The first line starts with an integer that we’ll call numVertices that tells you the number of vertices in the
graph. 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. Here’s an
example that represents the undirected graph on Slide 12 of Lecture 8:
4, 1 3, 3 2, 3 4, 4 2
Note that the same graph could be represented by each of the following input lines:
4, 3 1, 3 2, 4 3, 4 2
4, 3 1, 3 2, 1 3, 4 3, 4 2, 4 3
even though the last graph has edge {1, 3} and edge {4, 3} appearing twice. (Edges {1, 3} and {3, 1} are
the same edge.)
The rest of the lines in the input file that correspond to graph 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 graph). For example, if an input file has 7 lines, the first of which is the graph, then the
output should have 12 lines in it, containing each graph operation lines, each followed immediately by the
result of that operation (or ERROR).
Here are the operation tokens, their operands, and descriptions of the results. As we mentioned, most of
these operations simply print values returned by functions implemented in the Graph ADT that you will
implement in Graph.c and Graph.h. But PathExists is a little more interesting; we’ll outline its
implementation 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 of
u 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 v
in the current graph, and NO otherwise. A description of how to perform PathExists using a recursive
search appears at the end of this file. (Yes, if the operands u and v are the same vertex, there is a path
from u to v, so the output will be YES.)
4
Example: For an input file that consists of the following lines:
4, 3 1, 3 2, 1 3, 4 3, 4 2, 4 3
PrintGraph
GetSize
PathExists 1 4
PathExists 3
GetNeighborCount 4
GetNeighborCount 5
GetNeighborCount 3
the output file should be:
PrintGraph
4, 1 3, 3 2, 3 4, 4 2
GetSize
4
PathExists 1 4
YES
PathExists 3
ERROR
GetNeighborCount 4
2
GetNeighborCount 5
ERROR
GetNeighborCount 3
3
Your Graph ADT will be implemented in files Graph.c and Graph.h. Graph.c defines a struct called
GraphObj, and Graph.h will define a type called Graph that points to this struct. (You might want to reread
the C material in the two ADT handouts that are posted under ResourcesàGeneral Resources, and
review the Queue and Stack examples that are posted under ResourcesàQueueExample and
ResourcesàStackExample.)
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 List
for vertex j. You’ll 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 current
search. You will define constants UNVISITED, INPROGRESS and ALLDONE in the file
Graph.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, 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.
5
Your 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 doesn’t
// 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.
6
In addition to the above prototypes, Graph.h will define the type Graph, as well as #define constant macros
UNVISITED, 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 different
integers.
What does GraphProperties.c do?
GraphProperties reads in the first line of the input file, and uses newGraph() and addEdge() to create a
graph that corresponds to that line, as described above. When it reads in a subsequent line whose
operation token is one of GetOrder, GetSize or GetNeighborCount, it calls the corresponding function in
Graph.c (using the graph that was read in as the graph argument), and outputs the value returned. Obvious
requirements about number of operands should be checked in GraphProperties.c; obvious requirements
about operand values in should be checked in Graph.c, as we already mentioned. (If G isn’t a graph, your
program has a bug, and should exit.) The PrintGraph function in Graph.c that is exported in Graph.h
doesn’t 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 u
and v as its arguments, and determines whether or not there is a path from u to v, printing YES if there is a
path and NO if there isn’t. Here’s an informal description of how to write PathExists using the Graph
ADT.
You’ll 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” that
indicated which vertices are UNVISITED, so that we don’t 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) List
theMark = getMark(G,x).
IF theMark is UNVISITED
theFoundValue = PathExistsRecursive(G,x,v)
IF theFoundValue is FOUND
return(FOUND)
// Found a path to w, so no need to continue
// Finished processing all of x’s neighbors without finding v
setMark(G,w,ALLDONE)
RETURN(NOTFOUND)
Now that we have PathExistsRecursive(G,v), here’s what PathExists(G,u,v) does:
unvisitAll(G) // No vertices have been visited yet
theFoundValue = PathExistsRecursive(G,u,v) )
IF theFoundValue is FOUND
OUTPUT YES
ELSE OUTPUT ‘NO’
As 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.
