tsort.awk

awk scripts awk scripts awk scripts awk scripts

# tsort - topological sort of a graph
#   input:  predecessor - successor pairs
#   output: linear order, predecessors first

# AKW p172

      { if (!($1 in pcnt))
            pcnt[$1] = 0                # put $1 in pcnt
          pcnt[$2]++                    # count predecessors of $2
          slist[$1, ++scnt[$1]] = $2    # add $2 to successors of $1
      }
END   { for (node in pcnt) {
            nodecnt++
            if (pcnt[node] == 0)        # if it has no predecessors
                q[++back] = node        # queue node
          }
        for (front = 1; front <= back; front++) {
            printf(" %s", node = q[front])
            for (i = 1; i <= scnt[node]; i++)
                if (--pcnt[slist[node, i]] == 0)
                    # queue s if it has no more predecessors
                    q[++back] = slist[node, i]
        }
        if (back != nodecnt)
            printf("\nerror: input contains a cycle")
        printf("\n");
      }