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 }