Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#define PATH_MAX 4096
int edges_visited;
struct bfs {
struct AdjList* path;
struct Node* next;
};
//struct bfs paths[1000];
struct AdjList {
int value;
int mark;
struct Node* list;
};
struct Node {
struct AdjList* vertex;
struct Node* next;
};
struct Queue {
};
typedef struct AdjList AdjList;
typedef struct Node Node;
// creates a new vertex and return pointer to it
AdjList* new_vertex(int value, AdjList* graph[]) {
AdjList* vertex = (AdjList*)malloc(sizeof(AdjList));
vertex->value = value;
vertex->list = 0;
graph[value] = vertex;
return vertex;
}
// connect vertex a to vertex b
// by adding b to a's list
void do_connect(AdjList* a, AdjList* b) {
Node* node = (Node*)malloc(sizeof(Node));
node->vertex = b;
node->next = a->list;
a->list = node;
}
// connects a to b and b to a
void connect(AdjList* a, AdjList* b) {
do_connect (a, b);
//do_connect (b, a);
}
// visit function
int visit(AdjList* vertex, int goal) {
if (vertex->value == goal) {
printf ("%d ", vertex->value);
//clock_t end = clock();
//time_spent += (double)(end - begin) / CLOCKS_PER_SEC;
//printf("Time elpased is %f seconds", time_spent);
return 1;
//exit(0);
}
printf ("%d --" ,vertex->value);
//return 0;
}
int do_bfs(AdjList *vertex, int* count, int goal) {
Node *initialQueue, *front, *rear, *p, *temp;
//struct bfs paths[1000];
///int path_i = 0;
//paths[path_i].path = vertex;
AdjList *w;
// mark vertex with count
vertex->mark = ++(*count);
visit (vertex, goal);
// initialize queue with a vertex
initialQueue = (Node*)malloc(sizeof(Node));
initialQueue->vertex = vertex;
initialQueue->next = 0;
front = initialQueue;
rear = initialQueue;
// while queue is not empty
while (front != 0) {
// for vertex w in V adjacent to the front vertex
p = front->vertex->list;
while (p != 0) {
w = p->vertex;
// if w is marked with 0
if (w->mark == 0) {
// paths[path_i].next = w->list;
// path_i++;
Node* nextQueue;
// count = count + 1, mark w with count
edges_visited = edges_visited+1;
w->mark = ++(*count);
int is_goal = visit (w,goal);
if(is_goal == 1){
return path_i;
}
// add w to queue
nextQueue = (Node*)malloc(sizeof(Node));
nextQueue->vertex = w;
nextQueue->next = 0;
rear->next = nextQueue;
rear = nextQueue;
}
p = p->next;
//paths[path_i].path = p->vertex;
}
// remove front vertex from queue
temp = front;
front = front->next;
free (temp);
}
}
int bfs(AdjList *graph[], int goal, int no_vertices) {
int i;
int count = 0;
// set all to unvisited
for (i = 0; i < no_vertices; i ++) {
graph[i]->mark = 0;
}
// do bfs for each vertex
i = do_bfs (graph[1], &count, goal);
return i;
}
int main(int argc, char *argv[]) {
char c[1000];
FILE *fptr;
int is_bfs = 0;
int is_dfs = 0;
int is_extended = 0;
int goal_vertex;
char *graph_file;
for(int i = 0; i< argc; i++){
if (strcmp("-dfs", argv[i]) == 0) {
is_dfs = 1;
}
if (strcmp("-bfs", argv[i]) == 0) {
is_bfs = 1;
}
if (strcmp("-dest", argv[i]) == 0) {
goal_vertex = atoi(argv[i+1]);
}
if (strcmp("-e", argv[i]) == 0) {
is_extended = 1;
}
}
graph_file = argv[argc-1];
//printf("\n Graph file name is: %s", graph_file);
//printf("\n file path name is: %s", file_string);
if ((fptr = fopen(graph_file, "r")) == NULL)
{
printf("Error! opening file");
// Program exits if file pointer returns NULL.
exit(1);
}
fscanf(fptr, "%[^\n]",c);
//printf("\n %s",c);
int no_vertices = atoi(c);
no_vertices = no_vertices+1;
AdjList *graph[no_vertices];
for(int i = 0; i<=no_vertices; i++){
new_vertex(i, graph);
}
const size_t line_size = 300;
char* line = malloc(line_size);
for(int i = 0; i<no_vertices; i++){
//fscanf(fptr,"%[^\n]",c);
//printf("\n %s", c);
fgets(line, line_size, fptr);
//printf(line);
char* token = strtok(line, " ");
int start_vertex = atoi(token);
while (token){
//printf("token: %s\n", token);
token = strtok(NULL, " ");
if(token != NULL){
int dest_vertex = atoi(token);
connect(graph[start_vertex], graph[dest_vertex]);
}
}
}
//printGraph(graph, no_vertices);
double time_spent = 0.0;
clock_t start,end;
if (is_dfs == 1){
// do depth first search
printf ("path: ");
start = clock();
dfs (graph, goal_vertex, no_vertices);
end = clock();
}
int path_i = 0;
if (is_bfs == 1) {
// do breadth first search
printf ("\n\n");
start = clock();
printf ("path: ");
path_i = bfs (graph, goal_vertex, no_vertices);
end = clock();
}
time_spent = ((double) (end-start))/CLOCKS_PER_SEC;
double time_spent_ms = time_spent * 1000000;
printf("\nEdges: %d", edges_visited);
printf("\nExecution time: %f ms \n", time_spent_ms);
// printf("\n%d", path_i);
// printf("\n%d",paths[0].path->value);
fflush( stdout );
}
