Topological sort

grafo.txt

1 0
2 0
3 0
4 3
5 4
6 5
7 5
8 7
9 8
10 9
11 10
12 0
13 9
14 13
15 14
15 11
16 15
17 16
18 17
19 18
20 19
21 0
22 0
23 16
24 23
25 24
26 25
27 26
28 27
29 28
30 29
31 0
32 0
33 26
34 33
35 33
36 0
37 34
38 37
39 38
40 39
41 40
42 41
43 42
44 43

projeto.c

#include <stdio.h>
#include <stdlib.h>

#define ID_QTY 44 /* quantity of vertices */
#define OUTGOING_SIZE ID_QTY-1 /* max number of outgoing per vertex */

typedef struct {
  int id; // id representing the vertex
  int in_degree; // number of dependecies
  int outgoing_list[OUTGOING_SIZE]; // next vertices
} s_vertex;

/* list abstraction */
int ordened_list[ID_QTY];
int ordened_list_index = 0;
void add_to_ordened_list(s_vertex vertex) {
  ordened_list[ordened_list_index] = vertex.id;
  ordened_list_index++;
}
void print_ordened_list() {
  for(int i = 0; i < ordened_list_index; i++) {
    printf("%d ", ordened_list[i]);
  }
}

/* supposing the vertices are represented in:
 * "vertice_id dependence_id" each line
 * this function gets all the vertices in a list, incrementing its dependencies
 */
void get_vertices_from_file(char const *file_name, s_vertex vertex_list[]) {

  FILE *fp = fopen(file_name, "r");

  char line[20];
  int from_id;
  int to_id;
  int j;

  while(fgets(line, 20*sizeof(char), fp) != NULL) {
    sscanf(line, "%d %d", &to_id, &from_id);
    if(from_id != 0) {
      vertex_list[to_id].in_degree += 1;
      for(j = 0; vertex_list[from_id].outgoing_list[j] != -1; j++);
      vertex_list[from_id].outgoing_list[j] = to_id;
    }
  }
}

/* initialize the vertices list with 0 dependencies each and 0 outgoings */
void initialize_vertex_list(int size_list, int max_outgoings, s_vertex vertex_list[]) {

  for(int i = 1; i < size_list; i++) {
    vertex_list[i].id = i;
    vertex_list[i].in_degree = 0;
    for(int j = 0; j < max_outgoings; j++) { vertex_list[i].outgoing_list[j] = -1; }
  }
}

void topological_sort(s_vertex vertices[]) {
  int i;

  /* if the vertex has no dependecies, add it to the list */
  for(i = 1; i <= ID_QTY; i++) {
    if(vertices[i].in_degree == 0) {
      add_to_ordened_list(vertices[i]);
    }
  }

  /* for all edges u->v, decrement v.in_degree and add it to the sorted list if v.in_degree == 0 */
  for(i = 1; i <= ID_QTY; i++) {
    for(int j = 0; j < OUTGOING_SIZE; j++) {
      if(vertices[i].outgoing_list[j] == -1)
        break;

      vertices[vertices[i].outgoing_list[j]].in_degree--;

      if(vertices[vertices[i].outgoing_list[j]].in_degree == 0) {
        add_to_ordened_list(vertices[vertices[i].outgoing_list[j]]);
      }
    }
  }
}

/* debug vertices */
void print_vertex(s_vertex vertex) {
  printf("id: %d\n", vertex.id);
  printf("in_degree: %d\n", vertex.in_degree);
  printf("outgoings: ");
  for(int j = 0; j < OUTGOING_SIZE; j++) { printf("%d ", vertex.outgoing_list[j]); }
}
void print_vertices(s_vertex vertex_list[]) {
  for(int i = 1; i <= ID_QTY; i++) {
    print_vertex(vertex_list[i]);
    printf("\n----\n");
  }
}


int main(int argc, char *argv[]) {
  s_vertex vertices[ID_QTY+1];
  initialize_vertex_list(ID_QTY+1, OUTGOING_SIZE, vertices);
  get_vertices_from_file(argv[1], vertices);
  // print_vertices(vertices); /*debug function */

  /* kahn algorithm */
  topological_sort(vertices);

  print_ordened_list();

  return 0;
}