Prerequisites You are provided with a complete circular linked-list deque implementation in deque.c. You should be familiar with the Deque data structure and how to use it before starting this assignment. You should also be familiar with the DFS and BFS graph traversal algorithms. DFS and BFS implementation Your job is to implement iterative versions of DFS and BFS. These functions take two vertices and return 1 if there is a path between the vertices (a sequence of edges connecting them) and 0 otherwise. As a reference, you are provided with a complete recursive DFS implementation, dfsRecursive, in graph.c. The Deque implemented in deque.c can be used as a stack or a queue for your DFS and BFS implementations. This gives you a chance to apply some of your data structure knowledge from earlier in the course. Implement the functions in graph.c with the // FIXME: Implement comments. There are two tests in graphTests.c that compare the results of your functions against the results of dfsRecursive for every pair of vertices on a series of random graphs. Each test prints the graph it is about to test your functions on, so you can more easily use these tests to help you debug. If your implementations pass these tests, then they are likely (but maybe not uaranteed) correct. You can build the tests with make or make tests and run them with ./tests. Feel free to tweak or add your own tests for debugging. Note: You can ignore the deque tests in dequeTests.c. Those are just verification for the skeleton code. Written questions The program in main.c loads 3 predetermined graphs from files and prints the results of your DFS and BFS functions on each pair of vertices. For each pair, path or no path is printed for BFS and BFS separately, indicating if there is a path between vertices according to that function. You can build the program with make or make prog and run it with ./prog. After you finish your DFS and BFS implementations, run this program and then answer the following questions. 1. How is the graph stored in the provided code? Is it represented as an adjacency matrix or list? 2. Which of the 3 graphs are connected? How can you tell? 3. Imagine that we ran each depth-first and breadth-first searches in the other direction (from destination to source). Would the output change at all? Would the output change if the graphs were directed graphs? 4. What are some pros and cons of DFS vs BFS? When would you use one over the other? 5. What is the Big O execution time to determine if a vertex is reachable from another vertex? Tips Pay careful attention to the struct definitions. In particular the Graph struct contains an array of Vertex structs (all of the verices in the graph), while the Vertex struct contains an array of pointer to the Vertex structs that are neighbors of the vertex. These pointers point to the same vertices stored in the Graph structs array. The edges in this graph are undirected, meaning that an edge from vertex1 to vertex2 and an edgefrom vertex2 to vertex1 are the same edge. A graph is connected if there is at least one path between every pair of vertices in the graph. If a Vertex* vertex had at least three neighbors, to access the third neighbor we would write vertex->neighbors[2]. You can check for memory leaks on flip by typing make memcheckTests or make memcheckProg on the command line for tests or prog respectively.

CuTest.h

#ifndef CU_TEST_H

#define CU_TEST_H

#include #include

#define CUTEST_VERSION "CuTest 1.5"

char* CuStrAlloc(int size); char* CuStrCopy(const char* old);

#define CU_ALLOC(TYPE) ((TYPE*) malloc(sizeof(TYPE)))

#define HUGE_STRING_LEN 8192 #define STRING_MAX 256 #define STRING_INC 256

typedef struct { int length; int size; char* buffer; } CuString;

void CuStringInit(CuString* str); CuString* CuStringNew(void); void CuStringRead(CuString* str, const char* path); void CuStringAppend(CuString* str, const char* text); void CuStringAppendChar(CuString* str, char ch); void CuStringAppendFormat(CuString* str, const char* format, ...); void CuStringInsert(CuString* str, const char* text, int pos); void CuStringResize(CuString* str, int newSize); void CuStringDelete(CuString* str);

typedef struct CuTest CuTest;

typedef void (*TestFunction)(CuTest *);

struct CuTest { char* name; TestFunction function; int failed; int ran; int parents; char* message; jmp_buf *jumpBuf; };

void CuTestInit(CuTest* t, const char* name, TestFunction function); CuTest* CuTestNew(const char* name, TestFunction function); CuTest* CuTestCopy(CuTest* t); void CuTestRun(CuTest* tc); void CuTestDelete(CuTest *t);

