topologic_sort.c

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

typedef struct ListNode {
    struct ListNode *next;
    void *ptr;
} ListNode;

void
list_node_init(ListNode *ln, ListNode *next, void *with)
{
    ln->next = next;
    ln->ptr = with;
}

typedef struct {
    ListNode *head;
    int len;
} List;

void
list_init(List *l)
{
    l->head = NULL;
    l->len = 0;
}

void
list_deinit(List *l)
{
    if (l->head != NULL) {
        ListNode *temp;
        ListNode *ln = l->head;
        for (;ln;) {
            temp = ln->next;
            free(ln);
            ln = temp;
        }
    }
}

int
list_push(List *l, void *ptr)
{
    ListNode *ln = malloc(sizeof(ListNode));
    if (!ln) {
        return 1;
    }
    list_node_init(ln, l->head, ptr);
    l->head = ln;
    l->len += 1;
    return 0;
}

#define list_foreach(_id, _l) \
    for (ListNode *_id = (_l)->head; _id; _id = (_id)->next)

//

typedef struct Node {
    List nodes;
    char *text;

    int sort_mark;
} Node;

#define NOT_VISITED 0
#define VISITED 1

void
node_init(Node *n, char *text)
{
    list_init(&n->nodes);
    n->text = text;
    n->sort_mark = NOT_VISITED;
}

void
node_deinit(Node *n)
{
    list_deinit(&n->nodes);
}

int
node_link(Node *n, Node *to_add)
{
    return list_push(&n->nodes, to_add);
}

//

int
visit(Node *n, List *sorted)
{
    if (n->sort_mark == NOT_VISITED) {
        list_foreach(ln, &n->nodes) {
            Node *n2 = ln->ptr;
            visit(n2, sorted);
        }
        list_push(sorted, n);
        n->sort_mark = VISITED;
    }
    return 0;
}

int
toposort(List *nodes, List *sorted)
{
    list_foreach(ln, nodes) {
        Node *n = ln->ptr;
        n->sort_mark = NOT_VISITED;
    }

    list_foreach(ln, nodes) {
        Node *n = ln->ptr;
        visit(n, sorted);
    }

    return 0;
}

int
main(void)
{
    Node a;
    Node b;
    Node c;
    Node d;
    Node e;
    Node f;
    Node g;
    Node h;

    node_init(&a, "a");
    node_init(&b, "b");
    node_init(&c, "c");
    node_init(&d, "d");
    node_init(&e, "e");
    node_init(&f, "f");
    node_init(&g, "g");
    node_init(&h, "h");

    node_link(&a, &c);

    node_link(&b, &c);
    node_link(&b, &f);

    node_link(&c, &e);
    node_link(&c, &h);

    node_link(&d, &e);

    node_link(&e, &g);

    node_link(&f, &e);

    node_link(&h, &g);

    //

    List nodes;
    list_init(&nodes);
    list_push(&nodes, &b);
    list_push(&nodes, &f);
    list_push(&nodes, &e);
    list_push(&nodes, &g);
    list_push(&nodes, &h);
    list_push(&nodes, &a);
    list_push(&nodes, &d);
    list_push(&nodes, &c);

    List sorted;
    list_init(&sorted);

    toposort(&nodes, &sorted);

    list_foreach(ln, &sorted) {
        Node *n = ln->ptr;
        printf("%s\n", n->text);
    }

    //

    list_deinit(&nodes);
    list_deinit(&sorted);

    node_deinit(&a);
    node_deinit(&b);
    node_deinit(&c);
    node_deinit(&d);
    node_deinit(&e);
    node_deinit(&f);
    node_deinit(&g);
    node_deinit(&h);
}