[comp.os.minix] Enhanced tsort: cycles now permitted

philip@cs.vu.nl (Philip Homburg) (08/23/90)

Some time ago I wrote a version of tsort that works for all graphs. On
directed acyclic graphs (dags) it works just like the normal tsort
(and a bit faster than the BSD version). However this program is
capable of reducing more complex graphs to dags by splitting a node
into multiple other nodes with the same label (filename).

The algorithm I used is somewhat obscure, upon detection of a cycle 
the algorithm will go through a process of selecting nodes and keeping
track of dependencies until all relevant dependencies are fulfilled.

					Philip


begin 666 tsort.c.Z
M'YV-+U0HH#/GC1PZ+L8H&(@FS1P0<.2\.2,G3!N(9>28,=CF81@0=-[ ><-F
M8IHQ8=B *'@0Q!LW(#Z228-"3IDQ=,J020&"8A@X:%S"I(.F#(@T;N#40:A 
MQ8N%(Y".85.'C%$><^C,?.,"C0\%4=U,K7HU*QDV:<1T_1IVK%406+5:-;,6
MK%2J;^/*07JF;EN\5W'F@5/&[UVR<,/,F9,1H5>H<Y$:A1/&S4D4>'B2>?.%
MLN4QF%F ^/+%2!(F14B+)LTDB9/47U+8-3/ZRQ0J1(:0!AO9C5$H4IY0$9X%
M2I'0>7CB 9$';!DVC'F7,2,9!'#AQ(TC5XY"]H@R;F::64AGL,[I*^G(J8,3
MA)LW5A7L49 @Z_KV[]^J<//%-QXZ.]!G'WMT@*#3&4;M]\6!9<P18 )CH!&&
M'" HZ(9%93PX8'MH9;6@2@I:!8>#]"%5(']9A9%3@'VX!U\97P (V735.3'%
M%U4X4<4411"1  S24><;"#9^(<2.62200 Q!UGBC:TP\\004"<C0Y)!%2E%$
M$$0D.0-YYLV5WGT%,B@???G!6* *,-8!1YH:JD>@@60@6"&,_LG8(H,Q!CA0
MF.AM6*!/0)V90)HQ5GA&?R^2V"*A:/0))F%B"@I"AW1\:"BB:[+!J%5QDGFI
M0YD^5Z&G>;(XJH?/2?HGI>B!5\=%&4E$X1Y%%/&$$:+E^@033O1Z1!!2"-%K
M$T4TT:MIJ.TIAZVN7C<<%<45 0(**=)Q$@@13EBA36&0\44:5KE!AV@H,&NM
M"M2Q448**00H;7;68DN'BMO:\0:Y()AA$XR0H@MIHBI0!*^\P4U;[;79;CO'
M&FG \848;%2VQASHJEMAN^_&J\"\U!K'\+W:C@&"OOS6:A"Z*LN1:*T'?YPP
MO2/C:[*)_2(EKF]WH.5;QJ>MRW',("]LK\TN6D6PD#N_*'!%0!%,D6C=4K@?
MAD3/''*]#9O,:85MA+$&GDY?6W6%%[;1,<+8;5USR70B2'#88R]89QGH?JV"
MFY^N+7/;1G=]\KYD]/MOWWF_2'":60,N\M%P#[PFN.(&?*W&[*;A;N,*/RXX
MRH77,4<8"*)[M@H13=2?19S3#'F^A$.TE[E?6(Z"Y(I"C4;K;K]N,N@@L91I
MFHDKO:;!'A?M.<FP\TN009G:CGO!<O >./._Q[Y99Y6=9+J$5JN]&-7@;ZPY
MWD>9.ZIOUB^/-,YJRR&WB!A?B^F'!*M@DQE?A(V4:/=KU9K"M9/D:>UZ[U-?
MVLH@ Q&A*X">6I/^IM._,/PO:6I"VXO:QS7L#8Y?$3'1%^CW0%+A;TWTX^#;
MFE>XJ91A0E_(5H-*R*H(5BB%!G1<!Y$&/ *.L QP8-G=\K<_NR&H?GICG,<4
M(#B<O60,,&J#03*T$/^Y 043.L,81)-%.\@&9UD<0X!.U\4M="% \TG ]"#U
M(,QQS$\)2 -ML"@_DX6@!R"( 0A,8(*8U!$$=P2!#&2C)-&1K@QT/(,=M@"#
M+G@LCG,,8P]Z,$CZI#$!',/C1@@#DT0N,@9=$(T(Y"""1T+R6B$8&GV4U+)K
M%4%=C^P#?9X3'25E,CTS<0,<(85'RM5.=]<:VH/DB$I($?*2A'F60:XURA>2
M00<@*.6#$E &/*2A0"B(02QG P(B%.%(1Z!/"&D'J6L9,T#?"8\<Z?.\@_SR
M)T&YG>X>:1,ZU$$.,($!BQ8BN.GYLIPH4*4;SX=&^JQ1#@_2&]^(=RK.P(D^
MIW-3,D6C@I+<(2/#5%_5PH 3C"Y$C7+ 8]C84!*382L->BC#&^9(O9B=$@4A
M,-@J6XF"9"7KD11I@0\6E:8YX%&?']T(A5"P@QT<<Y7$A.G#(C:QBKGA8@$]
M'[Q6F8!ZWA,F%)GF1CL:TIZ4@0XF%292Y[C5G%!HDB X 1?<< )"*FD,+]&6
M&^I Q4*Z 4%@-1OX.&I6T8AUE1+-2"^=.:YRT2&JFYMF4D,0V.I1-:EF4*D9
M$-LQJE;UJU?M"4*I2LLR4/62MCP<I.1I2B59%9\@ *J2$B!+)2UVJ1*CF,7F
M0-FIKI:FOC*"*<LJ6*_FM;:*)>M>N0H"M*J5K6ZEIC*'ZBM@F;(.=_VJ27DK
M![]*=9H6[:TOR06>PXK5M7,,078=>]OENE)7N@TN*IG6GS+T3#*U32YNAU6L
MYTHL39K46=_,65T0--:4)>E;?L.S7WD"\ T7K9YZ4;#0%P$2CP%F'%5]**)K
MF2#"+](I?QA4OP9;99NR9*('@4=3F"F@92][5D$A5#X5V >.<[C#-2-T+1,G
M((TH80P(<JN#5=H'CR* ;C4)T]'"@:=P*\V9NT0P33& :PT/RK%1BD!?(?18
M23^.YADF)(9#@D ,TYFB@<+C$MKXK Q,7J637PAEB"IFRKH"UI7KHQX@"QD/
M1,Z)D<F<Y#.G64EK%MN#YA*&.K"!#G/.<I"?^IX[P*1E?TY H-O,6OJ889QT
MF*-9:B7*5I;@F2 HP1S6*@+1<'I,CZSF-:^ES7V*&&EZ8V^:^"N:!<KFH&-L
M\0)7G$3%P4$]<!3JM1#UZZ[F=*=]<Q &.Z.>/?;1/F-H QR&[6OU:'AU:F/!
M*FV]@V47&X_$MK8/^).G);XTW.3%Y+]0P.U90L>S-]YVM;M*-[*]A=U8FR:Z
MKYTG/!Z;IXV:YK^3#>YY/ZBUIX4)NETM.+W5N\"V5L#I=KTIQ:WIH6AZD4A3
M4M*3IG2E*-C/!A^Y6 FSTKPU1583'IDF?E>3#C]-:(;';<0&Q3SC5N$WAL"-
M(9GGG.8RQ&.1<K2C'OF\#->FW\TO:T_4/C3$@N/3FA[.H&NY2<(*?=.+5BSU
M.]T-C@S:.$G?8-(YH%2R(6>02Q>K]IFBW*8K?Q"#=-HFK5L%CU??^BSO1O?V
M_F?I"8\;%:$^XMCYJPP  R9I%8#KBAM/@U:A:)[Z!D?\:E:G +<*B=2->-(.
M<XXFQ^0RV?UR 6/0Y?_I-IPP".[2$X^JD[=\RVE>;JH>WMY&8?<&&5YX?MT>
MXAM40*]!9:BNL^ENDB\]@\!^MX+_?,-WV_SM=?_AS]?X;FX5-NG_4W,\SMT'
M>'IYMY<O^-9SGT':7NWDPR[XOM=^M;>_/H(\1O@$%DC6[CUS,*6J@(&Z:\6O
M!3&QY510-31N%7BJ%7AX!1I#4UQX=%PGP'M(<SK;95BUU7]!8S[_9R@X0UT:
M<G:)8G8I]2#%)A[\4R!IH#/5%&4MQEWF0E$JB <4U5@P=G9XA /#9%ABUW$B
M^"[6!U,N2 =NA5LJ1W+A44UX%(0/HGU%=52%! ?)A$<F$(1;T(,M $IP)'I#
MU6TQ"!?^!848E3Y6@0<KL )N!5K4Y6_2M7^)]5C"-2%\E1%P 0/)!5J<EWM!
M6%I,EUFJI22M!5[7XA!S0!E0A +495M*8H?0M8!Z!8=<95UMN%H)H (Q6(9+
MMUH]B$<>IR8I@ (QV )'85AZ&(2#Q7%D%XB&)1H].(KAE8>6I5RVXDI%.$VF
MA5FHI814]8>3&(-XY(&K](<]6"%X) .*Q8MB6$TM@(NNI8,@ "YC9U)!J(IG
M9TJ+Y8KE%8LI=U.*=81X((54N(DQD@(IR(UG1!^R5']P@S.PU52SQ8;O@H&H
MH8%4E$8=.%QF!4>;84FKE(:^%5;798X@< <-X2Z-6!%<-4DGD%8@P =\P"WV
M*%@]H%9TT%8_2%T\0(>KA( /LHAK:(@/V5_?%7@Q((%P SR&9"<HD#H\Q3H2
MUV(JB6TK=FFSDVDC8Q7/(DH[$@1'4 30)&H@L 5(H11TT (<TP6D)AHOF3:I
M9DW8U&H*@(XL)#LB!% RU7AI-'QU97S+]U&+)5/QIB28-EDB\!Z:!4^D9DH)
M=W X5P;^)@>8EVP_& (FATPS.4<B@ )E(&WED0)G.4UI:8[T(9#G0VT?IH]@
M69<H( (^B0*?IAE - <Z4&JG1WL84FLSAR(DXX.KA&D_-"+4AW0TET+3%):)
MR06()DTSU7R3"7U'M& AT':K%9;,I'N"-P<I@)I*(I@$B9?8MTJ@)9N)Z9.2
M^7UU-WODEF^<I9K$Z7<RXH>;69?,U)?R=G>KR9QJ"979XSS"\TY P5^WICM2
MLUE7:7&01T4E$EY>N8?XM(2C9WD#UU.JMW6L5YWO=TGYF(C<Y$W@I "D*0+M
M%#VZTY.CY@:2:9S8IIF<.5H&@TY'MDZK]411-$67""'N D,R1%L&*II4]9_ 
M5WWY^4U5$$ZQB9@B()WI)!Z_&) #F7L0VC]3!&+\U'N%LSV>L2TH(#[UPS$ 
M)!FR<3HXFFO>DCD;B#-G%I/ N6DW&4UKQ06*.6J2^6D">I1*ACYG)AHX2G\Q
M:G\@$#_S\YC74D16Q$5DL!,* $%$1$%6%"!F.D!CNF)KBC;N]2$4E3ER4$,9
M52#=$EUD $=YBB!DL'344:>EP@:#Q3]I&I@K>BT$Y(0)H)NY-T&&:D$PP4?7
M JD5A!0IH%.HXF \$!-CJJE]DUQ@*JE2B (A-ZJ8"JKEYIJ6:D4+V9 $I*J<
M6JFHZ@:9Z@.;6ICXJ7YQ^AP[2':;"'+[T:MLX%* "%,\\R')E0 U"AHB\ 9+
M469;FI>XJ23)^ARR2IVQBJN4!WO$JJHOAT>M*JFT.*Y(T7IW\"&TV*<Z@4<C
M^8NK1$!XM*VH(GZ &16TH9\ARI\D:A-S8&@%DF1<"B/T TW2))6T0S\A%Z@U
M%"\(FVFE2: ><Z(.&GCLNJ=/F:7IJ$ 8TD! ]*5H*JF669AOJ@+FJDO"1YXB
M1WQI5++7R@9PY*BT&K)(X6PS&ZFIRJVSUJFA5ZNE>JHT:ZO@^A\D%UXG^ZH8
MY(5 B[-"J[/!]Y6'0JR_"AH]**PO:ZPE1ZS)U:R)":T!2QMJTP;5^K+9RI88
MI&_?JK/A^BU!.TTGBZ[JFI&V"!/O6FGJF4\D&96<23_7DD)E:D("=$./N6(R
MBP)^"[7]*9RB03]EJW-J8TI*!P*,J[:I!YC8^4&%PZ&S]IFR@95<-T1KLI6'
MHK)O0!09T:UQI#YMD <QE)FB4;I%X3(R)!I(41(B03Z5X:?IEP D(2XM*D4V
M 4>U^P8BL707NW0Q-F/Q9* RY(121B0W0G0\0@1SMKJMJR)FR[R9*70W<B13
MD 5-]F11]F;0:R1(4KVL&W35J;Y% B52 @7ARV;CJV-9LB5=<F7/V[Y.$"53
M,F=_F0"$!K!SUJS,9!^Y:Q0RA)NME509^IAN-;S%FT?L.53L9Z <-GY?5W[M
M!W[,R:BP>[J6MYQY1WQ8)F-@%4_6V[R^N8_D6R3>FP5SQKMLX+MB$:$V,:'W
MN:L/:KJRN[TNP<-]<VTR1(LR3,-0Y*(W+!1'#+QU]: UC,1F"U3XVDT@&D[]
MJ;DO(J#7TIC<PG%\$6H/P9@[(:4&ND C"YJ8B;W:]L$N4\:5^<.Q&\1 EYD3
MVZ#C(8E8;!4HP,:A2L1\K+Y\K+W82\0I[,."O"*6E51_G)D.6+Y:PB59X&RO
M6,C8V\@NC"3+:H<O%0*_^Z*O*&GB^XHN9*&925N!?)F=:9M$#"%QA11T1<2Z
MF+JV"P?N2LCI:\BHS+[=BR1$K,A W, CDLFB+"%ZNI BE1%=.B*?C (F ,P8
M\\FG_'RIK(>Q/&FTV"*%ZY1.O,1BQ@=XU+M?T,G!2U76S,+T^R3[^[XQG%0B
M;'=H?+TY8<F[_+UU^*'[><7;F29:+,8\@1(D]<6+V9ADC,IFO+ZNJP#1_,X%
MG=!"3,<,JDYWO%IYC$@)75JZ6,Y*$L"'%L,$G)@&'%WI@;W5VEH+#'JYS,AH
MI;_\"P4'.+=Q"<%PP*B';+;U"\FC"9W!.: %2M#(68M-A[)V>['&[!X=6V',
M[,QG/+'$I*]63*(3K<5\^Q(&>\:.BZ SF<J?F70.W&W]::)V?)Z-J*>,"IQ-
M.M#2W&Y*(LYF6[>M-=/<^P6/W"5YFYTM5*$]C+UA[+<E2S^$FZB&Z\"&"<"/
MV;ASC+UO+;U&MTJ1.[GU6KF5=KD]-*:=";+\PV%)?6*@6R&6>L$I^W@K.X][
M)S>A^W4?5;B;'7TVN[0U9YM]-\)7@4&B2D$<]K.G?42W&GY$&Y>UW2!(N[,W
BN]JW_06NS:C4I)I4=S><2XO+V6]L6]G15ZY%--N"=YT* 'Y$
 
end