TopSort in Python?

[Mike C. Fletcher]

Well, it's not topsort-the-official-algo, but when I first described it, Tim
Peters said it was a type of topological sort.  Warning: it's extremely
inefficient, using recursive calls of all things!  I did this without any
knowledge of the computer science in the field (have since learned some, but
didn't fix this code), it was just a description of an algorithm I needed to
get a job done, and I don't use it any more.

Cheers,
Mike


Dinu C. Gherman <gherman at my-deja.com> wrote in message
news:7lfjn0$b1v$1 at nnrp1.deja.com...
> Does anybody have a simple-minded-but-working full-Python
> implementation of topsort, the topological sorting algorithm?
> Or maybe *any* topsort? I remember only one such algorithm...
> python.org/search doesn't reveal any...
>
> Thanks,
>
> Dinu
>
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
>


begin 666 dsort.py
M;G5L;'9A;" ]("@Q+"D-"@T*8VQA<W, at 1%-O<G0Z#0H))R<G#0H)02 B9&5P
M96YD96YC>2(@<V]R=&EN9R!C;&%S<RP@=7-E9"!T;R!O<F1E<B!E;&5M96YT
M<PT*"6%C8V]R9&EN9R!T;R!D96-L87)E9" B9&5P96YD96YC:65S(B H;6%N
M>2UT;RUO;F4@<F5L871I;VYS:&EP<RD-"@E)<R!N;W0 at 82!B96%U=&EF=6P@
M86QG;RP at 8G5T(&ET('=O<FMS("AO<B!S965M<R!T;RD-"@E297%U:7)E<R!H
M87-H86)L92!V86QU97, at 9F]R(&%L;"!E;&5M96YT<RX-"@D-"@E4:&ES(&ES
M(&$@<75I8VL@:&%C:RP@=7-E(&%T('EO=7(@;W=N(')I<VLA#0H)#0H)0F%S
M:6,@=7-A9V4Z#0H)"4-R96%T92!A($13;W)T(&UY<V]R=&5R#0H)"69O<B!E
M86-H(&5L96UE;G0@<2!W:&EC:"!I<R!P87)T(&]F('1H92!S970@=&\@<V]R
M="P at 8V%L;#H-"@D)"6UY<V]R=&5R+G)U;&4H(&1S;W)T+FYU;&QV86PL('$I
M#0H)"0DC('1H:7,@:7,@;F]T('-T<FEC=&QY(&YE8V5S<V%R>2!F;W(@96QE
M;65N=',@=VAI8V@@87)E#0H)"0DC(&1E<&5N9&5N="!O;B!O=&AE<B!O8FIE
M8W1S+"!B=70@:70@:7,@;F5C97-S87)Y(&9O<@T*"0D)(R!T:&]S92!W:&EC
M:"!A<F4@;F]T+B @1V5N97)A;&QY(&ET)W, at 96%S:65S="!T;R!C86QL#0H)
M"0DC('1H92!N=6QL(')U;&4 at 9F]R(&5A8V@@96QE;65N="X-"@D)9F]R(&5A
M8V@@<G5L92!X(&1E<&5N9',@;VX@>2P at 8V%L;#H-"@D)"6UY<V]R=&5R+G)U
M;&4H('@L('DI#0H)"7=H96X at 7V%L;%\@<G5L97, at 87)E(&5N=&5R960L(&-A
M;&P-"@D)=')Y. at T*"0D)<V]R=&5D;&ES=" ](&UY<V]R=&5R+G-O<G0H*0T*
M"0EE>&-E<'0 at 5F%L=65%<G)O<CH-"@D)"6AA;F1L92!R96-U<G-I=F4 at 9&5P
M96YD96YC:65S(&AE<F4N+BX-"@D)#0H)"0T*"49O<B!A;B!E>&%M<&QE(&]F
M(')E86PM;&EF92!U<V4L('-E92!T:&4 at 5E)-3"!L:6YE87)I<V5R+ at T*"0T*
M"2<G)PT*"61E9B!?7VEN:71?7RAS96QF+"!R96-U<G-E17)R;W(]3F]N92 I
M. at T*"0ES96QF+F1E<&5N9&]N(#T@>VYU;&QV86PZ6S!=?0T*"0ES96QF+G)E
M8W5R<V5%<G)O<B ](')E8W5R<V5%<G)O<@T*"61E9B!R=6QE*"!S96QF+"!D
M97!O;BP at 9&5P<RDZ#0H)"2<G)PT*"0E296=I<W1E<B!A(")R=6QE(BX@($)O
M=&@@96QE;65N=',@;75S="!B92!H87-H86)L92!V86QU97,N#0H)"5-E92!T
M:&4 at 8VQA<W,G(&1O8W5M96YT871I;VX at 9F]R('5S86=E+ at T*"0DG)R<-"B,)
M"7!R:6YT("<G)W)E9VES=&5R:6YG(')U;&4Z)R<G+"!D97!O;BP at 9&5P<PT*
M"0EI9B!S96QF+F1E<&5N9&]N+FAA<U]K97DH(&1E<',@*2!A;F0 at 9&5P;VX@
M:7,@;F]T(&YU;&QV86PZ#0H)"0ES96QF+F1E<&5N9&]N6R!D97!S(%TN87!P
M96YD*"!D97!O;B I#0H)"65L:68 at 9&5P;VX@:7,@;F]T(&YU;&QV86PZ#0H)
M"0ES96QF+F1E<&5N9&]N6R!D97!S(%T@/2!;+3$L(&1E<&]N70T*"0EE;&EF
M(&YO="!S96QF+F1E<&5N9&]N+FAA<U]K97DH(&1E<',@*3H-"@D)"7-E;&8N
M9&5P96YD;VY;(&1E<', at 72 ](%LM,2!=#0H)9&5F('-O<G0H('-E;&8@*3H-
M"@D))R<G#0H)"4=E="!T:&4@<V]R=&5D(')E<W5L=', at 87, at 82!L:7-T#0H)
M"2<G)PT*"0EF;W(@:V5Y+"!V86QU92!I;B!S96QF+F1E<&5N9&]N+FET96US
M*"DZ#0H)"0ES96QF+E]D<V]R="@@:V5Y+"!V86QU92D-"@D)=&5M<" ](%M=
M#0H)"69O<B!K97DL('9A;'5E(&EN('-E;&8N9&5P96YD;VXN:71E;7,H*3H-
M"@D)"71E;7 N87!P96YD*" H=F%L=65;,%TL(&ME>2D@*0T*"0ET96UP+G-O
M<G0H*0T*"0ET96UP+G)E=F5R<V4H*0T*"0ET96UP,B ](%M=#0H)"69O<B!X
M+'D@:6X@=&5M<#H-"@D)"71E;7 R+F%P<&5N9"@@>2 I#0H)"2, at 9F]L;&]W
M:6YG(&%D9',@=&AE(&5L96UE;G1S('=I=&@@;F\@9&5P96YD96YC:65S#0H)
M"71E;7 R6VQE;BAT96UP,BDZ72 ]('-E;&8N9&5P96YD;VY;(&YU;&QV86P@
M75LQ.ET-"@D)<F5T=7)N('1E;7 R#0H)9&5F(%]D<V]R="@@<V5L9BP@:V5Y
M+"!V86QU92 I. at T*"0EI9B!V86QU95LP72 ]/2 M,CH-"@D)"6EF('-E;&8N
M<F5C=7)S945R<F]R. at T*"0D)"7)A:7-E(%9A;'5E17)R;W(L("<G)T1E<&5N
M9&5N8VEE<R!W97)E(')E8W5R<VEV92$G)R<-"@D)"65L<V4Z#0H)"0D):68@
M7U]D96)U9U]?. at T*"0D)"0EP<FEN=" G)R=296-U<G-I=F4 at 9&5P96YD96YC
M>2!D:7-C;W9E<F5D(&%N9"!I9VYO<F5D(&EN(&1S;W)T+D1S;W)T+E]D<V]R
M="!O;B E<SHE<R<G)R4H:V5Y+"!V86QU92D-"@D)"0ER971U<FX@,2 C('=E
M(&MN;W<@:70@:&%S(&%T(&QE87-T(&]N92!R969E<F5N8V4N+BX-"@D)96QI
M9B!V86QU95LP72 ]/2 M,3H@(R!H879E;B=T('EE="!C86QC=6QA=&5D('1H
M:7,@<F1E<'1H#0H)"0EV86QU95LP72 ]("TR#0H)"0ET96UP=F%L(#T at 6S!=
M#0H)"0EF;W(@>"!I;B!V86QU95LQ.ETZ#0H)"0D)=')Y. at T*"0D)"0ET96UP
M=F%L+F%P<&5N9"@@,2 K('-E;&8N7V1S;W)T*"!X+"!S96QF+F1E<&5N9&]N
M6WA=*2 I#0H)"0D)97AC97!T($ME>45R<F]R. at T*"0D)"0ES96QF+F1E<&5N
M9&]N6R!N=6QL=F%L(%TN87!P96YD*"!X("D@(R!I<R!A;B!U;G)E9F5R96YC
M960 at 96QE;65N= T*"0D)"0ET96UP=F%L+F%P<&5N9"@@,2 I#0H)"0EV86QU
M95LP72 ](&UA>"@@=&5M<'9A;" I#0H)"0ER971U<FX@=F%L=65;,%T-"@D)
M96QS93H-"@D)"7)E='5R;B!V86QU95LP70T*)R<G#0IF<F]M(&UC9BYU=&EL
M<R!I;7!O<G0 at 9'-O<G0-"CX^/B!X(#T at 9'-O<G0N1%-O<G0H*0T*/CX^(&UA
M<"@@>"YR=6QE+"!;,2PR+#(L-"PU+#1=+"!;,BPS+#0L-2PV+#-=("D-"EM.
M;VYE+"!.;VYE+"!.;VYE+"!.;VYE+"!.;VYE+"!.;VYE70T*/CX^('@N<V]R
(="@I#0HG)R<`
`
end