読者です 読者をやめる 読者になる 読者になる

トポロジカル順序付け

アルゴリズム Ruby

トポロジカル順序付けは有向無閉路グラフ(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教科書)

アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)

  • 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
  • 出版社/メーカー: 近代科学社
  • 発売日: 2013/12/17
  • メディア: 大型本
  • この商品を含むブログ (6件) を見る