void CuFail_Line(CuTest* tc, const char* file, int line, const char* message2, const char* message); void CuAssert_Line(CuTest* tc, const char* file, int line, const char* message, int condition); void CuAssertStrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, const char* expected, const char* actual); void CuAssertIntEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, int expected, int actual); void CuAssertDblEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, double expected, double actual, double delta); void CuAssertPtrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, void* expected, void* actual);

#define CuFail(tc, ms) CuFail_Line( (tc), __FILE__, __LINE__, NULL, (ms)) #define CuAssert(tc, ms, cond) CuAssert_Line((tc), __FILE__, __LINE__, (ms), (cond)) #define CuAssertTrue(tc, cond) CuAssert_Line((tc), __FILE__, __LINE__, "assert failed", (cond))

#define CuAssertStrEquals(tc,ex,ac) CuAssertStrEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac)) #define CuAssertStrEquals_Msg(tc,ms,ex,ac) CuAssertStrEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac)) #define CuAssertIntEquals(tc,ex,ac) CuAssertIntEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac)) #define CuAssertIntEquals_Msg(tc,ms,ex,ac) CuAssertIntEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac)) #define CuAssertDblEquals(tc,ex,ac,dl) CuAssertDblEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac),(dl)) #define CuAssertDblEquals_Msg(tc,ms,ex,ac,dl) CuAssertDblEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac),(dl)) #define CuAssertPtrEquals(tc,ex,ac) CuAssertPtrEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac)) #define CuAssertPtrEquals_Msg(tc,ms,ex,ac) CuAssertPtrEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac))

#define CuAssertPtrNotNull(tc,p) CuAssert_Line((tc),__FILE__,__LINE__,"null pointer unexpected",(p != NULL)) #define CuAssertPtrNotNullMsg(tc,msg,p) CuAssert_Line((tc),__FILE__,__LINE__,(msg),(p != NULL))

#define MAX_TEST_CASES 1024

#define SUITE_ADD_TEST(SUITE,TEST) CuSuiteAdd(SUITE, CuTestNew(#TEST, TEST))

typedef struct { int count; CuTest* list[MAX_TEST_CASES]; int failCount;

} CuSuite;

void CuSuiteInit(CuSuite* testSuite); CuSuite* CuSuiteNew(void); void CuSuiteDelete(CuSuite *testSuite); void CuSuiteAdd(CuSuite* testSuite, CuTest *testCase); void CuSuiteAddSuite(CuSuite* testSuite, CuSuite* testSuite2); void CuSuiteConsume(CuSuite* testSuite, CuSuite* testSuite2); void CuSuiteRun(CuSuite* testSuite); void CuSuiteSummary(CuSuite* testSuite, CuString* summary); void CuSuiteDetails(CuSuite* testSuite, CuString* details);

#endif /* CU_TEST_H */

CuTest.c

#include #include #include #include #include #include #include

#include "CuTest.h"

char* CuStrAlloc(int size) { char* newStr = (char*) malloc( sizeof(char) * (size) ); return newStr; }

char* CuStrCopy(const char* old) { int len = strlen(old); char* newStr = CuStrAlloc(len + 1); strcpy(newStr, old); return newStr; }

void CuStringInit(CuString* str) { str->length = 0; str->size = STRING_MAX; str->buffer = (char*) malloc(sizeof(char) * str->size); str->buffer[0] = '\0'; }

CuString* CuStringNew(void) { CuString* str = (CuString*) malloc(sizeof(CuString)); str->length = 0; str->size = STRING_MAX; str->buffer = (char*) malloc(sizeof(char) * str->size); str->buffer[0] = '\0'; return str; }

void CuStringDelete(CuString *str) { if (!str) return; free(str->buffer); free(str); }

void CuStringResize(CuString* str, int newSize) { str->buffer = (char*) realloc(str->buffer, sizeof(char) * newSize); str->size = newSize; }

