home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS - Coast to Coast / simteldosarchivecoasttocoast2.iso / awk / awk320.zip / TSORT.AWK < prev    next >
Text File  |  1990-02-08  |  998b  |  29 lines
  1. # tsort - topological sort of a graph
  2. #   input:  predecessor - successor pairs
  3. #   output: linear order, predecessors first
  4.  
  5. # AKW p172
  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)        # if it has no predecessors
  15.                 q[++back] = node        # queue node
  16.           }
  17.         for (front = 1; front <= back; front++) {
  18.             printf(" %s", node = q[front])
  19.             for (i = 1; i <= scnt[node]; i++)
  20.                 if (--pcnt[slist[node, i]] == 0)
  21.                     # queue s if it has no more predecessors
  22.                     q[++back] = slist[node, i]
  23.         }
  24.         if (back != nodecnt)
  25.             printf("\nerror: input contains a cycle")
  26.         printf("\n");
  27.       }
  28.  
  29.