home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / cmplangm / 1989_6 / awk / tsort.awk < prev    next >
Text File  |  1988-03-05  |  984b  |  27 lines
  1. # tsort - topological sort of a graph
  2. #   input:  predecessor - successor pairs
  3. #   output: linear order, predecessors first
  4.  
  5.       { if (!($1 in pcnt))
  6.             pcnt[$1] = 0                # put $1 in pcnt
  7.           pcnt[$2]++                    # count predecessors of $2
  8.           slist[$1, ++scnt[$1]] = $2    # add $2 to successors of $1
  9.       }
  10. END   { for (node in pcnt) {
  11.             nodecnt++
  12.             if (pcnt[node] == 0)        # if it has no predecessors
  13.                 q[++back] = node        # queue node
  14.           }
  15.         for (front = 1; front <= back; front++) {
  16.             printf(" %s", node = q[front])
  17.             for (i = 1; i <= scnt[node]; i++)
  18.                 if (--pcnt[slist[node, i]] == 0)
  19.                     # queue s if it has no more predecessors
  20.                     q[++back] = slist[node, i]
  21.         }
  22.         if (back != nodecnt)
  23.             printf("\nerror: input contains a cycle")
  24.         printf("\n");
  25.       }
  26.  
  27.