トポロジカル順序付けは有向無閉路グラフ(directed acyclic graph)について定義されるものである。閉路がない有向グラフだと必ず順番のようなものを付けることができる。具体的にどういうものに使えるか、というと
- 仕事の順番
- 服を着る順番
- 講義科目の履修順
などがある。アルゴリズムデザインの3.6章には
- グラフに対してトポロジカル順序付けできるなら、そのグラフは有向無閉路グラフ
- グラフが有向無閉路グラフであるならば、トポロジカル順序付けできる
という証明が与えられている。
# -*- coding: utf-8 -*- require 'pp' require 'set' class Graph def initialize(edges=[]) @edges = edges @nodes = Hash.new{|h,k| h[k] = []} end def add_edge(edge) @edges.push edge unless @edges.index(edge) end def add_node(u, v) if @edges.index(u).nil? @edges.push u elsif @edges.index(v).nil? @edges.push v end unless @nodes[u].index(v) @nodes[u].push v end end def topological_sort(edges = @edges, nodes = @nodes, result = []) diff = (edges - nodes.values.flatten.uniq) diff.each{|item| result.push item nodes.delete(item) } topological_sort(edges - diff, nodes, result) unless (edges - diff).empty? return result end end g = Graph.new g.add_node("a", "b") g.add_node("a", "c") g.add_node("b", "d") g.add_node("b", "e") g.add_node("c", "f") g.add_node("d", "c") g.add_node("e", "d") g.add_node("g", "f") pp g.topological_sort
/tmp% ruby hash_graph.rb ["a", "g", "b", "e", "d", "c", "f"]
服を着る順序とかだとこんな感じでできるからイメージしやすいかも。
g = Graph.new g.add_edge("watch") g.add_node("undershorts", "shoes") g.add_node("undershorts", "pants") g.add_node("pants", "shoes") g.add_node("socks", "shoes") g.add_node("pants", "belt") g.add_node("shirts", "belt") g.add_node("shirts", "tie") g.add_node("belt", "jacket") g.add_node("tie", "jacket") pp g.topological_sort
時計を付けて、…、ジャケットを着てという順序が再現されているのが分かる。
tmp% ruby hash_graph.rb ["watch", "undershorts", "socks", "shirts", "pants", "tie", "shoes", "belt", "jacket"]
アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)
- 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
- 出版社/メーカー: 近代科学社
- 発売日: 2013/12/17
- メディア: 大型本
- この商品を含むブログ (6件) を見る