Skip to content

Instantly share code, notes, and snippets.

@Drowze
Forked from diogofurtado/Ordenação Topológica.c
Last active June 9, 2017 12:39
Show Gist options
  • Save Drowze/63fd1ee7c41a7ae3f2891c1c59b9ee51 to your computer and use it in GitHub Desktop.
Save Drowze/63fd1ee7c41a7ae3f2891c1c59b9ee51 to your computer and use it in GitHub Desktop.
Topological sort
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
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment