Prerequisites You are provided with a complete circular linked-list deque implem
ID: 3846417 • 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
DFS ITERATIVE
For Implementing Iterative DFS, Implementaion will be similar to BFS. But in BFS we use Queue (Basically use your deque to behave as queue) and in DFS implementation we will going to use Stack (Using same deque data structure).
I am going to give you hint here how to do that as your code is not well written and idented and I am unable to run it.
So now you are given with dfsIterative(graph, source, destination)
So logic goes like following
1.Initially mark all vertices as not visited, make a boolean array having all values false.
2.Create an empty stack
3.Push the current source node "source"
4. while stack is not empty repeat steps 5 to 7
5. stack.pop(), basically pop a vertex from stack and print it.
6. Now we have to check if stack contains same vertex twice. So we need to print the popped item only if it is not visited i.e, check your boolean array if it is visited, if yes mark it as true otherwise skip it.
7. Get all adjacent vertices of the popped vertex s If a adjacent has not been visited, then push it to the stack.
So if vertex is not visited add it to stack and go to step 4 till stack is not empty.
BFS ITERATIVE
Now for bfs you have to follow same steps as above except you have to manipulate your deque DS to behave as stack. If your DS logic is not clear I can write those functions for you but I need running code for that.