From 5e27a37c6ce0c8b98951b3ecc9308961b47b955a Mon Sep 17 00:00:00 2001
From: Mikkel Thestrup <mithe24@student.sdu.dk>
Date: Thu, 4 Dec 2025 18:44:09 +0100
Subject: program using vectors instead of linked list in graphs

---
 src/cycle_detection.c | 49 ++++++++++++++++++++-----------------------------
 1 file changed, 20 insertions(+), 29 deletions(-)

(limited to 'src')

diff --git a/src/cycle_detection.c b/src/cycle_detection.c
index 3aa8b74..d232d89 100644
--- a/src/cycle_detection.c
+++ b/src/cycle_detection.c
@@ -8,18 +8,13 @@
 
 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");
@@ -29,43 +24,39 @@ void cycle_detection(Graph *g) {
     }
     
     // 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;
+        for (int j = 0; j < (int)g->vertices[i].out_neighbours->size; j++) {
+            int neighbor = *(int *)g->vertices[i].out_neighbours->data[j];
+            indegree[neighbor]++;
         }
     }
     
     // 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). */
+    for (int i = 0; i < n; i++) {
+        if (!indegree[i]) {
             linked_list_append(queue, (void *)(intptr_t)i);
+        }
+    }
     
+    // Process queue for topological sort
     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;
+        
+        // Process all neighbors of current vertex
+        for (int j = 0; j < (int)g->vertices[top].out_neighbours->size; j++) {
+            int neighbor = *(int *)g->vertices[top].out_neighbours->data[j];
+            indegree[neighbor]--;
+            if (!indegree[neighbor]) {
+                linked_list_append(queue, (void *)(intptr_t)neighbor);
+            }
         }
     }
     
-    if ((int)list->size != n)
+    // Output result
+    if ((int)list->size != n) {
         fprintf(stdout, "CYCLE DETECTED!\n");
-    else {
+    } else {
         for (int i = 0; i < (int)list->size; i++) {
             if (i != 0)
                 fprintf(stdout, ", ");
@@ -73,7 +64,7 @@ void cycle_detection(Graph *g) {
         }
         fprintf(stdout, "\n");
     }
-
+    
     linked_list_delete(queue);
     vector_delete(list);
     free(indegree);
-- 
cgit v1.2.3-70-g09d2