[ruby-dev:16094] tsort.rb

気が向いたので tsort.rb のご意見募集をします。

tsort.rb はトポロジカルソートをするライブラリです。
モジュールとして実現されており、適当なクラスに include して二つばかり
メソッドを追加することによりトポロジカルソートの機能を追加することがで
きます。

例えば、
  class Hash
    include TSort
    alias tsort_each_node each_key
    def tsort_each_child(node, &block)
      fetch(node).each(&block)
    end
  end
とすると Hash がトポロジカルソート可能になって、

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

というようなことが可能になります。

また、内部的には Tarjan の強連結成分を求めるアルゴリズムを使っていて、
サイクルがある場合も扱えます。そのような場合 tsort メソッドでは
TSort::Cyclic という例外が発生しますが、
strongly_connected_components メソッドではサイクルを構成する集合が得ら
れます。

まぁ、頻繁に使うものではありませんが、たまには必要になり、必要になった
場合 Tarjanのアルゴリズムを各自が思いつくのは非常に困難なので、本体に
ついてるといいんじゃないかと思っています。個人的には
  モジュールの継承構造をたどりたいと思った時
  ABNF を正規表現に変換したいと思った時
  CVS のブランチタグの関係を調べたいと思った時
  Java のクラス間の関係を調べたいと思った時
  有限状態機械を(goto がない)プログラムに落したいと思った時
などにこのアルゴリズムを使ったことがあります。

また、[ruby-list:29897] で他の実装が提案されています。効率が悪そうなの
で文句をつけましたが。なお、[ruby-list:29897] のものとはまったく APIが
完全に API が異なり、共存不能です。

http://www.ruby-lang.org/~knu/cgi-bin/cvsweb.cgi/rough/lib/tsort.rb
から取得できます。

なお、(pp のときのように)反論がない場合、まつもとさんは返事をする必要
がないと思っている節があるので、今回はとくに反論がなければいきなり 1.7
に放りこむ予定です。というわけで盛大に文句を出してくれることを希望しま
す。
-- 
[田中 哲][たなか あきら][Tanaka Akira]
「ふえろ! わかめちゃん作戦です$(C⊇」(Little Worker, 桂遊生丸)