Prerequisites You are provided with a complete circular linked-list deque implem
ID: 3846591 • Letter: P
Question
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 struct’s 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 <setjmp.h>
#include <stdarg.h>
#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 <assert.h>
#include <setjmp.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#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] = '';
}
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] = '';
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] = '';
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 <stdlib.h>
#include <assert.h>
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 <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
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 <stdlib.h>
#include <assert.h>
#include <stdio.h>
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 <string.h>
#include <stdio.h>
#include <assert.h>
#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 <stdio.h>
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
Explanation / Answer
note: i have included answer for that 5 questions and graph.c file
answers.txt
1. How is the graph stored in the provided code? Is it represented as an adjacency matrix or list?
The graph utilizes an edge list.
2. Which of the 3 graphs are connected? How can you tell?
Graph 2 Graph 3 are both connected since all of their vertices are reachable, while in graph 1 some of
the vertices are not reachable.
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?
It would not change the results to simply reverse the direction since the paths between the vertices are not
dependent on the direction. If you were to change the graph to be directed it could change the results since
some paths would be single direction edges.
4. What are some pros and cons of DFS vs BFS? When would you use one over the other?
DFS
Pros: Uses less memory and has the possibility of finding the solution faster than BFS.
Cons: Has a potential of never getting stuck never finding the solution. It also can require a lot of
backtracking.
BFS
Pros: Will always find a solution since it checks all paths at once.
Cons: Requires much more memory than the DFS since it checks all possible paths at once.
5. What is the Big O execution time to determine if a vertex is reachable from another vertex?
The complexity is O(E+V), where E is the number of edges and V is the number of vertices.
graph.c
#include "graph.h"
#include "deque.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
/**
* Clears isVisited in all nodes in the graph.
* @param graph
*/
static void clearVisited(Graph* graph)
{
for (int i = 0; i < graph->numVertices; ++i)
{
graph->vertexSet[i].isVisited = 0;
}
}
/**
* Recursive helper function for DfsRecursive. Determines if there is a path
* from the given vertex to the destination using a recursive depth-first
* search.
* @param graph
* @param vertex
* @param destination
* @return 1 if there is a path, 0 otherwise.
*/
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;
}
/**
* Determines if an edge (v1, v2) exists.
* @param v1
* @param v2
* @return 1 if the edge exists, 0 otherwise.
*/
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;
}
/**
* Connects two vertices by adding each other to their neighbors lists.
* @param v1
* @param v2
*/
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);
}
/**
* Determines if there is a path from the source to the destination using a
* recursive depth-first search starting at the source.
*
* You can use this function to test the correctness of the others.
*
* @param graph
* @param source
* @param destination
* @return 1 if there is a path, 0 otherwise.
*/
int dfsRecursive(Graph* graph, Vertex* source, Vertex* destination)
{
clearVisited(graph);
return DfsRecursiveHelper(graph, source, destination);
}
/**
* Determines if there is a path from the source to the destination using an
* iterative depth-first search starting at the source.
*
* Remember to call clearVisited() before starting the search.
*
* @param graph
* @param source
* @param destination
* @return 1 if there is a path, 0 otherwise.
*/
int dfsIterative(Graph* graph, Vertex* source, Vertex* destination)
{
struct Deque *deque = dequeNew();
clearVisited(graph);
dequePushBack(deque, source);
while(!dequeIsEmpty(deque))
{
Vertex* vertex = dequeFront(deque);
vertex->isVisited =1;
dequePopFront(deque);
for(int i = 0; i<vertex->numNeighbors; i++)
{
if(!vertex->neighbors[i]->isVisited)
{
dequePushFront(deque, vertex->neighbors[i]);
}
}
if(vertex == destination)
{
return 1;
}
}
dequeDelete(deque);
return 0;
}
/**
* Determines if there is a path from the source to the destination using an
* iterative breadth-first search starting at the source.
*
* Remember to call clearVisited() before starting the search.
*
* @param graph
* @param source
* @param destination
* @return 1 if there is a path, 0 otherwise.
*/
int bfsIterative(Graph* graph, Vertex* source, Vertex* destination)
{
int i;
clearVisited(graph);
if(source == destination) {
return 1;
}
Deque *queue = dequeNew();
dequePushBack(queue, source);
while(!dequeIsEmpty(queue)) {
Vertex *cur = dequeFront(queue);
dequePopFront(queue);
cur->isVisited = 1;
if(cur == destination) {
return 1;
}
for(i = 0; i<cur->numNeighbors; i++) {
if(!(cur->neighbors[i]->isVisited)) {
dequePushBack(queue, cur->neighbors[i]);
}
}
}
dequeDelete(queue);
return 0;
}
typedef struct Edge Edge;
struct Edge
{
int i;
int j;
};
/**
* Generates a set of random unique edges of size numEdges sampled from the
* set of all possible edges.
* @param numVertices
* @param numEdges
* @return An array of numEdges edges.
*/
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;
}
/**
* Given a number of vertices and a number of edges, generates a graph
* connecting random pairs of vertices. The edges are unique, and thus their is
* a maximum number of edges allowed in proportion to the number of vertices.
* numEdges must be in the interval [0, numVertices * (numVertices + 1) / 2].
* @param numVertices
* @param numEdges
* @return
*/
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;
}
/**
* Loads a graph from the given file. The file's first line must be the number
* of vertices in the graph and each consecutive line must be a list of numbers
* separated by spaces. The first number is the next vertex and the following
* numbers are its neighbors.
* @param fileName
* @return
*/
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;
}
/**
* Frees all memory allocated for a graph and the graph itself.
* @param graph
*/
void freeGraph(Graph* graph)
{
for (int i = 0; i < graph->numVertices; ++i)
{
free(graph->vertexSet[i].neighbors);
}
free(graph->vertexSet);
free(graph);
}
/**
* Prints the vertex count, edge count, and adjacency list for each vertex.
* @param 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(" ");
}
}