void CuStringAppend(CuString* str, const char* text) { int length;

if (text == NULL) { text = "NULL"; }

length = strlen(text); if (str->length + length + 1 >= str->size) CuStringResize(str, str->length + length + 1 + STRING_INC); str->length += length; strcat(str->buffer, text); }

void CuStringAppendChar(CuString* str, char ch) { char text[2]; text[0] = ch; text[1] = '\0'; CuStringAppend(str, text); }

void CuStringAppendFormat(CuString* str, const char* format, ...) { va_list argp; char buf[HUGE_STRING_LEN]; va_start(argp, format); vsprintf(buf, format, argp); va_end(argp); CuStringAppend(str, buf); }

void CuStringInsert(CuString* str, const char* text, int pos) { int length = strlen(text); if (pos > str->length) pos = str->length; if (str->length + length + 1 >= str->size) CuStringResize(str, str->length + length + 1 + STRING_INC); memmove(str->buffer + pos + length, str->buffer + pos, (str->length - pos) + 1); str->length += length; memcpy(str->buffer + pos, text, length); }

void CuTestInit(CuTest* t, const char* name, TestFunction function) { t->name = CuStrCopy(name); t->failed = 0; t->ran = 0; t->parents = 0; t->message = NULL; t->function = function; t->jumpBuf = NULL; }

CuTest* CuTestNew(const char* name, TestFunction function) { CuTest* tc = CU_ALLOC(CuTest); CuTestInit(tc, name, function); return tc; }

CuTest* CuTestCopy(CuTest* t) { CuTest* copy = CU_ALLOC(CuTest); memcpy(copy, t, sizeof(CuTest)); return copy; }

void CuTestDelete(CuTest *t) { if (!t) return; if (--t->parents < 1){ free(t->name); free(t->message); free(t); } }

void CuTestRun(CuTest* tc) { jmp_buf buf; tc->jumpBuf = &buf; if (setjmp(buf) == 0){ tc->ran = 1; (tc->function)(tc); } tc->jumpBuf = 0; }

static void CuFailInternal(CuTest* tc, const char* file, int line, CuString* string) { char buf[HUGE_STRING_LEN];

sprintf(buf, "%s:%d: ", file, line); CuStringInsert(string, buf, 0);

tc->failed = 1; tc->message = string->buffer; if (tc->jumpBuf != 0) longjmp(*(tc->jumpBuf), 0); }

void CuFail_Line(CuTest* tc, const char* file, int line, const char* message2, const char* message) { CuString string;

CuStringInit(&string); if (message2 != NULL){ CuStringAppend(&string, message2); CuStringAppend(&string, ": "); } CuStringAppend(&string, message); CuFailInternal(tc, file, line, &string); }

void CuAssert_Line(CuTest* tc, const char* file, int line, const char* message, int condition) { if (condition) return; CuFail_Line(tc, file, line, NULL, message); }

void CuAssertStrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, const char* expected, const char* actual) { CuString string; if ((expected == NULL && actual == NULL) || (expected != NULL && actual != NULL && strcmp(expected, actual) == 0)) { return; }

CuStringInit(&string); if (message != NULL){ CuStringAppend(&string, message); CuStringAppend(&string, ": "); } CuStringAppend(&string, "expected <"); CuStringAppend(&string, expected); CuStringAppend(&string, "> but was <"); CuStringAppend(&string, actual); CuStringAppend(&string, ">"); CuFailInternal(tc, file, line, &string); }

void CuAssertIntEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, int expected, int actual) { char buf[STRING_MAX]; if (expected == actual) return; sprintf(buf, "expected <%d> but was <%d>", expected, actual); CuFail_Line(tc, file, line, message, buf); }

void CuAssertDblEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, double expected, double actual, double delta) { char buf[STRING_MAX]; if (fabs(expected - actual) <= delta) return; sprintf(buf, "expected <%f> but was <%f>", expected, actual);

CuFail_Line(tc, file, line, message, buf); }

void CuAssertPtrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, void* expected, void* actual) { char buf[STRING_MAX]; if (expected == actual) return; sprintf(buf, "expected pointer <0x%p> but was <0x%p>", expected, actual); CuFail_Line(tc, file, line, message, buf); }

void CuSuiteInit(CuSuite* testSuite) { testSuite->count = 0; testSuite->failCount = 0; memset(testSuite->list, 0, sizeof(testSuite->list)); }

CuSuite* CuSuiteNew(void) { CuSuite* testSuite = CU_ALLOC(CuSuite); CuSuiteInit(testSuite); return testSuite; }

void CuSuiteDelete(CuSuite *testSuite) { unsigned int n; for (n=0; n < MAX_TEST_CASES; n++){ if (testSuite->list[n]){ CuTestDelete(testSuite->list[n]); } } free(testSuite);

}

void CuSuiteAdd(CuSuite* testSuite, CuTest *testCase) { assert(testSuite->count < MAX_TEST_CASES); testSuite->list[testSuite->count] = testCase; testSuite->count++; if (testCase->parents != INT_MAX){ testCase->parents++; }else{ testCase = CuTestCopy(testCase); } }

void CuSuiteAddSuite(CuSuite* testSuite, CuSuite* testSuite2) { int i; for (i = 0 ; i < testSuite2->count ; ++i){ CuTest* testCase = testSuite2->list[i]; CuSuiteAdd(testSuite, testCase); } }

void CuSuiteConsume(CuSuite* testSuite, CuSuite* testSuite2) { CuSuiteAddSuite(testSuite, testSuite2); CuSuiteDelete(testSuite2); }

void CuSuiteRun(CuSuite* testSuite) { int i; for (i = 0 ; i < testSuite->count ; ++i){ CuTest* testCase = testSuite->list[i]; CuTestRun(testCase); if (testCase->failed) { testSuite->failCount += 1; } } }

void CuSuiteSummary(CuSuite* testSuite, CuString* summary) { int i; for (i = 0 ; i < testSuite->count ; ++i){ CuTest* testCase = testSuite->list[i]; CuStringAppend(summary, testCase->failed ? "F" : "."); } CuStringAppend(summary, " "); }

void CuSuiteDetails(CuSuite* testSuite, CuString* details) { int i; int failCount = 0;

if (testSuite->failCount == 0){ int passCount = testSuite->count - testSuite->failCount; const char* testWord = passCount == 1 ? "test" : "tests"; CuStringAppendFormat(details, "OK (%d %s) ", passCount, testWord); } else { if (testSuite->failCount == 1) CuStringAppend(details, "There was 1 failure: "); else CuStringAppendFormat(details, "There were %d failures: ", testSuite->failCount);

for (i = 0 ; i < testSuite->count ; ++i){ CuTest* testCase = testSuite->list[i]; if (testCase->failed){ failCount++; CuStringAppendFormat(details, "%d) %s: %s ", failCount, testCase->name, testCase->message); } } CuStringAppend(details, " !!!FAILURES!!! ");

CuStringAppendFormat(details, "Runs: %d ", testSuite->count); CuStringAppendFormat(details, "Passes: %d ", testSuite->count - testSuite->failCount); CuStringAppendFormat(details, "Fails: %d ", testSuite->failCount); } }

deque.h

#ifndef DEQUE_H #define DEQUE_H

typedef void* Type; typedef struct Link Link; typedef struct Deque Deque;

struct Link { Type value; Link* next; Link* prev; };

struct Deque { int size; Link* sentinel; };

Deque* dequeNew(); void dequeDelete(Deque* deque); void dequePushFront(Deque* deque, Type value); void dequePushBack(Deque* deque, Type value); Type dequeFront(Deque* deque); Type dequeBack(Deque* deque); void dequePopFront(Deque* deque); void dequePopBack(Deque* deque); int dequeIsEmpty(Deque* deque); void dequeClear(Deque* deque);

