home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / cmplangm / 1989_6 / awk / rtsort.awk < prev    next >
Text File  |  1988-03-05  |  994b  |  33 lines
  1. # rtsort - reverse topological sort
  2. #   input:  predecessor - successor pairs
  3. #   output: linear order, successors 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)
  13.                 rtsort(node)
  14.         }
  15.         if (pncnt != nodecnt)
  16.             printf("\nerror: input contains a cycle")
  17.         printf("\n");
  18.       }
  19.  
  20. function rtsort(node,       i, s) {
  21.     visited[node] = 1;
  22.     for (i = 1; i <= scnt[node]; i++)
  23.         if (visited[s = slist[node, i]] == 0)
  24.             rtsort(s)
  25.         else if (visited[s] == 1)
  26.             printf("error: nodes %s and %s are in a cycle\n",
  27.                 s, node)
  28.     visited[node] = 2;
  29.     printf(" %s", node)
  30.     pncnt++     # count nodes printed
  31. }
  32.  
  33.