diff options
Diffstat (limited to '')
| -rw-r--r-- | src/cycle_detection.c | 27 | ||||
| -rw-r--r-- | src/graph.c | 32 | ||||
| -rw-r--r-- | src/vector.c | 2 |
3 files changed, 32 insertions, 29 deletions
diff --git a/src/cycle_detection.c b/src/cycle_detection.c index d232d89..8dd5691 100644 --- a/src/cycle_detection.c +++ b/src/cycle_detection.c @@ -9,12 +9,19 @@ void cycle_detection(Graph *g) { int n = g->num_vertices; int *indegree = calloc(n, sizeof(int)); + if (!indegree) { + fprintf(stderr, "Memory allocation failed: could not create list.\n"); + free(indegree); + return; + } + 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"); @@ -22,7 +29,7 @@ void cycle_detection(Graph *g) { linked_list_delete(queue); return; } - + // Compute in-degrees for (int i = 0; i < n; i++) { for (int j = 0; j < (int)g->vertices[i].out_neighbours->size; j++) { @@ -30,19 +37,19 @@ void cycle_detection(Graph *g) { indegree[neighbor]++; } } - + // Add all vertices with no incoming edges for (int i = 0; i < n; i++) { - if (!indegree[i]) { + if (indegree[i] == 0) { linked_list_append(queue, (void *)(intptr_t)i); } } - + // Process queue for topological sort - while (queue->size) { + while (queue->size != 0) { int top = (int)(intptr_t)linked_list_popfront(queue); vector_push(list, (void *)(intptr_t)top); - + // 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]; @@ -52,11 +59,11 @@ void cycle_detection(Graph *g) { } } } - + // Output result - if ((int)list->size != n) { + 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, ", "); @@ -64,7 +71,7 @@ void cycle_detection(Graph *g) { } fprintf(stdout, "\n"); } - + linked_list_delete(queue); vector_delete(list); free(indegree); diff --git a/src/graph.c b/src/graph.c index 44ce400..8c19a19 100644 --- a/src/graph.c +++ b/src/graph.c @@ -20,7 +20,7 @@ Graph *graph_new(int n) { graph->num_edges = 0; graph->num_vertices = n; - + for (int i = 0; i < n; i++) { graph->vertices[i].id = i; graph->vertices[i].out_neighbours = vector_new(); @@ -47,46 +47,42 @@ Graph *graph_read(const char *filename) { FILE *file = fopen(filename, "r"); if (!file) return NULL; - - char line[1024]; + + char line[4096]; + if (!fgets(line, sizeof(line), file)) { fclose(file); return NULL; } - + int n = atoi(line); if (n <= 0) { fclose(file); return NULL; } - + Graph *g = graph_new(n); if (!g) { fclose(file); return NULL; } - - for (int i = 0; i < n; i++) { + + for (int row = 0; row < n; row++) { if (!fgets(line, sizeof(line), file)) { - fprintf(stderr, "Error: Could not read row %d\n", i); fclose(file); return g; } - - int j = 0; + int col = 0; - while (col < n && line[j] != '\0' && line[j] != '\n') { - if (line[j] == '1') { - graph_add_edge(g, i, col); - col++; - } else if (line[j] == '0') { + for (int i = 0; line[i] != EOF && line[i] != '\n'; i++) { + if (line[i] == '0' || line[i] == '1') { + if (line[i] == '1') + graph_add_edge(g, row, col); col++; } - // skip any other characters - j++; } } - + fclose(file); return g; } diff --git a/src/vector.c b/src/vector.c index 40dc92c..9884957 100644 --- a/src/vector.c +++ b/src/vector.c @@ -31,7 +31,7 @@ void vector_push(Vector *v, void *element) { } void *vector_pop(Vector *v) { - if (!v->size) return NULL; + if (v->size == 0) return NULL; return v->data[--v->size]; } |