Grading Log for CS113 -- HW6 Name: Walsh, Alison SCRIPT FILES ====== ===== h6.scr =================================================== > Script started on Wed Apr 28 17:25:56 1999 > %cat h6main.c > /* > * Filename: h6main.c > * Name: Alison Walsh > * Class: CS 113 > * Homework: 6 > */ > > /* > * THIS IS THE MAIN PROGRAM WHICH CARRIES OUT A GRAPH TRAVERSAL. > * ------------------------------------------------------------- > * This program reads in a set of vertices and edges from the user > * and constructs the graph they represent. > * It prompts the user for a vertex whose component > * must be found and printed, and prints out that component. > * The program terminates. > */ > > #include > #include > #include > #include > > /* > * Includes header file for graph module to get type definitions > * and function prototypes needed for implementation. > */ > > #include "h6graph.h" > > /* MAIN FUNCTION */ > > int main(void) > { > /* VARIABLE DECLARATIONS */ > > int n, /* number of vertices */ > i; /* iteration variable */ > > graphElementT element1, /* first vertex of edge */ > element2, /* second vertex of edge */ > withElement; /* vertex in component to be printed */ > > graphADT graph; /* graph variable to hold all info about graph */ > > /* ACTION OF MAIN */ > > graph = GraphCreate(); /* Initializes empty graph */ > > printf("\nPlease enter the total number of vertices: "); > scanf("%d", &n); > > for(i=1; i<=n; i++) > GraphAddVertex(graph, i); /* Adds vertices */ > > printf("\nPlease enter a vertex in the component"); > printf(" you wish to be printed: "); > scanf("%d", &withElement); > > printf("\nPlease enter the edges [press Ctrl-D to end]:\t"); > > while (!feof(stdin)) { > if(scanf("%d%d", &element1, &element2) == 2) > GraphAddEdge(graph, element1, element2); /* Adds edges */ > printf("\t\t\t\t\t\t"); > } > > /* Prints component to standard output */ > GraphPrintComponentWith(graph, withElement, stdout); > > printf("\n"); > > GraphDestroy(graph); > > return(0); /* Quits program */ > > } > > /* > * Function: PrintElement > * ---------------------- > * Prints one element to output file. > */ > void PrintElement(graphElementT element, FILE *outfileP) > { > fprintf(outfileP, "%d ", element); > > } > %cat h6graph.h > /* > * File name: h6graph.h > * Name: Alison Walsh > * Assignment: 6 > * Class: cs113 > * Date: April 28, 1999 > */ > > /* > * THIS IS A HEADER FILE WHICH CONTAINS TYPE DEFINITIONS > * AND FUNCTION PROTOTYPES NEEDED FOR GRAPH IMPLEMENTATION. > */ > > #ifndef _h6graph_h /* wraps header file. */ > #define _h6graph_h > > /* TYPE DEFINITIONS */ > > typedef int graphElementT; > > typedef struct graphCDT *graphADT; > > /* FUNCTION PROTOTYPES */ > > /* > * Function: GraphCreate > * Usage: graph = GraphCreate(); > * ----------------------------- > * Creates and initializes an empty graph at start of program. > */ > > graphADT GraphCreate(void); > > /* > * Function: GraphDestroy > * Usage: GraphDestroy(graph); > * --------------------------- > * Destroys entire graph from memory at end of program. > */ > > void GraphDestroy(graphADT graph); > > /* > * Function: GraphAddVertex > * Usage: GraohAddVertex(graph, element); > * -------------------------------------- > * Adds a specific vertex to the graph. > */ > > void GraphAddVertex(graphADT graph, graphElementT element); > > /* > * Function: GraphAddEdge > * Usage: GraphAddEdge(graph, element1, element2); > * ----------------------------------------------- > * Adds a specific edge between two vertices to the graph. > */ > > void GraphAddEdge(graphADT graph, > graphElementT element1, > graphElementT element2); > > /* > * Function: GraphPrintComponentWith > * Usage: GraphPrintEdgeWith(graph, withElement, stdout); > * ------------------------------------------------------ > * Prints component of specific vertex to file. > */ > > void GraphPrintComponentWith(graphADT graph, > graphElementT withElement, > FILE *outfileP); > > /* > * Function: PrintElement > * Usage: PrintElement(element, stdout); > * ------------------------------------- > * Prints a vertex element to file. > * This is only prototyped in the graph module, > * it is defined in the main program. > */ > void PrintElement(graphElementT element, FILE *outfileP); > > #endif > %cat h6graph.c > /* > * File name: h6graph.c > * Name: Alison Walsh > * Assignment: 6 > * Class: cs113 > * Date: April 28, 1999 > */ > > /* > * THIS IS THE IMPLEMENTATION FILE FOR THE GRAPH MODULE. > */ /* * All the while loops that traverse linked lists below can be * written more concisely as "for" loops. -TF */ > #include > #include > > /* > * Gets the types and prototypes associated > * with the h6graph module. > */ > #include "h6graph.h" > > /* > * Gets the types and prototypes associated > * with the h6stack module. > */ > #include "h6stack.h" > > /* TYPE DEFINITIONS */ > > typedef struct vertexTag { /* VERTEX NODE */ > graphElementT element; /* element is vertex "number" */ > int visited; /* visited if traversed already */ > struct edgeTag *edges; /* pointer to edges */ > struct vertexTag *next; /* pointer to next vertex */ > } vertexT; > > typedef struct edgeTag { /* EDGE NODE */ > struct vertexTag *connectsTo; /* pointer to other vertex of edge */ > struct edgeTag *next; /* pointer to next edge */ > } edgeT; > > typedef struct graphCDT { /* GRAPH NODE */ > vertexT *vertices; /* pointer to first vertex */ > } graphCDT; > > /* HELPER FUNCTION PROTOTYPE */ > > /* > * Function: VertexInGraph > * Usage: vertexFoundP = VertexInGraph(graph, element); > * ----------------------------------------------- > * Returns pointer to vertex if in graph, or NULL otherwise. > */ > > vertexT *VertexInGraph(graphADT graph, graphElementT element); > > /* FUNCTION DEFINITIONS */ > > /* > * Function: GraphCreate > * -------------------- > * Allocates a CDT, initializes it and returns a pointer to it. > */ > graphADT GraphCreate(void) > { > graphADT graph; > > graph = (graphADT)malloc(sizeof(graphCDT)); /* allocates graph */ > > if(graph==NULL) { /* ERROR if not enough memory */ > fprintf(stderr, "Insufficient memory for new graph.\n"); > exit(1); /* exits the program */ > } > > graph->vertices = NULL; /* assigns first pointer to null */ > > return graph; /* returns empty graph */ > } /* Destroy is way too complicated...Simplify. -TF */ > /* > * Function: GraphDestroy > * ---------------------- > * Deallocates all vertex and and edge nodes > * and then deallocates the CDT. > */ > void GraphDestroy(graphADT graph) > { > vertexT *vertcurrP, *vertprevP; > edgeT *edgecurrP, *edgeprevP; > > while (graph->vertices != NULL) { > > vertcurrP = graph->vertices; > if (vertcurrP->next == NULL) { > while (vertcurrP->edges != NULL) { > edgecurrP = vertcurrP->edges; > if (edgecurrP->next == NULL) { > edgecurrP->connectsTo = NULL; > free(edgecurrP); > vertcurrP->edges = NULL; > } > else { > edgeprevP = edgecurrP; > edgecurrP = edgeprevP->next; > while (edgecurrP->next != NULL) { > edgeprevP = edgecurrP; > edgecurrP = edgeprevP->next; > } > edgecurrP->connectsTo = NULL; > free(edgecurrP); > edgeprevP->next = NULL; > } > } > free(vertcurrP); > graph->vertices = NULL; > } > else { > vertprevP = vertcurrP; > vertcurrP = vertprevP->next; > while (vertcurrP->next != NULL) { > vertprevP = vertcurrP; > vertcurrP = vertprevP->next; > } > while (vertcurrP->edges != NULL) { > edgecurrP = vertcurrP->edges; > if (edgecurrP->next == NULL) { > edgecurrP->connectsTo = NULL; > free(edgecurrP); > vertcurrP->edges = NULL; > } > else { > edgeprevP = edgecurrP; > edgecurrP = edgeprevP->next; > while (edgecurrP->next != NULL) { > edgeprevP = edgecurrP; > edgecurrP = edgeprevP->next; > } > edgecurrP->connectsTo = NULL; > free(edgecurrP); > edgeprevP->next = NULL; > } > } > free(vertcurrP); > vertprevP->next = NULL; > } > } > free(graph); > > } > > /* > * Function: GraphAddVertex > * ------------------------ > * Searches for element in graph. If not found, adds a new > * vertex to the graph, by allocating a new vertex node, > * placing an element in it, and adding the new node to > * the linked list of vertices. If the element is found, > * it does nothing. > */ > void GraphAddVertex(graphADT graph, graphElementT element) > { > vertexT *vertexNewP, /* pointer to vertex to be added */ > *vertexCurrP, /* pointer to current vertex */ > *vertexPrevP, /* pointer to previous vertex */ > *vertexFoundP; /* pointer to vertex already in graph */ > > /* Searches for element in graph */ > vertexFoundP = VertexInGraph(graph, element); > > if (vertexFoundP == NULL) { /* If not found in graph */ > > /* Allocates a new vertex node */ > vertexNewP = (vertexT *)malloc(sizeof(vertexT)); > > vertexNewP->element = element; /* Initializes new vertex info */ > vertexNewP->visited = 0; > vertexNewP->edges = NULL; > vertexNewP->next = NULL; > > if((graph->vertices) == NULL) /* If graph is empty, */ > graph->vertices = vertexNewP; /* adds as first vertex */ > else { /* If not, adds to end of vertices */ > vertexPrevP = graph->vertices; > vertexCurrP = (vertexPrevP)->next; > while (vertexCurrP != NULL) { > vertexPrevP = vertexCurrP; > vertexCurrP = (vertexPrevP)->next; > } /* vertexPrevP is last vertex of linked list */ > (vertexPrevP->next) = vertexNewP; > } > > } > } > > /* > * Function: GraphAddEdge > * ---------------------- > * Adds a bidirectional edge between two vertices in the graph, by > * adding one edge node to both vertices of the edge. > * If either of the vertices are not there, an error message is > * is displayed and the program terminates. > */ > void GraphAddEdge(graphADT graph, > graphElementT element1, > graphElementT element2) > { > > edgeT *edge1NewP, *edge2NewP, *edgeCurrP, *edgePrevP; > vertexT *vert1FoundP, *vert2FoundP; > > /* search for element1 in graph */ > vert1FoundP = VertexInGraph(graph, element1); > > if (vert1FoundP == NULL) { /* if not found in graph */ > fprintf(stderr, "[Vertex not in graph.]\n\n"); /* error message */ > exit(1); /* terminates */ > } > else { /* if found in graph */ > /* Allocates new edge node */ > edge1NewP = (edgeT *)malloc(sizeof(edgeT)); > edge1NewP->next = NULL; /* initializes new edge info */ > edge1NewP->connectsTo = vert1FoundP; > } > > /* search for element2 in graph */ > vert2FoundP = VertexInGraph(graph, element2); > > if (vert2FoundP == NULL) { /* if not found in graph */ > fprintf(stderr, "[Vertex not in graph.]\n\n"); /* error message */ > exit(1); /* terminates */ > } > else { /* if found in graph */ > /* Allocates new edge node */ > edge2NewP = (edgeT *)malloc(sizeof(edgeT)); > edge2NewP->next = NULL; /* initializes new edge info */ > edge2NewP->connectsTo = vert2FoundP; > } > > /* Connects new edges to linked list */ > > if ((vert2FoundP->edges) == NULL) > (vert2FoundP->edges) = edge1NewP; > else { > edgePrevP = vert2FoundP -> edges; > edgeCurrP = edgePrevP -> next; > while(edgeCurrP != NULL) { > edgePrevP = edgeCurrP; > edgeCurrP = edgePrevP -> next; > } > edgePrevP -> next = edge1NewP; > } > > if ((vert1FoundP->edges) == NULL) > (vert1FoundP->edges) = edge2NewP; > else { > edgePrevP = (vert1FoundP->edges); > edgeCurrP = (edgePrevP->next); > while(edgeCurrP != NULL) { > edgePrevP = edgeCurrP; > edgeCurrP = edgePrevP -> next; > } > edgePrevP -> next = edge2NewP; > } > > } > > /* > * Function: GraphPrintComponentWith > * --------------------------------- > * Prints all vertices in the same component as input vertex, i.e. > * all vertices that are somehow reachable from the initial vertex, > * to an output file. > */ > void GraphPrintComponentWith(graphADT graph, > graphElementT withElement, > FILE *outfileP) > { > > /* Temporary stack. */ > stackT stack; > /* Pointer to vertex node we are processing. */ > vertexT *traverseP; > /* Pointer to edge node we are processing. */ > edgeT *edgecurrP; > > printf("\n\nThe following vertices are in the component: "); > > /* Assigns visited to false for all vertices. */ > if((graph->vertices)!=NULL) { > traverseP = graph->vertices; > while (traverseP != NULL) { > traverseP->visited = 0; > traverseP = traverseP->next; > } > } > > /* Creates a stack to hold vertex node pointers. */ > StackInitialize(&stack); > > /* traverse is a pointer to the given vertex of the component. */ > traverseP = VertexInGraph(graph, withElement); > > if (traverseP == NULL) { /* If not a vertex of the graph. */ > fprintf(stderr, "\n[Vertex not in graph.]\n"); > return; > } > else { > /* Sets visited of given vertex to true. */ > traverseP->visited = 1; > /* Puts initial vertex node pointer in stack. */ > StackPush(&stack, traverseP); > } > > while (!StackIsEmpty(&stack)) { > > /* Gets top vector from stack. */ > traverseP = StackPop(&stack); > /* Prints element of vertex in component. */ > PrintElement(traverseP->element, outfileP); > > if (traverseP->edges != NULL) { > edgecurrP = traverseP->edges; > /* Loops through edges of vector. */ > while(edgecurrP != NULL) { > traverseP = edgecurrP->connectsTo; > if(traverseP->visited == 0) { > traverseP->visited = 1; > StackPush(&stack, traverseP); /* adds vector to stack */ > } > edgecurrP = edgecurrP->next; > } > } > } > > /* Cleans up the stack. */ > StackDestroy(&stack); > printf("\n"); > } > > /* HELPER FUNCTION DEFINITION */ > > /* > * Function: VertexInGraph > * ----------------------- > * Searches for element in graph and returns pointer to > * vertex if it is found, or NULL if it is not found. > */ > > vertexT *VertexInGraph(graphADT graph, graphElementT element) > { > > vertexT *vertexCurrP, *vertexFoundP = NULL; > > if((graph->vertices)==NULL) /* if graph is empty, not found */ > vertexFoundP = NULL; > else { > vertexCurrP = graph->vertices; /* search through vertices */ > while (vertexCurrP != NULL) { > if((vertexCurrP->element) == element) > vertexFoundP = vertexCurrP; /* Stop looping when you find it. -TF */ > vertexCurrP = vertexCurrP->next; > } > } > > return vertexFoundP; > > } > > %cat h6stack.h > /* > * File name: h6stack.h > * Name: Alison Walsh > * Assignment: 6 > * Class: cs113 > * Date: April 28, 1999 > */ > > /* > * THIS IS A HEADER FILE WHICH CONTAINS TYPE DEFINITIONS AND > * FUNCTION PROTOTYPES NEEDED FOR STACK IMPLEMENTATION. > */ > > #ifndef _h6stack_h /* wraps header file */ > #define _h6stack_h > > /* TYPE DEFINITIONS */ > typedef struct vertexTag *stackElementT; /* stack holds vertex pointers */ > > typedef struct stackNodeTag { > stackElementT data; > struct stackNodeTag *next; > } stackNodeT; > > typedef struct { > stackNodeT *top; > } stackT; > > /* FUNCTION PROTOTYPES */ > > /* Function : StackInitialize > * Usage : StackInitialize(&stackP); > * --------------------- > * This function creates an empty stack. > */ > void StackInitialize(stackT *); > > /* Function : StackDestroy > * Usage : StackDestroy(&stackP); > * ------------------ > * This function removes any remaining nodes in list, which > * deletes the list. > */ > void StackDestroy(stackT *); > > /* Function : StackPush > * Usage : StackPush(&stackP, stackElement) > * -------------------- > * This function places an element at the top of the stack. > */ > void StackPush(stackT *, stackElementT); > > /* Function : StackPop > * Usage : StackPop(&stackP); > * ---------------- > * This function removes an element from the top of the stack, > * and stores it in an element variable. > */ > stackElementT StackPop(stackT *); > > /* Function : StackIsEmpty > * Usage : StackIsEmpty(&stackP); > * ----------------- > * This function reports true or false based on if the > * stack is empty or not. > */ > int StackIsEmpty(stackT *); > > #endif > %cat h6stack.c > /* > * File name: h6stack.c > * Name: Alison Walsh > * Assignment: 6 > * Class: cs113 > * Date: April 28, 1999 > */ > > /* > * THIS IS THE IMPLEMENTATION FILE FOR THE STACK MODULE. > */ > > #include "h6stack.h" > #include > #include > > /* > * Function : StackInitialize() > * ---------------------------- > * Initializes top of stack pointer to null. > */ > > void StackInitialize(stackT *stack) > { > stack->top = NULL; > } > > /* > * Function : StackDestroy() > * ------------------------- > * Traverses the stack and frees each element. > * Sets top of stack to null. > */ > > void StackDestroy(stackT *stack) > { > stackNodeT *current = stack->top; > stackNodeT *temp; > > while(current != NULL) > { > temp = current; > current = current->next; > free(temp); > } > > stack->top = NULL; > } > > /* > * Function : StackPush() > * ---------------------- > * Adds element to top of stack by creating new node > * and linking it to the beginning of the linked list. > */ > > void StackPush(stackT *stack, stackElementT element) > { > /* holds address of current top field */ > stackNodeT *temp; > > /* creates the new node */ > temp = (stackNodeT *) malloc(sizeof(stackNodeT)); > if(temp!=NULL) > { > temp->next = stack->top; > temp->data = element; > stack->top = temp; > } > else { > fprintf(stderr, "Not enough memory to add element.\n"); > exit(1); > } > } > > /* > * Function StackPop() > * ------------------- > * frees the first node of the linked list, reattaches > * the rest of the linked list, and returns the data > * contained in the deleted node. > */ > > stackElementT StackPop(stackT *stack) > { > stackElementT tempelem; > > stackNodeT *tempnodeP; > > /* If the stack is not empty, pop off the top element */ > if(!StackIsEmpty(stack)) > { > /* Store the top and the top data */ > tempnodeP = stack->top; > tempelem = stack->top->data; > /* Move the top pointer to the next element */ > stack->top = stack->top->next; > free(tempnodeP); /* Delete the popped node */ > return tempelem; /* Return the data value */ > } > else /* Stack is empty, so returns error */ > { > fprintf(stderr, "There are no stack elements "); > fprintf(stderr, "to pop. Goodbye.\n"); > exit(1); > }; > } > > /* > * Function : StackIsEmpty() > * ------------------------- > * returns true if top of stack is null, signifying > * an empty stack. otherwise, returns false. > */ > int StackIsEmpty(stackT *stack) > { > return (stack->top == NULL); > } > %cat h6makefile > # Makefile for CS113 - HW6 > # Alison Walsh U79 38 0760 > # April 27, 1999 > > # ***************************************************** > # Parameters to control Makefile operation > > CC = gcc > CFLAGS = -ansi -pedantic -Wall -g > > # **************************************************** > # Entries to bring the executable up to date > > h6graph: h6main.o h6graph.o h6stack.o > $(CC) $(CFLAGS) -o h6graph h6main.o h6graph.o h6stack.o -lm > > h6main.o: h6main.c h6graph.h > $(CC) $(CFLAGS) -c h6main.c > > h6graph.o: h6graph.c h6graph.h h6stack.h > $(CC) $(CFLAGS) -c h6graph.c > > h6stack.o: h6stack.c h6stack.h > $(CC) $(CFLAGS) -c h6stack.c > %cat h6data > 10 > 1 > 1 5 > 1 2 > 3 6 > 5 2 > 3 7 > 7 4 > 2 6 > 4 8 > 7 8 > 5 10%make -f h6makefile > gcc -ansi -pedantic -Wall -g -c h6main.c > gcc -ansi -pedantic -Wall -g -c h6graph.c > gcc -ansi -pedantic -Wall -g -c h6stack.c > gcc -ansi -pedantic -Wall -g -o h6graph h6main.o h6graph.o h6stack.o -lm > %h6graph < h6data > > Please enter the total number of vertices: > Please enter a vertex in the component you wish to be printed: > Please enter the edges [press Ctrl-D to end]: > > The following vertices are in the component: 1 2 6 3 7 8 4 5 10 > > %h6graph > > Please enter the total number of vertices: 8 > > Please enter a vertex in the component you wish to be printed: 2 > > Please enter the edges [press Ctrl-D to end]: 1 2 > 2 3 > 3 1 > 7 8 > 5 6 > 6 7 > 2 8 > ^D > > The following vertices are in the component: 2 8 7 6 5 3 1 > > %h6graph > > Please enter the total number of vertices: 4 > > Please enter a vertex in the component you wish to be printed: 1 > > Please enter the edges [press Ctrl-D to end]: ^D > > The following vertices are in the component: 1 > > %h6graph > > Please enter the total number of vertices: 8 > > Please enter a vertex in the component you wish to be printed: 9 > > Please enter the edges [press Ctrl-D to end]: 2 6 > 7 2 > 7 3 > ^D > > The following vertices are in the component: > [Vertex not in graph.] > > %h6graph > > Please enter the total number of vertices: 7 > > Please enter a vertex in the component you wish to be printed: 2 > > Please enter the edges [press Ctrl-D to end]: 2 8 > [Vertex not in graph.] > > %exit > exit > > script done on Wed Apr 28 17:29:56 1999