Added cycle_detection()

1 files changed, 80 insertions, 0 deletions

diff --git a/src/cycle_detection.c b/src/cycle_detection.c
new file mode 100644
index 0000000..3aa8b74
--- /dev/null
+++ b/src/cycle_detection.c
@@ -0,0 +1,80 @@
+#include "cycle_detection.h"
+#include "graph.h"
+#include "linked_list.h"
+#include "vector.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+
+void cycle_detection(Graph *g) {
+    int n = g->num_vertices;
+
+    /* Use `calloc()` to allocate memory
+     * initialized to zero */
+    int *indegree = calloc(n, sizeof(int));
+
+    LinkedList *queue = linked_list_new();
+    if (!queue) {
+        fprintf(stderr, "Memory allocation failed: could not create queue.\n");
+        free(indegree);
+        return;
+    }
+
+    Vector *list = vector_new();
+    if (!list) {
+        fprintf(stderr, "Memory allocation failed: could not create vector.\n");
+        free(indegree);
+        linked_list_delete(queue);
+        return;
+    }
+    
+    // Compute in-degrees
+    LinkedListNode *node;
+    for (int i = 0; i < n; i++) {
+        node = g->vertices[i].out_neighbours->head;
+        while (node) {
+            indegree[((Vertex *)node->data)->id]++;
+            node = node->next;
+        }
+    }
+    
+    // Add all vertices with no incoming edges
+    for (int i = 0; i < n; i++)
+        if (!indegree[i])
+            /* Use `intptr_t` to safely store the int as a pointer.
+             * `intptr_t` is guaranteed to be pointer-sized
+             * (8 bytes on 64-bit systems). */
+            linked_list_append(queue, (void *)(intptr_t)i);
+    
+    while (queue->size) {
+        int top = (int)(intptr_t)linked_list_popfront(queue);
+        vector_push(list, (void *)(intptr_t)top);
+
+        /* Walk the linked list `out_neighbours`
+         * for the graph vertex */
+        node = g->vertices[top].out_neighbours->head;
+        Vertex *v;
+        while (node) {
+            v = (Vertex *)node->data;
+            indegree[v->id]--;
+            if (!indegree[v->id])
+                linked_list_append(queue, (void *)(intptr_t)v->id);
+            node = node->next;
+        }
+    }
+    
+    if ((int)list->size != n)
+        fprintf(stdout, "CYCLE DETECTED!\n");
+    else {
+        for (int i = 0; i < (int)list->size; i++) {
+            if (i != 0)
+                fprintf(stdout, ", ");
+            fprintf(stdout, "%d", (int)(intptr_t)vector_get(list, i));
+        }
+        fprintf(stdout, "\n");
+    }
+
+    linked_list_delete(queue);
+    vector_delete(list);
+    free(indegree);
+}