topological sort in awk

topsort.awk

#!/usr/bin/gawk -f

# @file topsort.awk
# @brief perform topological sort in awk
# @note tested in gawk 4.1.3, mawk 1.3.4, and nawk

{
    edge[$1] = edge[$1]" "$2;
}
END {
    do {
        last_sources = "";
        for (i in edge) {
            last_sources = last_sources" "i;
        }
        for (source in edge) {
            found = 0;
            for (s in edge) {
                split (edge[s],targets," ");
                for (j in targets) {
                    if (source == targets[j]) {
                        found = 1;
                        break;
                    }
                }
                if (found) {
                    break;
                }
            }
            if (!found) {
                print source;
                split(edge[source],targets," ");
                for (i in targets) {
                    if (!(targets[i] in edge)) {
                        edge[targets[i]] = "";
                    }
                }
                delete edge[source];
            }
        }
        now_sources = "";
        for (i in edge) {
            now_sources = now_sources" "i;
        }
    } while (now_sources != last_sources);
    if (length(last_sources) != 0 ) {
        print "loop found!!";
    }
}

topsort.in

7 11
7 8
5 11
3 8
3 10
11 2
11 9
8 9
11 10