Due: Wed Feb 1, 2012
This project is a way for us to get to know each other. You'll find out just how precise I expect you to be in following the software requirements and it will give me a chance to learn more about your programming background. It is quick and easy if you have had basic C before and know your simple data structures. My solution is 22 lines. As usual, you may not copy code from the net and you may not use code from your classmates. The TA will be checking all software through Moss to detect those not doing their own work.
Goal
Your goal is to implement a simple directed graph in C and to write a recursive function that visits every reachable node from a given pointer argument. You must implement the following three functions with these specific signatures:
Attached to this page, you'll find file graph.h that has these specifications as well as the Node definition below.
- newNode() Given the string payload argument, create a new Node struct then: set the state number so that it is numbered from 0..n-1 for n total states in the graph, store the payload, and set the number of edges to 0.
- addEdge() Given a source and target node, add target as an edge to the source node. Do not worry about adding more than the maximum number of edges.
- walk() Starting at node p, print out the payload string and then trace through all of the nodes reachable from edges in p. This function must be recursive.
During execution of your recursive walk, you must avoid graph cycles (looping forever). For example, if node x points to itself, a program that naively jumps from node to node, will loop forever. You need to track which nodes you have visited, but you must not alter the node structs themselves. That means you must maintain an external data structure that tracks which nodes you have seen. My suggestion is to use an array of "booleans" indexed off of the state number to track which you have seen. You may assume a max of 1000 nodes.
Graph definition
Testing
Here's a simple test program that creates a graph of 4 nodes and then walks them starting from node 'a'.
Node 'd' is not connected to the graph, so the output of this program should be
$ cc -o test main.c graph.c $ ./test a b c
If you use eclipse CDT (C development tool), then obviously you just hit run. On the other hand, I want you to notice that we are using separate compilation here. The C compiler individually compiles main.c and graph.c and then creates an executable by linking the resulting object files (*.o) together. We will test your program like this:
$ cc -o test grading.c graph.c
The grading.c file will include the graph.h file attached to this page so make sure that you don't modify graph.h and expect it to work when we test your program. Our grading file will look like this:
Deliverables
In file graph.c, you will provide the following 3 functions per the graph.h interface specification:
- addEdge function
- newNode function
- walk function
The code and data structures you need in order to prevent infinite recursion in walk() must also be placed in graph.c.
You will also turn in your test program, which must live in main.c. Your main program must not live inside graph.c otherwise we will not be able to test it with our own main.
Failure to follow naming conventions or code won't compile or code that doesn't operate exactly as specified gets 10% off
Submission
Make sure that you have a cs345 directory associated with your user account:
svn mkdir https://www.cs.usfca.edu/svn/YOUR_CS_STUDENT_LOGIN/cs345 -m 'add dir'
To map that directory to a directory on your disk, do something like this:
$ cd ~ $ svn co https://www.cs.usfca.edu/svn/YOUR_CS_STUDENT_LOGIN/cs345
This makes a cs345 in your home directory, but of course you can put it wherever you want on your local disk tree. I only care about the pathnames in subversion. Be careful not to create extra subdirectories that get mapped to subversion. I will pull your files exactly as shown below. Failure to put the files in the right directory means 10% off. We will be using a robot to pull and test your source code.
https://www.cs.usfca.edu/svn/YOUR_CS_STUDENT_LOGIN/cs345/graph/main.c https://www.cs.usfca.edu/svn/YOUR_CS_STUDENT_LOGIN/cs345/graph/graph.c
You can use the svn account for development of the software too if you would like, but I will only be looking at your jar file in the build directory.
For more information, see svn in CS601. Naturally you will have to substitute cs345 for cs601.