Commit | Line | Data |
---|---|---|
fa5222dc JB |
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 | } |