Refine .gitignore some more.
[Algorithmic_C.git] / TP7 / exo1 / graphs.c
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #include "graphs.h"
5
6 void init_adj_matrix(int adj_matrix[num_nodes][num_nodes]) {
7 for (unsigned int i = 0; i < num_nodes; i++) {
8 for (unsigned int j = 0; j < num_nodes; j++) {
9 adj_matrix[i][j] = 0;
10 }
11 }
12 }
13
14 unsigned int num_successors_adj_matrix(unsigned int node, int adj_matrix[num_nodes][num_nodes]) {
15 unsigned int num_successors = 0;
16
17 for (unsigned int i = 0; i < num_nodes; i++) {
18 if (adj_matrix[node][i] == 1) {
19 num_successors++;
20 }
21 }
22 return num_successors;
23 }
24
25 unsigned int num_successors_adj_list(unsigned int node, succ_list_t* nodes[num_nodes]) {
26 struct list_head* list_iter = NULL;
27 unsigned int num_successors = 0;
28
29 if (!list_empty(&nodes[node]->list)) {
30 list_for_each(list_iter, &nodes[node]->list) {
31 num_successors++;
32 }
33 }
34 return num_successors;
35 }
36
37 bool has_successor_adj_matrix(unsigned int node, int adj_matrix[num_nodes][num_nodes]) {
38
39 for (unsigned int i = 0; i < num_nodes; i++) {
40 if (adj_matrix[node][i] == 1) {
41 return true;
42 }
43 }
44 return false;
45 }
46
47 void add_adj_list_cell(unsigned int node, bool is_valued, int value, succ_list_t* successors_list) {
48 succ_list_t* list_cell = (succ_list_t*)malloc(sizeof(succ_list_t));
49 if (!list_cell) {
50 exit(EXIT_FAILURE);
51 }
52
53 list_cell->num_node = node;
54 if (is_valued) list_cell->val = value;
55 list_add_tail(&(list_cell->list), &(successors_list->list));
56 }
57
58 void free_adj_list(succ_list_t* successors_list) {
59 succ_list_t* list_iter = NULL;
60
61 while (!list_empty(&successors_list->list)) {
62 list_iter = list_entry(successors_list->list.next, succ_list_t, list);
63 list_del(&(list_iter->list));
64 free(list_iter);
65 }
66 }
67
68 void build_adj_list(unsigned int node, int adj_matrix[num_nodes][num_nodes], succ_list_t* successors_list) {
69 unsigned int num_successors = 0;
70
71 num_successors = num_successors_adj_matrix(node, adj_matrix);
72
73 for (unsigned int i = 0; i < num_successors && num_successors != 0; i++) {
74 if (adj_matrix[node][i] == 1) {
75 add_adj_list_cell(node, false, 0, successors_list);
76 }
77 }
78 }
79
80 void convert_adj_matrix_to_adj_lists(int adj_matrix[num_nodes][num_nodes], succ_list_t* nodes[num_nodes]) {
81 succ_list_t succ_list_array[num_nodes];
82
83 for (unsigned int i = 0; i < num_nodes; i++) {
84 //init num_nodes linked list
85 INIT_LIST_HEAD(&(succ_list_array[i].list));
86 //NOTE: the nodes array is NOT the head of the list, they point to the list head
87 build_adj_list(i, adj_matrix, &succ_list_array[i]);
88 //if list_array[i] not empty, then nodes[i] = &list_array[i] else = NULL
89 }
90 }
91
92 void display_adj_matrix(int adj_matrix[num_nodes][num_nodes]) {
93 for (unsigned int i = 0; i < num_nodes; i++) {
94 for (unsigned int j = 0; j < num_nodes; j++) {
95 printf("%d ", adj_matrix[i][j]);
96 }
97 printf("\n");
98 }
99 }
100
101 void display_adj_lists(succ_list_t* nodes[num_nodes]) {
102 succ_list_t* list_iter = NULL;
103
104 for (unsigned int i = 0; i < num_nodes; i++) {
105 list_for_each_entry(list_iter, &nodes[i]->list, list) {
106 printf("%d ", list_iter->num_node);
107 }
108 printf("\n");
109 }
110 }