12.92 util.toposort - トポロジカルソート

Module: util.toposort ¶

トポロジカルソートのアルゴリズムを実装します。

Function: topological-sort graph :optional eqproc ¶

{util.toposort} Graphは有向非循環グラフ(DAG)を表現するリストです。 リストの各要素は次の形をしています。

(<node> <downstream> <downstream2> ...)

これで、ノード<node>から別のノード<downstream>等への接続が あることを表現します。<node>はどんなオブジェクトであっても構いませんが、 同一性の判定がeqprocで行えなければなりません。eqprocの既定値は eqv?です (等価参照)。 トポロジカルにソートされたノードのリストを返します。

グラフに循環が検出された場合はエラーとなります。