トポロジカル順序付け

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