#endif

deque.c

#include "deque.h" #include #include

static void removeLink(Link* link) { link->prev->next = link->next; link->next->prev = link->prev; free(link); }

static void addLinkAfter(Link* link, Type value) { Link* newLink = malloc(sizeof(Link)); newLink->value = value; newLink->next = link->next; newLink->prev = link; newLink->next->prev = newLink; newLink->prev->next = newLink; }

Deque* dequeNew() { Deque* deque = malloc(sizeof(Deque)); assert(deque != NULL); Link* sentinel = malloc(sizeof(Link)); sentinel->next = sentinel; sentinel->prev = sentinel; deque->sentinel = sentinel; deque->size = 0; return deque; }

void dequeDelete(Deque* deque) { dequeClear(deque); free(deque->sentinel); free(deque); }

void dequePushFront(Deque* deque, Type value) { addLinkAfter(deque->sentinel, value); ++(deque->size); }

void dequePushBack(Deque* deque, Type value) { addLinkAfter(deque->sentinel->prev, value); ++(deque->size); }

Type dequeFront(Deque* deque) { assert(deque->size > 0); return deque->sentinel->next->value; }

Type dequeBack(Deque* deque) { assert(deque->size > 0); return deque->sentinel->prev->value; }

void dequePopFront(Deque* deque) { assert(deque->size > 0); removeLink(deque->sentinel->next); --(deque->size); }

void dequePopBack(Deque* deque) { assert(deque->size > 0); removeLink(deque->sentinel->prev); --(deque->size); }

int dequeIsEmpty(Deque* deque) { return deque->size == 0; }

void dequeClear(Deque* deque) { while (!dequeIsEmpty(deque)){ dequePopFront(deque); } }

dequeTests.c

#include "cutest/CuTest.h" #include "deque.h" #include

int** createValues(int n) { int** values = malloc(sizeof(int*) * n); for (int i = 0; i < n; ++i){ values[i] = malloc(sizeof(int)); *values[i] = i; } return values; }

void freeValues(int** values, int n) { for (int i = 0; i < n; ++i){ free(values[i]); } free(values); }

void testPushFrontPopFront(CuTest* test) { const int N = 100; int** values = createValues(N); Deque* deque = dequeNew(); CuAssertIntEquals(test, 1, dequeIsEmpty(deque)); for (int i = 0; i < N; ++i){ dequePushFront(deque, values[i]); } for (int i = 0; i < N; ++i){ CuAssertIntEquals(test, 0, dequeIsEmpty(deque)); CuAssertPtrEquals(test, values[N - i - 1], dequeFront(deque)); CuAssertPtrEquals(test, values[0], dequeBack(deque)); dequePopFront(deque); } CuAssertIntEquals(test, 1, dequeIsEmpty(deque)); dequeDelete(deque); freeValues(values, N); }

void testPushFrontPopBack(CuTest* test) { const int N = 100; int** values = createValues(N); Deque* deque = dequeNew(); CuAssertIntEquals(test, 1, dequeIsEmpty(deque)); for (int i = 0; i < N; ++i){ dequePushFront(deque, values[i]); } for (int i = 0; i < N; ++i){ CuAssertIntEquals(test, 0, dequeIsEmpty(deque)); CuAssertPtrEquals(test, values[N - 1], dequeFront(deque)); CuAssertPtrEquals(test, values[i], dequeBack(deque)); dequePopBack(deque); } CuAssertIntEquals(test, 1, dequeIsEmpty(deque)); dequeDelete(deque); freeValues(values, N); }

void testPushBackPopFront(CuTest* test) { const int N = 100; int** values = createValues(N); Deque* deque = dequeNew(); CuAssertIntEquals(test, 1, dequeIsEmpty(deque)); for (int i = 0; i < N; ++i){ dequePushBack(deque, values[i]); } for (int i = 0; i < N; ++i){ CuAssertIntEquals(test, 0, dequeIsEmpty(deque)); CuAssertPtrEquals(test, values[N - 1], dequeBack(deque)); CuAssertPtrEquals(test, values[i], dequeFront(deque)); dequePopFront(deque); } CuAssertIntEquals(test, 1, dequeIsEmpty(deque)); dequeDelete(deque); freeValues(values, N); }

