トポロジカルソートのベンチマークらしきもの

離散最適化理論の課題を提出し終わったので、貼ってみるテスト。トポロジカルソートのためのところは前にちょちょいと書いたんですが

• 説明用の図
• 巨大なグラフを作る用の関数
• 計算時間をplotするための関数

などなどの付近も書いたので、貼ってみます。

例を使って説明する付近はruby-graphvizを使ってみたりしました。結構使いやすい。

あと、グラフのノード数とエッジ数を色々変えて実験しないといけなかったので、こんな感じのトポロジカルソートできそうな、でかいグラフを吐ける関数を用意しておきました。

グラフの計算時間はになるんですが

• エッジ数を固定、ノード数を動かす
• ノード数を固定、エッジ数を動かす
• 両方を動かす

の3種類の計算時間をplotしてみました。グラフ理論とかの計算量ってパラメータが2つになったりして、色々やりづらかったりするなーと思った。



id:reposeが書いたやつも添削っぽいことをしたいんだけど、時間を捻出できるか怪しくなってきた気がする。。。

以下ソースです。

# -*- coding: utf-8 -*-

require "rubygems"
require "graphviz"
require "pp"
require "set"

class Graph
  attr_reader :nodes
  attr_reader :edges
  def initialize(nodes=[])
    @nodes = nodes
    @edges = Hash.new{|h,k| h[k] = []}
  end
  
  def add_node(node)
    @nodes.push node unless @nodes.index(node)
  end
  
  def add_edge(u, v)
    if @nodes.index(u).nil?
      @nodes.push u
    end
    if @nodes.index(v).nil?
      @nodes.push v
    end
    
    unless @edges[u].index(v)
      @edges[u].push v
    end
  end

  def topological_sort(nodes = @nodes.to_set, edges = @edges.clone, result = []) 
    # function for topological sort
    # "clone" is for shallow copy, not deep copy
    diff = nodes - edges.values.flatten.uniq.to_set
    # 入ってくることがない枝をdiffに代入
    diff.each{|item|
      result.push item
      edges.delete(item)
      # グラフから削除
    }
    topological_sort(nodes - diff, edges, result) unless (nodes - diff).empty?
    # 入ってくることがない枝を取り除いたものに対して、再帰的にトポロジカルソートを適用
    return result
  end

  def convert2graphViz(option) 
    # function to plot the graph
    # option must be a hash
    g = GraphViz.new("G", option)
    @nodes.each{|node|
      g.add_node(node)
    }
    @edges.each_pair{|key, value|
      value.each{|item|
        g.add_edge(g.add_node(key), g.add_node(item))
      }
    }
    return g
  end
end

def make_graph_for_topological_sort(param)
  # make the random graph for topological sort 
  min = param[:min]
  max = param[:max]
  interval = param[:interval]
  add_node_param = param[:add_node_param]
  add_edge_param = param[:add_edge_param]

  g = Graph.new
  num = min
  while true
    g.add_node(num.to_s) if rand < add_node_param
    num += 1
    break if num > max
  end
  g.nodes.each{|i|
    g.nodes.each{|j|
      if i < j
        g.add_edge(i, j) if rand < add_edge_param
      end
    }
  }
  return g
end

# 服の例
g = Graph.new

g.add_edge("belt", "jacket")
g.convert2graphViz({:output => "png",
                     :file => "~/discrete_optimization_theory/graph/clothes8.png"}).output
g.add_node("shoes")
g.convert2graphViz({:output => "png",
                     :file => "~/discrete_optimization_theory/graph/clothes7.png"}).output
g.add_edge("tie", "jacket")
g.convert2graphViz({:output => "png",
                     :file => "~/discrete_optimization_theory/graph/clothes6.png"}).output
g.add_edge("pants", "belt")
g.add_edge("pants", "shoes")
g.convert2graphViz({:output => "png",
                     :file => "~/discrete_optimization_theory/graph/clothes5.png"}).output
g.add_edge("shirts", "belt")
g.add_edge("shirts", "tie")
g.convert2graphViz({:output => "png",
                     :file => "~/discrete_optimization_theory/graph/clothes4.png"}).output
g.add_edge("socks", "shoes")
g.convert2graphViz({:output => "png",
                     :file => "~/discrete_optimization_theory/graph/clothes3.png"}).output
g.add_edge("undershorts", "pants")
g.convert2graphViz({:output => "png",
                     :file => "~/discrete_optimization_theory/graph/clothes2.png"}).output
g.add_edge("undershorts", "shoes")
g.add_node("watch")
g.convert2graphViz({:output => "png",
                     :file => "~/discrete_optimization_theory/graph/clothes1.png"}).output

g.convert2graphViz({:output => "png",
                     :file => "~/discrete_optimization_theory/graph/clothes.png"}).output
puts "[#{g.topological_sort.join(", ")}]"


# 巨大なグラフのplot
g = make_graph_for_topological_sort({:min => 0, :max => 100,
                                  :add_node_param => 0.3,
                                  :add_edge_param => 0.2
                                })
g.convert2graphViz({:output => "png",
                     :file => "~/discrete_optimization_theory/graph/example.png"}).output

puts "=" * 30
puts "Edge数を固定、Node数を動かす"

f = File.open("/tmp/topological_sort_fixing_edge.csv", "w")

n = 20
max = 1000
(1..25).each{|x|
  mean_time = 0
  mean_nodes = 0
  mean_edges = 0
  n.times do 
    g = make_graph_for_topological_sort({:min => 0, :max => max,
                                          :add_node_param => 0.04 * x,
                                          :add_edge_param => 0.02 / x**2 
                                        })
    t = Time.now
    g.topological_sort
    mean_time += Time.now - t
    mean_nodes += g.nodes.length
    mean_edges += g.edges.values.flatten.length
  end
  str = "#{mean_nodes / n}, #{mean_edges / n}, #{mean_time / n}"
  puts str
  f.puts str
}
f.close

puts "=" * 30
puts "Node数を固定、Edge数を動かす"

f = File.open("/tmp/topological_sort_fixing_node.csv", "w")

n = 10
max = 1000
(1..25).each{|x|
  mean_time = 0
  mean_nodes = 0
  mean_edges = 0
  n.times do 
    g = make_graph_for_topological_sort({:min => 0, :max => max,
                                          :add_node_param => 0.5,
                                          :add_edge_param => 0.04 * x
                                        })
    t = Time.now
    g.topological_sort
    mean_time += Time.now - t
    mean_nodes += g.nodes.length
    mean_edges += g.edges.values.flatten.length
  end
  str = "#{mean_nodes / n}, #{mean_edges / n}, #{mean_time / n}"
  puts str
  f.puts str
}
f.close

puts "=" * 30
puts "Node数、Edge数を動かす"

f = File.open("/tmp/topological_sort.csv", "w")

n = 10
max = 1000
(1..10).each{|x|
  (1..10).each{|y|
    mean_time = 0
    mean_nodes = 0
    mean_edges = 0
    n.times do 
      g = make_graph_for_topological_sort({:min => 0, :max => max,
                                            :add_node_param => 0.1 * x,
                                            :add_edge_param => 0.01 * y
                                          })
      t = Time.now
      g.topological_sort
      mean_time += Time.now - t
      mean_nodes += g.nodes.length
      mean_edges += g.edges.values.flatten.length
    end
    str = "#{mean_nodes / n}, #{mean_edges / n}, #{mean_time / n}"
    puts str
    f.puts str
    puts "x #{x}, y #{y}"
  }
}
f.close