Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!yale!mintaka!bloom-beacon!eru!luth!sunic!mcsun!hp4nl!star.cs.vu.nl!philip@cs.vu.nl From: philip@cs.vu.nl (Philip Homburg) Newsgroups: comp.os.minix Subject: Enhanced tsort: cycles now permitted Message-ID: <7367@star.cs.vu.nl> Date: 23 Aug 90 11:13:24 GMT Sender: news@cs.vu.nl Organization: Fac. Wiskunde & Informatica, VU, Amsterdam Lines: 118 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'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#]"%5(']9A9%3@'VX!U\97P (V735.3'% M%U4X4<4411"1 S24><;"#9^(<2.62200 Q!UGBC:TP\\004"@@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../._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%!G12 M00<@*.6#$E &/*2A0"B(02QG P(B%.%(1Z!/"&D'J6L9,T#?"8\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<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(/?;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&.1FW\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;JH>WMY&8?<&&5YX?MT> MXAM40*]!9:BNL^ENDB\]@\!^MX+_?,-WV_SM=?_AS]?X;FX5-NG_4W,\SMT' M>'IYMY_/H(\1O@$%DC6[CUS,*6J@(&Z:\6O M!3&QY510-31N%7BJ%7AX!1I#4UQX=%PGP'M(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"8EVP_& (FATPS.4;69?,U)?R=G>KR9QJ"979XSS"\TY P5^WICM2 MLUE7:7&01T4E$EY>N8?XM(2C9WD#UU.JMW6L5YWO=TGYF(CL2TH(#[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*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 U^P8BL707NW0Q-F/Q9* RY(121B0W0G0\0@1SMKJMJR)FR[R9*70W[J6MYQY1WQ8)F-@%4_6V[R^N8_D6R3>FP5SQKMLX+MB$:$V,:'W MN:L/:KJRN[TNP<-]Q/&FTV"*%ZY1.O,1BQ@=XU+M?T,G!2U76S,+T^R3[^[XQG%0B M;'=H?+TY8<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,"IQ- M.M#2W&Y*(LYF6[>M-=/<^P6/W"5YFYTM5*$]C+UA[+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