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
++) {
14 unsigned int num_successors_adj_matrix(unsigned int node
, int adj_matrix
[num_nodes
][num_nodes
]) {
15 unsigned int num_successors
= 0;
17 for (unsigned int i
= 0; i
< num_nodes
; i
++) {
18 if (adj_matrix
[node
][i
] == 1) {
22 return num_successors
;
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;
29 if (!list_empty(&nodes
[node
]->list
)) {
30 list_for_each(list_iter
, &nodes
[node
]->list
) {
34 return num_successors
;
37 bool has_successor_adj_matrix(unsigned int node
, int adj_matrix
[num_nodes
][num_nodes
]) {
39 for (unsigned int i
= 0; i
< num_nodes
; i
++) {
40 if (adj_matrix
[node
][i
] == 1) {
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
));
53 list_cell
->num_node
= node
;
54 if (is_valued
) list_cell
->val
= value
;
55 list_add_tail(&(list_cell
->list
), &(successors_list
->list
));
58 void free_adj_list(succ_list_t
* successors_list
) {
59 succ_list_t
* list_iter
= NULL
;
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
));
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;
71 num_successors
= num_successors_adj_matrix(node
, adj_matrix
);
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
);
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
];
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
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
]);
101 void display_adj_lists(succ_list_t
* nodes
[num_nodes
]) {
102 succ_list_t
* list_iter
= NULL
;
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
);