void testPushBackPopBack(CuTest* test) { const int N = 100; int** values = createValues(N); Deque* deque = dequeNew(); CuAssertIntEquals(test, 1, dequeIsEmpty(deque)); for (int i = 0; i < N; ++i){ dequePushBack(deque, values[i]); } for (int i = 0; i < N; ++i){ CuAssertIntEquals(test, 0, dequeIsEmpty(deque)); CuAssertPtrEquals(test, values[N - i - 1], dequeBack(deque)); CuAssertPtrEquals(test, values[0], dequeFront(deque)); dequePopBack(deque); } CuAssertIntEquals(test, 1, dequeIsEmpty(deque)); dequeDelete(deque); freeValues(values, N); }

CuSuite* getDequeTestSuite() { CuSuite* suite = CuSuiteNew(); SUITE_ADD_TEST(suite, testPushFrontPopFront); SUITE_ADD_TEST(suite, testPushFrontPopBack); SUITE_ADD_TEST(suite, testPushBackPopFront); SUITE_ADD_TEST(suite, testPushBackPopBack); return suite; }

graph.h

#ifndef GRAPH_H #define GRAPH_H

typedef struct Vertex Vertex;

typedef struct Graph Graph;

struct Vertex { int label; int isVisited; int numNeighbors; Vertex** neighbors; };

struct Graph { int numEdges; int numVertices; Vertex* vertexSet; };

int dfsRecursive(Graph* graph, Vertex* source, Vertex* destination); int dfsIterative(Graph* graph, Vertex* source, Vertex* destination); int bfsIterative(Graph* graph, Vertex* source, Vertex* destination);

Graph* randomGraph(int numVertices, int numEdges); Graph* loadGraph(const char* fileName); void freeGraph(Graph* graph); void printGraph(Graph* graph);

#endif

graph.c

#include "graph.h" #include "deque.h" #include #include #include #include

static void clearVisited(Graph* graph) { for (int i = 0; i < graph->numVertices; ++i){ graph->vertexSet[i].isVisited = 0; } }

static int DfsRecursiveHelper(Graph* graph, Vertex* vertex, Vertex* destination)

{ vertex->isVisited = 1; if (vertex == destination){ return 1; } for (int i = 0; i < vertex->numNeighbors; ++i){ Vertex* neighbor = vertex->neighbors[i]; if (!neighbor->isVisited){ if (DfsRecursiveHelper(graph, neighbor, destination) == 1){ return 1; } } } return 0; }

static int isAdjacent(Vertex* v1, Vertex* v2) { if (v1 == v2){ return 1; } for (int i = 0; i < v1->numNeighbors; ++i){ if (v1->neighbors[i] == v2) { return 1; } } return 0; }

static void createEdge(Vertex* v1, Vertex* v2) { v1->neighbors = realloc(v1->neighbors, sizeof(Vertex*) * (v1->numNeighbors + 1)); v2->neighbors = realloc(v2->neighbors, sizeof(Vertex*) * (v2->numNeighbors + 1)); v1->neighbors[v1->numNeighbors] = v2; v2->neighbors[v2->numNeighbors] = v1; ++(v1->numNeighbors); ++(v2->numNeighbors); }

int dfsRecursive(Graph* graph, Vertex* source, Vertex* destination) { clearVisited(graph); return DfsRecursiveHelper(graph, source, destination); }

