Ruby 1.8.7 リファレンスマニュアル > ライブラリ一覧 > tsortライブラリ > TSortモジュール

module TSort

クラスの継承リスト: TSort

要約

TSort は強連結成分に関する Tarjan のアルゴリズムを用いたトポロジカルソートの実装です。

TSort は任意のオブジェクトを有向グラフとして解釈できるように設計されています。 TSort がオブジェクトをグラフとして解釈するには2つのメソッドを要求します。すなわち、tsort_each_node と tsort_each_child です。

tsort_each_node はグラフ上のすべての頂点を巡回するのに用いられます。
tsort_each_child は与えられた頂点の子を巡回するのに用いられます。

頂点同士の等価性は eql? と hash によって定義されます。これは TSort が内部でハッシュを用いているからです。

インスタンスメソッド

定義	説明
`each_strongly_connected_component {\|nodes\| ...} -> nil`	strongly_connected_components メソッドのイテレータ版です。 obj.each_strongly_connected_component は obj.strongly_connected_components.each に似ていますが、ブロックの評価中に obj が変更された場合は予期しない結果になることがあります。
`each_strongly_connected_component_from(node) {\|nodes\| ...} -> ()`	node から到達可能な強連結成分についてのイテレータです。
`strongly_connected_components -> Array`	強連結成分の集まりを配列の配列として返します。この配列は子から親に向かってソートされています。各要素は強連結成分を表す配列です。
`tsort -> Array`	頂点をトポロジカルソートして得られる配列を返します。この配列は子から親に向かってソートされています。すなわち、最初の要素は子を持たず、最後の要素は親を持ちません。
`tsort_each {\|node\| ...} -> nil`	tsort メソッドのイテレータ版です。 obj.tsort_each は obj.tsort.each と似ていますが、ブロックの評価中に obj が変更された場合は予期しない結果になることがあります。
`tsort_each_child(node) {\|child\| ...} -> ()`	TSort で拡張されるクラスで定義されていなければならないメソッドです。
`tsort_each_node {\|node\| ...} -> ()`	TSort で拡張されるクラスで定義されていなければならないメソッドです。