Push the WIP graphs handling code

[Algorithmic_C.git] / TP7 / exo1 / graphs.c

diff --git a/TP7/exo1/graphs.c b/TP7/exo1/graphs.c
new file mode 100644 (file)
index 0000000..4347350
--- /dev/null
+++ b/TP7/exo1/graphs.c
@@ -0,0 +1,110 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "graphs.h"
+
+void init_adj_matrix(int adj_matrix[num_nodes][num_nodes]) {
+    for (unsigned int i = 0; i < num_nodes; i++) {
+        for (unsigned int j = 0; j < num_nodes; j++) {
+            adj_matrix[i][j] = 0;
+        }
+    }
+}
+
+unsigned int num_successors_adj_matrix(unsigned int node, int adj_matrix[num_nodes][num_nodes]) {
+    unsigned int num_successors = 0;
+
+    for (unsigned int i = 0; i < num_nodes; i++) {
+        if (adj_matrix[node][i] == 1) {
+            num_successors++;
+        }
+    }
+    return num_successors;
+}
+
+unsigned int num_successors_adj_list(unsigned int node, succ_list_t* nodes[num_nodes]) {
+    struct list_head* list_iter = NULL;
+    unsigned int num_successors = 0;
+
+    if (!list_empty(&nodes[node]->list)) {
+        list_for_each(list_iter, &nodes[node]->list) {
+            num_successors++;
+        }
+    }
+    return num_successors;
+}
+
+bool has_successor_adj_matrix(unsigned int node, int adj_matrix[num_nodes][num_nodes]) {
+
+    for (unsigned int i = 0; i < num_nodes; i++) {
+        if (adj_matrix[node][i] == 1) {
+            return true;
+        }
+    }
+    return false;
+}
+
+void add_adj_list_cell(unsigned int node, bool is_valued, int value, succ_list_t* successors_list) {
+    succ_list_t* list_cell = (succ_list_t*)malloc(sizeof(succ_list_t));
+    if (!list_cell) {
+        exit(EXIT_FAILURE);
+    }
+
+    list_cell->num_node = node;
+    if (is_valued) list_cell->val = value;
+    list_add_tail(&(list_cell->list), &(successors_list->list));
+}
+
+void free_adj_list(succ_list_t* successors_list) {
+     succ_list_t* list_iter = NULL;
+
+     while (!list_empty(&successors_list->list)) {
+         list_iter = list_entry(successors_list->list.next, succ_list_t, list);
+         list_del(&(list_iter->list));
+         free(list_iter);
+     }
+}
+
+void build_adj_list(unsigned int node, int adj_matrix[num_nodes][num_nodes], succ_list_t* successors_list) {
+    unsigned int num_successors = 0;
+
+    num_successors = num_successors_adj_matrix(node, adj_matrix);
+
+    for (unsigned int i = 0; i < num_successors && num_successors != 0; i++) {
+        if (adj_matrix[node][i] == 1) {
+            add_adj_list_cell(node, false, 0, successors_list);
+        }
+    }
+}
+
+void convert_adj_matrix_to_adj_lists(int adj_matrix[num_nodes][num_nodes], succ_list_t* nodes[num_nodes]) {
+    succ_list_t succ_list_array[num_nodes];
+
+    for (unsigned int i = 0; i < num_nodes; i++) {
+        //init num_nodes linked list
+        INIT_LIST_HEAD(&(succ_list_array[i].list));
+        //NOTE: the nodes array is NOT the head of the list, they point to the list head
+        build_adj_list(i, adj_matrix, &succ_list_array[i]);
+        //if list_array[i] not empty, then nodes[i] = &list_array[i] else = NULL
+    }
+}
+
+void display_adj_matrix(int adj_matrix[num_nodes][num_nodes]) {
+    for (unsigned int i = 0; i < num_nodes; i++) {
+        for (unsigned int j = 0; j < num_nodes; j++) {
+            printf("%d     ", adj_matrix[i][j]);
+        }
+        printf("\n");
+    }
+}
+
+void display_adj_lists(succ_list_t* nodes[num_nodes]) {
+    succ_list_t* list_iter = NULL;
+
+    for (unsigned int i = 0; i < num_nodes; i++) {
+        list_for_each_entry(list_iter, &nodes[i]->list, list) {
+            printf("%d     ", list_iter->num_node);
+        }
+        printf("\n");
+    }
+}