% Copyright 1989 by Norman Ramsey, Odyssey Research Associates % Not to be sold, but may be used freely for any purpose % For more information, see file COPYRIGHT in the parent directory #*Detecting cycles in a directed graph of productions. {\tt SPIDER} writes a list of possibly cyclic productions on {\tt cycle.test}. The program {\tt cycle.awk} reads those and reports on whether there can be a cycle in the graph. If there were a cycle, it might lead to an infinite loop in \.{WEAVE}. One should inspect contexts to see if that could really happen. # Input is a list of edges in the form $$\hbox{\tt name leftnode --> rightnode}$$ We detect a cycle if one exists. # We will use the following strategy: assemble all the edges, then read through them to label each node with the number of incoming edges and then the names of the successor nodes. We will then put nodes with no incoming edges on the work list, and remove them one by one, decrementing the incoming counts of their successors. If anything is left, there must be a cycle. #(cycle.awk#>= NF==4 && $3=="-->" { incoming[$4]+=1 if (incoming[$2]=="") { incoming[$2]=0 } successors[$2]=successors[$2] " " $4 outgoing_edges[$2]=outgoing_edges[$2] $0 "\n" next } #=!/^ *$/#> { print "What's all this?", $0 exit 1 } END { # n=0 while (n n++ } for (node in incoming) { if (incoming[node]!=0) { # } } if (cycle==0) { print "There can't possibly be a cycle in the graph" } else { exit 0 ## no error until we check context } } # #= for (node in incoming) { if (incoming[node]==0) { work[high++]=node } } # #= thisnode=work[n] temp=successors[thisnode] m = split(temp,newnodes," ") for (j=1; j<=m; j++) { thisnode=newnodes[j] incoming[thisnode]-=1 if (incoming[thisnode]==0) { work[high++]=thisnode } } # #= if (cycle==0) { print "There is a potential cycle here somewhere -- check the context" cycle=1 } printf "%s", outgoing_edges[node]