diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/2-1-breadth-first-search.c | 160 |
1 files changed, 160 insertions, 0 deletions
diff --git a/src/2-1-breadth-first-search.c b/src/2-1-breadth-first-search.c new file mode 100644 index 0000000..0b232c5 --- /dev/null +++ b/src/2-1-breadth-first-search.c @@ -0,0 +1,160 @@ +#include <algolib.c> +#include <stdbool.h> +#include <stdio.h> +#include <vectorlib.c> + +#define PROJECT_NAME "algorithms-breadth first search" + +typedef struct DATASET { + char* title; + char** cast; +} DATASET; + +void bfs(BFS_Graph* graph, char** argv) +{ + printf("\nsearching %s - %s\n",argv[1],argv[2]); + BFS_Node* start = BFS_Gr_SetStart(graph, argv[1]); + BFS_Node* end = BFS_Gr_SetEnd(graph, argv[2]); + + if (!start || !end) + return; + + BFS_Node* queue[200]; + int queue_len = 0; + + start->searched = true; + queue[++queue_len] = start; + + printf("\n"); + while (queue_len > 0) { + BFS_Node* current = queue[queue_len--]; + if (current == end) { + printf("found %s\n", current->value); + break; + } + for (int i = 0; i < 200; i++) { + if (current->edges[i] != NULL) { + BFS_Node* neighbor = current->edges[i]; + if (neighbor->searched == false) { + neighbor->searched = true; + neighbor->parent = current; + queue[++queue_len] = neighbor; + } + } + } + } + + BFS_Node* path[200]; + int path_len = 0; + + path[path_len++] = end; + BFS_Node* next = end->parent; + + while (next != NULL) { + path[path_len++] = next; + if (next->parent != NULL) { + next = next->parent; + } else { + break; + } + } + + for (int i = path_len - 1; i >= 0; i--) { + printf("%s", path[i]->value); + if (i != 0) + printf(" --> "); + } +} + +int main(int argc, char** argv) +{ + BFS_Graph* graph = BFS_Graph_Constructor(); + DATASET** movies = (DATASET**)malloc(sizeof(DATASET*) * 5); + for (int i = 0; i < 5; i++) { + movies[i] = (DATASET*)malloc(sizeof(DATASET)); + movies[i]->cast = (char**)malloc(sizeof(char*) * 3); + } + + // cant be bothered to parse or add a lib to parse json. + // just doing it manually + movies[0]->title = "Me!"; + movies[0]->cast[0] = "garry"; + movies[0]->cast[1] = "jesus"; + movies[0]->cast[2] = "niles"; + + movies[1]->title = "That Guy."; + movies[1]->cast[0] = "garry"; + movies[1]->cast[1] = "neilman"; + movies[1]->cast[2] = NULL; + + movies[2]->title = "Some Stuff"; + movies[2]->cast[0] = "cole"; + movies[2]->cast[1] = "faux"; + movies[2]->cast[2] = NULL; + + movies[3]->title = "dogs"; + movies[3]->cast[0] = "cole"; + movies[3]->cast[1] = "niles"; + movies[3]->cast[2] = "jales"; + + movies[4]->title = "Cats"; + movies[4]->cast[0] = "james"; + movies[4]->cast[1] = "jesus"; + movies[4]->cast[2] = NULL; + + for (int i = 0; i < 5; i++) { + char* movie = movies[i]->title; + BFS_Node* movieNode = BFS_Constructor(movie); + BFS_Gr_AddNode(graph, movieNode); + for (int j = 0; j < 3; j++) { + char* actor = movies[i]->cast[j]; + if (actor == NULL) + break; + + BFS_Node* actorNode = BFS_Gr_GetNode(graph, actor); + if (actorNode == NULL) { + actorNode = BFS_Constructor(actor); + } + BFS_Gr_AddNode(graph, actorNode); + BFS_AddEdge(movieNode, actorNode); + } + } + + printf("nodes::\n"); + for (int i = 0; i < 200; i++) { + if (graph->nodes[i] != NULL) { + printf("%s\n", graph->nodes[i]->value); + } + } + + printf("\ngraph::\n"); + for (int i = 0; i < 200; i++) { + if (graph->graph[i]->node != NULL) { + printf("%s\n", graph->graph[i]->node->value); + for (int j = 0; j < 20; j++) { + if (graph->graph[i]->node->edges[j] != NULL) { + printf(" %s\n", graph->graph[i]->node->edges[j]->value); + } + } + } + } + + if (argv[1] && argv[2]) { + bfs(graph, argv); + } + + BFS_FreeGraph(graph); + + for (int i = 0; i < 5; i++) { + free(movies[i]->cast); + free(movies[i]); + } + free(movies); + + printf("\nEND\n"); +} + +/* Challanges + * + * make a prettier visualization + */ |