From: Tanaka Akira <akr@...17n.org>
Date: 2002-02-26T14:04:35+09:00
Subject: [ruby-dev:16094] tsort.rb

$B5$$,8~$$$?$N$G(B tsort.rb $B$N$40U8+Jg=8$r$7$^$9!#(B

tsort.rb $B$O%H%]%m%8%+%k%=!<%H$r$9$k%i%$%V%i%j$G$9!#(B
$B%b%8%e!<%k$H$7$F<B8=$5$l$F$*$j!"E,Ev$J%/%i%9$K(B include $B$7$FFs$D$P$+$j(B
$B%a%=%C%I$rDI2C$9$k$3$H$K$h$j%H%]%m%8%+%k%=!<%H$N5!G=$rDI2C$9$k$3$H$,$G(B
$B$-$^$9!#(B

$BNc$($P!"(B
  class Hash
    include TSort
    alias tsort_each_node each_key
    def tsort_each_child(node, &block)
      fetch(node).each(&block)
    end
  end
$B$H$9$k$H(B Hash $B$,%H%]%m%8%+%k%=!<%H2DG=$K$J$C$F!"(B

  {1=>[2, 3], 2=>[3], 3=>[], 4=>[]}.tsort
  #=> [3, 2, 1, 4]

$B$H$$$&$h$&$J$3$H$,2DG=$K$J$j$^$9!#(B

$B$^$?!"FbItE*$K$O(B Tarjan $B$N6/O"7k@.J,$r5a$a$k%"%k%4%j%:%`$r;H$C$F$$$F!"(B
$B%5%$%/%k$,$"$k>l9g$b07$($^$9!#$=$N$h$&$J>l9g(B tsort $B%a%=%C%I$G$O(B
TSort::Cyclic $B$H$$$&Nc30$,H/@8$7$^$9$,!"(B
strongly_connected_components $B%a%=%C%I$G$O%5%$%/%k$r9=@.$9$k=89g$,F@$i(B
$B$l$^$9!#(B

$B$^$!!"IQHK$K;H$&$b$N$G$O$"$j$^$;$s$,!"$?$^$K$OI,MW$K$J$j!"I,MW$K$J$C$?(B
$B>l9g(B Tarjan$B$N%"%k%4%j%:%`$r3F<+$,;W$$$D$/$N$OHs>o$K:$Fq$J$N$G!"K\BN$K(B
$B$D$$$F$k$H$$$$$s$8$c$J$$$+$H;W$C$F$$$^$9!#8D?ME*$K$O(B
  $B%b%8%e!<%k$N7Q>59=B$$r$?$I$j$?$$$H;W$C$?;~(B
  ABNF $B$r@55,I=8=$KJQ49$7$?$$$H;W$C$?;~(B
  CVS $B$N%V%i%s%A%?%0$N4X78$rD4$Y$?$$$H;W$C$?;~(B
  Java $B$N%/%i%94V$N4X78$rD4$Y$?$$$H;W$C$?;~(B
  $BM-8B>uBV5!3#$r(B(goto $B$,$J$$(B)$B%W%m%0%i%`$KMn$7$?$$$H;W$C$?;~(B
$B$J$I$K$3$N%"%k%4%j%:%`$r;H$C$?$3$H$,$"$j$^$9!#(B

$B$^$?!"(B[ruby-list:29897] $B$GB>$N<BAu$,Ds0F$5$l$F$$$^$9!#8zN($,0-$=$&$J$N(B
$B$GJ86g$r$D$1$^$7$?$,!#$J$*!"(B[ruby-list:29897] $B$N$b$N$H$O$^$C$?$/(B API$B$,(B
$B40A4$K(B API $B$,0[$J$j!"6&B8ITG=$G$9!#(B

http://www.ruby-lang.org/~knu/cgi-bin/cvsweb.cgi/rough/lib/tsort.rb
$B$+$i<hF@$G$-$^$9!#(B

$B$J$*!"(B(pp $B$N$H$-$N$h$&$K(B)$BH?O@$,$J$$>l9g!"$^$D$b$H$5$s$OJV;v$r$9$kI,MW(B
$B$,$J$$$H;W$C$F$$$k@a$,$"$k$N$G!":#2s$O$H$/$KH?O@$,$J$1$l$P$$$-$J$j(B 1.7
$B$KJ|$j$3$`M=Dj$G$9!#$H$$$&$o$1$G@9Bg$KJ86g$r=P$7$F$/$l$k$3$H$r4uK>$7$^(B
$B$9!#(B
-- 
[$BEDCf(B $BE/(B][$B$?$J$+(B $B$"$-$i(B][Tanaka Akira]
$B!V$U$($m(B! $B$o$+$a$A$c$s:n@o$G$9$(C"=$B!W(B(Little Worker, $B7KM7@84](B)