home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programming
/
powerprogramming1994.iso
/
progtool
/
cmplngmg
/
cl_jun89.arc
/
AWK210.ARC
/
RTSORT.AWK
< prev
next >
Wrap
Text File
|
1988-03-05
|
994b
|
33 lines
# rtsort - reverse topological sort
# input: predecessor - successor pairs
# output: linear order, successors first
{ 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)
rtsort(node)
}
if (pncnt != nodecnt)
printf("\nerror: input contains a cycle")
printf("\n");
}
function rtsort(node, i, s) {
visited[node] = 1;
for (i = 1; i <= scnt[node]; i++)
if (visited[s = slist[node, i]] == 0)
rtsort(s)
else if (visited[s] == 1)
printf("error: nodes %s and %s are in a cycle\n",
s, node)
visited[node] = 2;
printf(" %s", node)
pncnt++ # count nodes printed
}