コンテンツにスキップ

0251: 集合演算による推移閉包

問題

有向グラフを辺のタプル \((u, v)\) の集合（set）で表します。 transitive_closure(edges) を実装してください。 返り値は edges の推移閉包、すなわち「\(u\) から \(v\) へ長さ1以上の有向路が存在するとき、かつそのときに限り \((u, v)\) を含む」最小の辺集合です。

アルゴリズムの骨格は不動点反復です。 現在の辺集合の2辺をつないで得られる辺をすべて追加する操作を、集合が変化しなくなるまで繰り返します。 1回の拡大は集合内包表記と集合演算で書いてください。

制約

  • edges は (始点, 終点) のタプルからなる set です。頂点はハッシュ可能なオブジェクトです。
  • edges は空集合のこともあります。そのときは空の set を返します。
  • 入力の edges を変更してはいけません。返り値は新しい set です。
  • グラフに閉路があるとき、閉路上の各頂点 \(u\) について \((u, u)\) が閉包に含まれることに注意してください。
  • 反復は必ず停止しなければなりません。

例

>>> sorted(transitive_closure({(1, 2), (2, 3), (3, 4)}))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
>>> sorted(transitive_closure({("a", "b"), ("b", "a")}))
[('a', 'a'), ('a', 'b'), ('b', 'a'), ('b', 'b')]
>>> transitive_closure(set())
set()
>>> e = {(1, 2)}
>>> transitive_closure(e) == e
True
>>> e
{(1, 2)}

発展

  • 1回の反復で辺を「1本ずつ伸ばす」実装では、最長の路の長さに比例した回数の反復が必要です。閉包の途中結果どうしをつなぐように変更すると、反復回数を路長の対数に抑えられます（ダブリング）。両者の反復回数を頂点数 \(n\) の関数として見積もり、実測で比較してください。
  • 反射推移閉包を返す reflexive_transitive_closure(edges) を実装してください。頂点集合は edges に現れる頂点全体とします。

参考