home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS - Coast to Coast / simteldosarchivecoasttocoast2.iso / awk / awk320.zip / RTSORT.AWK < prev    next >
Text File  |  1990-02-08  |  1KB  |  35 lines
  1. # rtsort - reverse topological sort
  2. #   input:  predecessor - successor pairs
  3. #   output: linear order, successors first
  4.  
  5. # AKW p174
  6.  
  7.       { if (!($1 in pcnt))
  8.             pcnt[$1] = 0                # put $1 in pcnt
  9.           pcnt[$2]++                    # count predecessors of $2
  10.           slist[$1, ++scnt[$1]] = $2    # add $2 to successors of $1
  11.       }
  12. END   { for (node in pcnt) {
  13.             nodecnt++
  14.             if (pcnt[node] == 0)
  15.                 rtsort(node)
  16.         }
  17.         if (pncnt != nodecnt)
  18.             printf("\nerror: input contains a cycle")
  19.         printf("\n");
  20.       }
  21.  
  22. function rtsort(node,       i, s) {
  23.     visited[node] = 1;
  24.     for (i = 1; i <= scnt[node]; i++)
  25.         if (visited[s = slist[node, i]] == 0)
  26.             rtsort(s)
  27.         else if (visited[s] == 1)
  28.             printf("error: nodes %s and %s are in a cycle\n",
  29.                 s, node)
  30.     visited[node] = 2;
  31.     printf(" %s", node)
  32.     pncnt++     # count nodes printed
  33. }
  34.  
  35.