Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!hp4nl!star.cs.vu.nl!philip@cs.vu.nl From: philip@cs.vu.nl (Philip Homburg) Newsgroups: comp.os.minix Subject: Re: tsort - the never ending story Message-ID: <10163@star.cs.vu.nl> Date: 6 Jun 91 11:58:14 GMT Sender: news@cs.vu.nl Organization: Fac. Wiskunde & Informatica, Vrije Universiteit, Amsterdam Lines: 128 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'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!@*22*M@4!AE?I*&8&W14AP+!12QY(!MEI) "C@HOV*##=( 9L1UO: R" M&3:9>:S'QP*K D4FHZP@PR&C\'#$,[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;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=#",+RP50E&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@(?" M4WUM 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$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%O2@*$BH M2J5\NM=I6,47K"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?BHTR3Y8,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\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 M G?5Y)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#%HRUT\W%$LIQ/R39+)4*I4T)D,4=%=$0T5!Y I$*(2D@XTJ@S1 9D ML&62&GQW4"5%U3QR0$9*Q2,3$ 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)Y\#FJ4% M2C\$)'*))[5;=ICZAYDZ\P9$D1'#MR6#F@=O!R9[RKQ%$39AI$%Q\08B84'( M8:H']R1,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@,%W!G M3#BW6[UK3,D23)Q&RK,<-6&!K!@H,,E%BL>7',"BS*%A%(Y4',!M3+WA.$^3 M'$8]*,!?T,&4LF_"2AA12D%8[F"$K;N[Y.25RZ3+T1#,DY(7=:7,"O_$O-#* SXKH3!LQ M2Y-4E1&%JIS M',=@;,<%FP !/5#U2\LCK"A M.]>^@M5ES<&20BF!ND5XD]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 end