[ruby-list:29897] tsort.rb

　tsort(1) のようなトポロジカルソートを行う TSort クラスを作って
みました。

	http://www.idaemons.org/~knu/ruby/misc/tsort.rb

何をするのかというと、 A は B より強い、 C は A より強い、 B は
D より強い、 C は D と E より強い、 E は D より強い、といった
情報をいくつも与え、それを元に強い順を導き出すというものです。

　今の例は、

	require '~/src/rb/tsort.rb'

	t = TSort.new 

	t.add(:A, :B)
	t.add(:C, :A)
	t.add(:B, :D)
	t.add(:C, :D, :E)
	t.add(:E, :D)

	t.tsort #=> [:C, :A, :B, :E, :D]

で実現できます。典型的には、依存関係を解くときなどに使います。

　与えるヒントが十分でない場合、当然結果は一意になりません。
逆にヒントに矛盾がある場合にはグー・チョキ・パーのような循環が
できてしまうこともあります。


　以下が各メソッドの説明です。

TSort::new
	生成。

TSort#add(a, *b)
	a は b の各要素より大きいという情報を与える。

TSort#delete(a)
	a という要素の存在を抹消する。
TSort#delete(a, *b)
	a が b の各要素より大きいという情報を抹消する。

TSort#tsort!
TSort#tsort! { |cycle| ... }
	ソートを行い結果を配列で返す。ソートの過程でオブジェクトは
	破壊され、終了後は情報は空になる。ブロックが与えられた場合、
	循環が検出される度にその循環を引数にブロックが呼び出される。
	ブロックの評価値が偽の場合ソートは中断され、 nil が返る。
	ブロックが与えられなかった場合やブロックが真を返した場合は、
	その循環を切断してソートは続行される。

TSort#tsort
TSort#tsort { |cycle| ... }
TSort#to_a
TSort#to_a { |cycle| ... }
	オブジェクトが保存されることを除き tsort! と同じ。ただし、
	保存のためにディープコピーが発生するのでコストは高い。

TSort#empty?
	情報が空の場合に真を返す。

TSort#clear
	情報を空にする。

TSort#dump
	情報をハッシュ化したもののコピーを返す。

TSort#dup
	オブジェクトをディープコピーにより複製する。

-- 
                     /
                    /__  __            Akinori.org / MUSHA.org
                   / )  )  ) )  /     FreeBSD.org / Ruby-lang.org
Akinori MUSHA aka / (_ /  ( (__(  @ iDaemons.org / and.or.jp

"Freeze this moment a little bit longer, make each impression
  a little bit stronger..  Experience slips away -- Time stand still"