CS 113: Introduction to Computer Science II with Introduction to C

Steve Homer---Spring 1999

Homework 6---due Tuesday, April 27

Reading: The chapter on hashing in the text.

For this problem you are to implement an undirected graph using a linked representation. The elements held at vertices of the graph will be numbers (like 1, 2, 7, etc.) Using your graph, you'll write a main program that finds the connected component of the graph which contains a particular vertex.

This assignment is different than past ones in that we are giving you MUCH more freedom than in past assignments on how you do this one. I am including an appendix here which spells out in considerable detail how you could do this assignment. You don't have to follow our suggestions in the appendix if you don't want to.

Still this assignment is not without constraints. To get credit for it you have to.

1. GRAPH MODULE

Implement you graph module using a linked list representation of the undirected graph.

One such representation was discussed in class (and as well in the text book) and another is in implementation was discussed in the Graph Lab. They are not the same, but are similar. The main difference is that the discussion section notes are based on a directed graph. The graphs you deal with here are undirected.

Only generic graph code should go in this graph module.

You must submit files h6graph.h, containing the interface, and h6graph.c, containing the implementation.

2. STACK MODULE

When you traverse the graph searching for other elements in its component, we would like you to traverse it using a stack. Thus, you simply need to take your stack from HW4 (or a student solution) and adapt it to store what you need to traverse the graph. Using a data structure to help traverse another one was covered extensively in the Breadth-first Traversal Lab. Your traversal will be similar, only it will use a stack and be "depth-first". In this component traversal, note that you only need use the stack to traverse the component (i.e., like where we used recursion in our IsReachable function in lab), you may still use iteration in other parts (e.g., if you set all the visited flags to false).

You must submit files h6stack.h, containing the interface, and h6stack.c, containing the implementation for this stack. Remember to rename those files when you reuse the old stack code, including in code that include the header.

3. MAIN PROGRAM

Write a main program which carries out a connected components algorithm (really just a graph traversal). All the main program needs to do is to:

• Read in a set of vertices and edges from standard input (i.e., the keyboard or redirected in from a file) and construct the graph they represent.
• Prompt the user for a vertex whose component must be found and printed.
• Print out that component.
• Terminate the program.

The graph that is to be read in will be given in the format:

8
2 3
1 5
1 4
2 8
4 7

As an example output, if the user asked to output the list of vertices in the component containing vertex 1, that would be 1,4,5,7.

Provide prompts and label output appropriately. If the users asks for the component of an element which is not in the graph, then nothing special is needed, just print an empty list of elements in that case.

You must submit a file named h6main.c that contains this main program.

4. MAKEFILE

Write and use a makefile for this program that will generate the executable ``h6main'' for the program above. This will be a smaller portion of your grade for this homework, but still must be done correctly to get full credit.

You should name your make file ``h6makefile'' and submit it as part of this homework. Since the utility make normally expects the makefile to be named ``Makefile'' or ``makefile'', you will have to run the make utility with:

make -f h6makefile

Since this homework uses more than one module, we suggest you first draw the dependency chart for this program, since this make file will be slightly more complicated than the last few.

6. TEST RUNS

Run your program on some test runs. Your script file (h6.scr) must contain: each source code file (use "cat" to display each), compilation (using your make file) and 4 test runs.

Construct your own test runs. They must demonstrate your program on different graphs (some with separate disconnected components, etc.)

APPENDIX:

Here are some suggestions on how to proceed with the graph implementation

An Implementation of Graphs

typedef ?? graphElementT;

typedef struct graphCDT *graphADT;

graphADT GraphCreate(void);
void GraphDestroy(graphADT graph);
void GraphAddVertex(graphADT graph, graphElementT element);
void GraphAddEdge(graphADT graph,
                  graphElementT element1,
                  graphElementT element2);
void GraphPrintComponentWith(graphADT graph,
                             graphElementT withElement,
                             FILE *outfileP);

Like last homework, the interface should also contain the prototype for one more function:

 * PrintElement is not defined here in the graph module,
 * it is only prototyped here.
 */
void PrintElement(graphElementT element, FILE *outfileP);

However, this last function must be defined in the main program h6main.c, not in the implementation file. In other words, the fact the the graph module only has a prototype for PrintElement() says that this function must be defined in a main program in order to use the module.

The implementation file will need some types of its own:

typedef struct vertexTag {
  graphElementT element;
  int visited;
  struct edgeTag *edges;
  struct vertexTag *next;
} vertexT;

typedef struct edgeTag {
  struct vertexTag *connectsTo;
  struct edgeTag *next;
} edgeT;

typedef struct graphCDT {
  vertexT *vertices;
} graphCDT;

Each vertex node contains the element at that vertex, a flag for whether it has been visited, a linked list of edges (out of this vertex), and a pointer to the next vertex node.

Each edge node contains a pointer to the vertex the edge connects to, plus a pointer to the next edge node (i.e., the next edge in the linked list of edges for a particular vertex).

The CDT just contains a pointer to the beginning of the linked list of vertices.

Graph Operations

• GraphCreate: Allocate a CDT, initialize it, and return a pointer to it to the caller.
• GraphDestroy: Deallocate all vertex AND edge nodes, then deallocate the CDT.
• GraphAddVertex: Add a new vertex to the graph. This means allocating a new vertex node, placing the element in it, and adding the node to the linked list of vertices. If that element is already there, this function needn't do anything.
• GraphAddEdge: Add a bidirectional edge between 2 vertices that are already in the graph. Should find both vertices and add 2 edges (remember since this implementation uses unidirectional edges, you have to add one edge from the first vertex to the second AND another edge from the second vertex to the first). Adding these edges will mean adding one edge node to each of the 2 vertices' linked list of edges. If either of the vertices are not in the graph, print an error message and terminate the program.
• GraphPrintComponentWith: Print out all the elements in the connected component containing the specified element. As in last homework, this function will use PrintElement() to print out each element and will print to the already-open file specified via a parameter.