[comp.os.minix] tsort - the never ending story

philip@cs.vu.nl (Philip Homburg) (06/06/91)

About a year ago I posted the following article:

-------------------------------------------------------------------------
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.
-------------------------------------------------------------------------

But I forgot to include my name in the program. Before everybody
tries to ftp that file from ftp.thp.uni-koeln.de, here is a repost
(with my name on it).

					Philip


begin 666 tsort.c.Z
M'YV0+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;CP
MBIPT='+"%),'!)2&;-+  8'D31LQ=>2< 8$":)JL<(",F>/"3AT7;MCP#".Q
MCALR()38-1HC1PX8"E2\6#@"Z1@V=<@8Y3&'SLPW+M#X4%#8S>'$BQN3R2HF
M\N3*EQ6#8.Q8L1G/E TC%DWZJ9LSJ$&O7HPS#YPRL55C'AUFSIR,""43-HW4
M*)PP;DZBP,.3S)LOQY./6<X"Q)<O1I(P*7*]^G4F29QP_Y(BM1GK7Z90(3+D
M.F7B;HQ"D?*$2OTL4(I0S\,3#X@\E)7!QF_OE6%&<5;19Q\5^.F'!PO\@8 '
M"N6-4,9=:9BQ$!VVZ63@2G3(40=.(+CQAF(*[*%  HV)2**)HJG@QA?QX4''
M#BNV."(=(.ATAE$R?N%C&7/@F, 8:- %0I!N6%2&D3J2F%5C0JH4I&)P%+DB
M4CS.V%@8.>'81XDGEO'%C<,9B* 34WQ1A1-53%$$$0D -@)\1K'YA1!Q9I% 
M C$4>&!\(.@9'A-// %% C((NF:;4A01!!%^SK!AAZ:!Z"*/0Z:X(HQF\JB"
MF77  2J4(>[8(QD_+FEFC6B..>29. Z$Z8=1\N@34)XF .J92YY!8YE:CKDK
M&K1>>ENFN8(P)1U5]OJKJ&P,JQBJFSKK$+0"+EDMK&)J2Z6 R=JZ[(<7UG%1
M1A+) <(>113QA!'5Q?L$$T[4>T004@A1;Q-%-%%O=MO)*D>[Y<Y7WWWYD?4E
M'2>!@*22*M@4!AE?I*&8&W14AP+!12QY(!MEI) "C@HOV*##=( 9L1UO: R"
M&3:9>:S'QP*K D4FHZP@PR&C\'#$<ZRAU1=BL('<&G-X#++(9Y5\L@(I \VR
MRV.  +/,[!KD<==R ,MNSU3_S&##0K<,<=9<SHP4QO'=D55\3FL7L@HC2^WS
MPF<'/736TT)]E[5EX%P14#I35-W$[LKH)-E5]WWUVF0JIG,;8:SQ:ID>,[YD
MDVWH73;?*Z>-]:H_7IZYF4-Z'+@*I1(.N=FE_ZUUS'C17,;FBKE>ILZ@SDXZ
MVK;G+*K%&-],UM-X1RV\RL2K_3+N(-0Q1Q@_=IYDXQ%-1*-%SUMM.N5;XQ41
MEU\HCX+QP1Z.1OB2CS^]S 09!"VHOELN*L]31UZ[]%DK'TA8 BWUL6]G<H#?
M_TXG0.= !SDGT1[%0N>;Q6T/:B2K3MOF)CK_1>]T;0N=6,R$I::1Y5E5TEG%
M#/0%S"&E.B@DEZ@NMI/^T>Z#E&L;Z,H@ RQY+(;5$M4*S=#",+RP<J'Z7)D4
MB,/YF<\UT"KA#[>50E&5D(E^ ^#M9':8,M#E"P\CTA3'%<0E7=&&P\LB ZE'
MPR_XD"RS$J)-B#@D$[XN>%-3@.W:]I(QF*D-!GG20ESH!A30Y0QCJ,XA[5">
MMAUR##CRG H6N84NX$A%"3C@L8S$O+S5*@$9(LLC01""'H @!B P@0EB(I:L
ME1($,BC/GZR'O3(84BQVV (,NC U4)[GEHCL00]BN2),)B!OIMS(;6 "S%S&
MH O5$8$<1-!+7Y(E!'F3Y9_ 1I8B@*R7?5B1@ CT)V2":"9N^.2Q3(F\]+F/
M+-DT4BA1$()CR=*8MSF80<@B32^200<@H*:1$E &/$"%+#$ IWE 0(0B\.D(
M*SH?Q]SYDZ"LSWU3LQ"&-)2 ^AV$HD ABSV-9!,ZA 4F,!#30HKG/IVU\UCP
M=)X".AFU2ZY(DW(PTNMBAS]O/>=4*Y)DJ?)9'164Y X9D2?')+:],. DJ0O)
MI!Q,B3DVE"1K0DN#'LKPAE\BD&S6I"?/5D10?;H+!0$+6"\IT@(?" M4<S!E
M2J.ZD;/N8 ?W).L\0U"THR5M:7- 03:UF8"2GK0G.24KXYR:DZGVI QTP&H\
M]?K+Q3[57<($P0FXX(83$'8,+X&8&^H@R%F^!K)8M6QCJS-9L@XU(^ST9\8V
M1@?!.F^@>WUM LD:5C-PU0RV)9G)>%M8R!Z6(@,EZ(#*P%MCEK-F($7#1:OY
M)\/* :7)#>>?]MI7."!-:6Y@6G"EQEMNHE5>1JBF:F'[V,C&5+BXK6Q3+PN"
MS&ZVLX0UK[WP54V[_,B]*%BO'%A[6[(>E;WMU-B%:CO9[?XR! ?>[9_*VJYN
MHK>:>QT4W,H@M^*,=[@3UN^^^M5?[X(JF6\CG$@'7#TXY+.:)2$<B@<'JA7#
M\ U(36!\R<+3,I'2E#$.'F_;B"6RF"#(96KKC.I8G1XK1J'AU*,6!6C>L2D 
M;&([F$V/=$$5M.B3<[@#5) $QX/E]4B],8J]C* #LK;(E"+8"QYN\U2\7 @O
M774;R40P4#%8; U&0LEO0%"$$0NAS7]Z<T#/0!<QU!($8C!0('MT%Y><AX-\
M)JN?O0CHH*:9T/+"%Z)9%"(XRYG..;%SI?.,Z3[_V4BF"4,=V$"'42LZSN$U
MT1U@ K9,_VG3F3.2=LT@43K\4C/LBB8W2_!/$)1@#IP50762K:E>%O2@*$BH
M2J5\NM=I6,47K<X.RX/32'9YAUN^X^_@$*)/UI4LOV*W8]GJ5L(5"8G0"5$J
M5]FB,;1A*RB(=XB4_+W0L8"LX]X!ON5M2H'+@>"PRF-8':Y-W=DRX>)<;C$1
MONY2@P!SF@,WQO_D<(@7E ZFI/=;B350E=N[X1U/; *T:UV8.'S;MGL=R'EG
ME( _3@&21+>T?B<JH'ZJ3%1-R56SNM6NHD!&2^SE7H6\3;-V$V!-Z"6H3&XC
MN>HTR3Y8,JN(Y/6C*P;B3FJXD[Y^]K"#46UE,*6>WA2G.;&]# 0O8=F+:]+K
M(A'G6HSCDG8NI+'SV%1+5,!.$7^M7@E^5&/_Y)"2;M4W8'4.6OWMTX<$UKUR
MGJSZQ;JUQ]Y64C$^[BT&*D%)[X-7G7SO-4>=(*-L.P%:/+HK)G=+]Y=83*J[
M=Y\[.>$^>6+$MG7EBM'2,6LV77G^DNK'W&? A5_\K;L=7']'8L.ISSG>PDK&
M2.0Z'0A[^QH'?(F 7Z/,RN_C\S]9\4178N,Q^?C6!=]&A?^1Y,<.\[:+_4?*
M9W'N5S+.!T=C5W'2]WV3)WNE1R,GIW!# H'\5R+"USK>5X$3."0-&'&\97$&
M^"-30WM:U#;?%C<<]%XE,U-V@T&"A$G<933>]5?A%5B#15:Q-U=\=URH]6'U
M94KW=0+I1SF2E&"T]6$JN!TLN&5M(V!0DGG @GE;923R-A-F0$0\D@9O4U"!
MUF4*QC%%E84/LB2Z!6:99THX($^T17E+!X4$N"4/UH7C!WI6AU:BIU2*@0>F
M!(=&\FXH<%=GE@"Z94HF (=;P(8M\$R?%'UV=11W45"CT6+YI'!@N (KH$W.
M)6 IAUHH2%WS)&"C 0.$Y5S+MSMD 8?4E8-^AX-_HET.5HJ^<1Q^%&#SU5@@
M]B>BZ%^:*(MTP5@906#P15PJ,(DKL'<3QH:FQ'2AD@(H (8M<!2T=8IP&%M*
M9WFE2%O5P8;0^(;/2%P4)GUIE77)A8HPH8>\Q8H)$(R-B(=,M8N7-5"LR(9+
M8DHR@%M@F(?IV +DN%UI" (64WE8!8?7F'D8IHT+EE]S^(T8EHZ"2(C(>"8I
M@(7I:$DK$DXB"$)+U5W?!5B;>(1WXTF]LH2S"%4KXAP;]R>8V%Z256 S!P)W
M@!4]AXD]< *:!0)\P ?K6!&7)4R;10>>58"ZB).-Q0.@:(/&E8I&@HL )F"^
MV(;B>$I!Z$35<SVM4A82\5;@ W1=UCU6V09;1FQ0=&R.06TB$"=!< 1% %#/
M!@);@!1*00<MD#==$&W5H94%9VT&Q2/9%H(K-6744VRX-UT*4&Y#IS_R5UKU
M%WE1M5=CE0#X])4H( (F@E@5%6W55'/"9G:HYW)PY9,A0'6-R26_) (H4 ;_
MQB$I0)D#99D3N2(M&37PEGB,25;%!EPBD)8HP&S-4099H@/2%G[7YR3B!G9>
M G?5Y)<E-(!YIYMS4)R.*0)<4&L"!7H3:'W_1R0[1D^?-V&SR4_G)WO+&9U_
MTIHD\X$I:(N\M9V/F9:]J8&M]P6E0IT%QY3;E(&LYWHVXHZR^97\A)H<IQC]
MAW?7]X"K69'D0ST>54#O!)B"Z7OQ!W6-YX;7M)CBN(<)B'3&5V^;F7W5)YP.
M:"-_2)+F61CGT5 /I0"S^9@'&EUH"6UNT)OPB7%^>2S-%R ;Q5M]]$>!1(Q'
M0C)?%$:!!9]7E%PI:G[!@R,BRE .5040I9W-R9\:185D-2;BV7,WVD*!!&5[
MJ7YXX4#1$3$H0$$FE#<P5!SE(4E@:FX4XY$;5!Q=B9[(=C#1Q%E<4)O0UIO,
MMJ)RJ6>%HRUT\W%$LIQ/R39+)4*I4T)D,4=%=$0T5!Y I$*(2D@XTJ@S1 9D
ML&62&GQW4"5%U3QR0$9*Q2,3<UJ5&E6A^B-DL'<'TJG<P@:Q1420RIHN*4J4
M^H=32A9#E*@PH4JV^JA&Y 8IT%;?XF,\$!.4"JRRPUN\BA2"B )/EZR^:JP1
M=YTA<*N$1),V24/0*JR[RD*$]*L^$*SO9YX3%C=5HH:6AXQ.)R,<5B5@U8KT
M1*X"0E@)T*73(0)OL!26YJ=M )XDMZX"DJW^2:QD +"EU:^9^J_?VJ$HMR3.
MFES4VJO;=[!LD%REJA.F% /X^2<T9$K8FK#@LII'2J)*:J+-:1-S,&L\DF>$
M2D+*"5 "!1%0Y$;*^72I2D8G [.@^9A.>F<9LB*Q5[&C2J 1HT-.TD.Z>:C<
MVJO!^7Z7J@(/BQ0X\GLMN")-"Z\3&U6UVJQ)BQ3[MJVNVJO>"JZ+@43:Y*S+
MJK5?BQ1AJ[!2]V!/"Q,UB42/B+:XNK:>B7#^RJH?-XW3P8;I:K7M.G5Y2UCT
M^ICWFK+G$3K[6DU62[#_.5"-Z[&OQ[!;FTYD];816R6I690P@;&KV91S);0!
MU)<Q:Z@H<$4*T+0EM&59B[JQ^2<G2J<!51TE1+!H%SK5I'<@4+N2>Y\#FJ4%
M2C\$)'*))[5;=ICZAYDZ\P9$D1'#MR6#F@=O!R9[RKQ%$39AI$%Q\08B84'(
M8:H']R<D@3%5"D@V\4E(41(BL7= NW=A-F86!9]A=&:"EB=M0G=R0@2CU@;2
M&T;_27#^6RAMPB=3D 6NQFF!]FEZ0L!9L+_]"W?_ZW8!;"A.@"B*<L#!YFF#
MIB>1,BD-K,'V^P6'DBA0,&JJF0"QAK*C1J_\U"+?:Q1A!)[:-4] JIS:E+[<
M"P<72Z%GM8#P64<2J'^R9TKL:9]Q^+H)8+W.6WQ%[)ZG-U#O&UD6Q;_3FQ.6
MJ%@*/,!],FI)S ;D:QDX:A,Z"J+B.F%*C+T0[!+-&S;R"W?A.+Y?4+XY*A1^
M9*7G2UQR+,8@,%<AFZ00%;M#6B8K2A:X*3%*AQ1C89NXF:<O"IR^.9S4>W!G
M3#BW6[UK3,D23)Q&RK,<-6&!K!@H,,E%BL>7',"BS*%A%(Y4',!M3+WA.$^3
M'$8]*,!?T,&4LF_<N,IP-\L+W"?R*HIA%0)Y7)X3]FNOQHU=U*-P%UBG['\R
MFR6G>"2AA12D%8[F"$K;N[Y.25RZ3+T1#,DY(7=:7,"O_$O-#* SXKH3!LQ 
M2Y-4E1&%JIS<F  H8 (UG"7A6\Q)?,GW#*C$=<W UFD3)J6QFI?)-<SN[!)>
M',=@;,<%FP !/5#U2\LCK"A</$]-_)ZHO,N9U<L%'(H+);)_W)R?7 :#?)L[
M8<A6A<C.]A H?9HMNK3H')\R#<!P)\G\S*$[5!WG;-/4FU&<3%PE'<HY_639
MQ5L1358I3&M<S,*/Z<*G!2+4RZ_:-<//M]'4R\MM4M%04+:<RYDX+!)_V,KA
M3,NV;,#Y"9K\]&R,K-./L[E]9[DS%U1)(JH)O4-&"W#VS*%21+9&&DHB3;(Y
M*P(E/<B&^A(N6]._B;LX8IPSV\\W&[L[6Z-A!;1_B)YTVM;./'))W-#FBWJ>
M.]>^@M5ES<&20BF!ND5XD<QH3+TNC;JJJYRL6]"N:TR\*[8^7=KW"R?Y.U"Z
M>]L*>YFBJ]H"^\Q(2T=C9T>)]WBW"L3P1Y@..K6KESJB$H%86]#-G=Q=2[=U
MY*VF5V/#"GW%A=P >+;9#8#>S;:<>=Y$8JUR.ZS<G=SIK='AZEP+2'A#,H#4
1U<2P8DKLK7Q_\M]$C)AS'4[>
 
end