int dfsIterative(Graph* graph, Vertex* source, Vertex* destination) { // FIXME: Implement return 0; }

int bfsIterative(Graph* graph, Vertex* source, Vertex* destination) { // FIXME: Implement return 0; }

typedef struct Edge Edge;

struct Edge { int i; int j; };

Edge* randomEdges(int numVertices, int numEdges) { assert(numVertices > 0); int maxEdges = numVertices * (numVertices - 1) / 2; assert(numEdges >= 0); assert(numEdges <= maxEdges); // Generate all possible edges Edge* edges = malloc(sizeof(Edge) * maxEdges); int k = 0; for (int i = 0; i < numVertices; ++i){ for (int j = i + 1; j< numVertices; ++j){ edges[k].i = i; edges[k].j = j; ++k; } }

// Shuffle edges for (int i = maxEdges - 1; i > 0; --i){ int j = rand() % (i + 1); Edge temp = edges[i]; edges[i] = edges[j]; edges[j] = temp; } // Take only the number of edges needed edges = realloc(edges, sizeof(Edge) * numEdges); return edges; }

Graph* randomGraph(int numVertices, int numEdges) { assert(numVertices > 0); assert(numEdges >= 0); assert(numEdges <= numVertices * (numVertices - 1) / 2); Graph* graph = malloc(sizeof(Graph)); graph->numVertices = numVertices; graph->numEdges = numEdges; graph->vertexSet = malloc(sizeof(Vertex) * numVertices); // Initialize vertices for (int i = 0; i < graph->numVertices; ++i){ Vertex* vertex =& graph->vertexSet[i]; vertex->label = i; vertex->isVisited = 0; vertex->numNeighbors = 0; vertex->neighbors = NULL; } // Randomly connect vertices Edge* edges = randomEdges(numVertices, numEdges); for (int i = 0; i < numEdges; ++i){ Vertex* v1 =& graph->vertexSet[edges[i].i]; Vertex* v2 =& graph->vertexSet[edges[i].j]; createEdge(v1, v2); } free(edges);

return graph; }

Graph* loadGraph(const char* fileName) { FILE* file = fopen(fileName, "r"); char buffer[512]; // Get the number of vertices fgets(buffer, sizeof buffer, file); int numVertices = (int) strtol(buffer, NULL, 10); Graph* graph = malloc(sizeof(Graph)); graph->numVertices = numVertices; graph->numEdges = 0; // Initialize vertices graph->vertexSet = malloc(sizeof(Vertex) * numVertices); for (int i = 0; i < numVertices; ++i){ Vertex* vertex =& graph->vertexSet[i]; vertex->isVisited = 0; vertex->label = i; vertex->neighbors = NULL; vertex->numNeighbors = 0; } // Create edges while (fgets(buffer, sizeof buffer, file) != NULL){ char* begin = buffer; char* end = NULL; // Get vertex int i = (int) strtol(begin, &end, 10); Vertex* vertex =& graph->vertexSet[i]; begin = end; // Create edges for (int i = (int) strtol(begin, &end, 10); end != begin; i = (int) strtol(begin, &end, 10)) { Vertex* neighbor = &graph->vertexSet[i]; if (!isAdjacent(vertex, neighbor)){ createEdge(vertex, neighbor); ++(graph->numEdges); } begin = end; } } fclose(file); return graph; }

void freeGraph(Graph* graph) { for (int i = 0; i < graph->numVertices; ++i){ free(graph->vertexSet[i].neighbors); } free(graph->vertexSet); free(graph); }

void printGraph(Graph* graph) { printf("Vertex count: %d ", graph->numVertices); printf("Edge count: %d ", graph->numEdges); for (int i = 0; i < graph->numVertices; ++i){ Vertex* vertex =& graph->vertexSet[i]; printf("%d :", vertex->label); for (int j = 0; j < vertex->numNeighbors; ++j){ printf(" %d", vertex->neighbors[j]->label); } printf(" "); } }

graphTests.c

#include "cutest/CuTest.h" #include "deque.h" #include "graph.h" #include #include #include

void testDfsIterative(CuTest* test) { printf("--- testing dfsIterative --- "); const int N = 10; for (int testNum = 0; testNum < N; ++testNum{ Graph* g = randomGraph(N, N - 1); printf(" Graph %d --- ", testNum); printGraph(g); for (int i = 0; i < g->numVertices; ++i){ for (int j = i; j < g->numVertices; ++j){ Vertex* source = &g->vertexSet[i]; Vertex* destination = &g->vertexSet[j]; int expected = dfsRecursive(g, source, destination); int actual = dfsIterative(g, source, destination); CuAssertIntEquals(test, expected, actual); } } freeGraph(g); } printf(" "); }

void testBfsIterative(CuTest* test) { printf("--- testing bfsIterative --- "); const int N = 10; for (int testNum = 0; testNum < N; ++testNum){ Graph* g = randomGraph(N, N - 1); printf(" Graph %d --- ", testNum); printGraph(g); for (int i = 0; i < g->numVertices; ++i){ for (int j = i; j < g->numVertices; ++j){ Vertex* source = &g->vertexSet[i]; Vertex* destination = &g->vertexSet[j]; int expected = dfsRecursive(g, source, destination); int actual = bfsIterative(g, source, destination); CuAssertIntEquals(test, expected, actual); } } freeGraph(g); } printf(" "); }

CuSuite* getGraphTestSuite() { CuSuite* suite = CuSuiteNew(); SUITE_ADD_TEST(suite, testDfsIterative); SUITE_ADD_TEST(suite, testBfsIterative); return suite; }

main.c

#include "graph.h"

#include #include #include

#define NUM_GRAPHS 3

int main() { // Load graphs Graph* graphs[NUM_GRAPHS]; char nameBuffer[256]; for (int i = 0; i < NUM_GRAPHS; ++i){ sprintf(nameBuffer, "graph%d.txt", i + 1); graphs[i] = loadGraph(nameBuffer); } // Run DFS and BFS on each graph for (int graphNum = 0; graphNum < NUM_GRAPHS; ++graphNum){ Graph* g = graphs[graphNum]; printf(" Graph %d (graph%d.txt) --- ", graphNum + 1, graphNum + 1); printGraph(g); printf(" "); for (int i = 0; i < g->numVertices; ++i){ for (int j = i; j < g->numVertices; ++j){ Vertex* v1 = &g->vertexSet[i]; Vertex* v2 = &g->vertexSet[j]; printf("%d ... %d : ", v1->label, v2->label); int dfs = dfsIterative(g, v1, v2); int bfs = bfsIterative(g, v1, v2); printf("DFS %s, BFS %s ", (dfs == 1) ? "path" : "no path", (bfs == 1) ? "path" : "no path"); } } freeGraph(g); } return 0; }

tests.c

#include "cutest/CuTest.h"

#include

CuSuite* getDequeTestSuite(); CuSuite* getGraphTestSuite();

int main() { CuSuite* suite = CuSuiteNew(); CuSuiteConsume(suite, getDequeTestSuite()); CuSuiteConsume(suite, getGraphTestSuite()); CuSuiteRun(suite); CuString* output = CuStringNew(); CuSuiteSummary(suite, output); CuSuiteDetails(suite, output); printf("%s ", output->buffer); CuStringDelete(output); CuSuiteDelete(suite); return 0; }

graph1.txt

10 0 2 1 1 9 2 0 2 0 1 8 3 6 4 6 5 9 6 3 7 4 7 6 8 2 9 1 5

graph2.txt

10 0 4 5 1 7 9 6 3 2 8 1 2 5 0 7 6 4 9 8 3 2 7 1 9 6 3 4 0 8 5 3 2 9 6 4 7 0 5 1 8 4 0 7 2 8 9 1 3 6 5 5 0 1 9 7 6 8 4 3 2 6 2 9 8 7 1 3 5 0 4 7 2 4 6 1 0 9 5 3 8 8 6 9 4 5 2 7 0 1 3 9 2 6 8 3 7 4 0 5 1

graph3.txt

10 0 7 8 1 5 2 2 1 3 3 2 8 4 5 5 4 1 6 8 7 9 0 8 0 6 3 9 7