srfi.234 - トポロジカルソート ¶このモジュールはトポロジカルソートを実装しています。
このSRFIはもともとGaucheのutil.toposortを拡張して作られました
(see util.toposort - トポロジカルソート)。
このSRFIがfinalizeされたので、新たなコードではこちらのSRFIを使うことを推奨します。
元のutil.toposortは今ではこのSRFIの薄いラッパーになっています。
[SRFI-234]{srfi.234}
graphで表される依存関係を満たすように整列したノードのリストを返します。
graphは有向非循環グラフ(DAG)を接続のリストで表したものです。 各接続は次の形式です。
(<node> <downstream> <downstream2> ...)
これは、<node>から他のノード<downstream> …への
接続があることを示してます。<node>はどんなオブジェクトであっても構いません。
ノード同士の等しさはeq引数で比較され、そのデフォルトはequal?です。
グラフに循環があった場合は#fが返されます。
(topological-sort '((shirt tie belt)
(tie jacket)
(belt jacket)
(watch)
(pants shoes belt)
(undershorts pants shoes)
(socks shoes)))
⇒ (socks undershorts watch shirt tie pants belt jacket shoes)
省略可能引数node-arrayが与えられ、それが#fでない場合、
それはノードのベクタでなければなりません。その場合、graphはノード自体ではなく
node-arrayへのインデックスで表現されます。
トポロジカルソートが終了したら、結果はnode-arrayにあるノードのリストで
返されます。
[SRFI-234]{srfi.234}
topological-sortと似ていますが、より詳しい情報を3つの戻り値で返します。
引数の意味はtopological-sortと同じです。
ノードがトポロジカルソート可能であれば、最初の戻り値はソートされたノードのリスト、
二番目と三番目の戻り値は#fです。
ノードがトポロジカルソート可能でない場合、最初の戻り値は#f、
二番目の戻り値はエラーメッセージ、そして三番目の戻り値は
少なくともひとつの循環についての情報を与えるノードのリストです。
[SRFI-234]{srfi.234}
エッジのリストedgelistを、topological-sortに渡せる形式のグラフへと
変換します。各エッジは(from-node to-node)の形式で、
from-nodeからto-nodeへの直接の接続があることを示します。
返されるグラフは、
(from-node downstream-node downstream-node2 …)
を要素とするリストです。
省略可能引数retrieverは、グラフからfrom-nodeを起点とする
エントリを抜きだす手続きで、(retriever from-node graph)
のように呼ばれます。デフォルトはassocです。
扱うグラフのノードがequal?で単純に比較できないものである場合に、
この引数に必要な機能を持つ手続きを渡すことができます。
(edgelist->graph '((a b) (a c) (b e) (c b))) ⇒ ((a b c) (b e) (c b))
[SRFI-234]{srfi.234}
edgelist->graphと似ていますが、エッジリストの各エントリは
(to-node from-node)と解釈されます。
(edgelist/inverted->graph '((a b) (a c) (b e) (a e))) ⇒ ((b a) (c a) (e b a))
[SRFI-234]{srfi.234}
(from-node downstream-node downstream-node1 …)
のリストであるgraphを取り、
(from-node to-node)のリストであるエッジリストを返します。
これはedgelist->graphの逆関数です。
[SRFI-234]{srfi.234}
(from-node downstream-node downstream-node1 …)
のリストであるgraphを取り、
(to-node from-node)のリストであるエッジリストを返します。
これはedgelist/inverted->graphの逆関数です。
[SRFI-234]{srfi.234}
有向グラフgraphから、連結成分(connected component)のノードリストのリストを返します。
graphのフォーマットはtopological-sortに渡すものと同じ、
すなわち((node downstream …) …)のリストです。
連結成分とは、グラフ内のノードのグループで、そのグループ内のどのノードから出発しても グループ内の他のノードに到達できるようなものです。
(connected-components '((1 2 3) (2 1) (3 4) (4 3))) ⇒ ((4 3) (1 2))
註: 結果のリストの順序、また各ノードグループのリストの順序に意味はありません。 数学的には、これらはリストよりもセットであるべきものです。