11.64 srfi.234 - トポロジカルソート ¶

Module: srfi.234 ¶

このモジュールはトポロジカルソートを実装しています。

このSRFIはもともとGaucheのutil.toposortを拡張して作られました (see util.toposort - トポロジカルソート)。 このSRFIがfinalizeされたので、新たなコードではこちらのSRFIを使うことを推奨します。 元のutil.toposortは今ではこのSRFIの薄いラッパーになっています。

Function: topological-sort graph :optional eq node-array ¶

[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にあるノードのリストで 返されます。

Function: topological-sort/details graph :optional eq node-array ¶

[SRFI-234]{srfi.234} topological-sortと似ていますが、より詳しい情報を3つの戻り値で返します。 引数の意味はtopological-sortと同じです。

ノードがトポロジカルソート可能であれば、最初の戻り値はソートされたノードのリスト、 二番目と三番目の戻り値は#fです。

ノードがトポロジカルソート可能でない場合、最初の戻り値は#f、 二番目の戻り値はエラーメッセージ、そして三番目の戻り値は 少なくともひとつの循環についての情報を与えるノードのリストです。

Function: edgelist->graph edgelist :optional retriever ¶

[SRFI-234]{srfi.234} Converts a list of edges edgelist to a graph acceptable by topolocial-sort. Each edge is a list of two nodes, representing a directed edge (from-node to-node). The returned graph is a list of (from-node downstream-node downstream-node2 …).

The optional argument retriever is called as (retriever from-node graph) to get a graph entry starting with from-node. When omitted, assoc is used. If you need to compare nodes in a special way different from equal?, you can give a customized procedure.

(edgelist->graph '((a b) (a c) (b e) (c b)))
 ⇒ ((a b c) (b e) (c b))

Function: edgelist/inverted->graph edgelist :optional retriever ¶

[SRFI-234]{srfi.234} Like edgelist->graph, but take each edge entry as (to-node from-node).

(edgelist/inverted->graph '((a b) (a c) (b e) (a e)))
 ⇒ ((b a) (c a) (e b a))

Function: graph->edgelist graph ¶

[SRFI-234]{srfi.234} Given graph, which is a list of (from-node downstream-node downstream-node1 …), returns a list of edges, each of which being (from-node to-node). This is an inverse operation of edgelist->graph.

Function: graph->edgelist/inverted graph ¶

[SRFI-234]{srfi.234} Given graph, which is a list of (from-node downstream-node downstream-node1 …), returns a list of edges, each of which being (to-node from-node). This is an inverse operation of edgelist/inverted->graph.

Function: connected-components graph ¶

[SRFI-234]{srfi.234} Returns a list of node lists, where each list of nodes consists of a connected component of a directed graph graph. The format of graph argument is the same as topological-sort, i.e. ((node downstream …) …).

A connected component is a group of nodes such that from any node in the group can reach any other nodes in the same group.

(connected-components '((1 2 3) (2 1) (3 4) (4 3)))
  ⇒ ((4 3) (1 2))

Note: The order of result list, and the order of each node group in the list, don’t matter. Mathematically, they should be sets instead of lists.