最大出次数を最小にする順序/Rubyのpriority queue

kousuke.hatenablog.com

以前、この記事で最大出次数を最小にする順序は難しいかもと書いたけどできるらしい。

Degeneracy (graph theory) - Wikipedia

アルゴリズムも載っていたのだけれど、優先度を変更できる優先度付キューをつかうと簡単にできそうだった。


Rubyの優先度付キューを探してみると標準では優先度付キューはないようだ。lazy priority quueuというgemがあって、この中でベンチマークがある。

github.com

優先度変更がなくてよいならPriorityQueueCxx、 変更有りならsupertinou/PriorityQueue、どちらもC++ extensionなので、Pure Rubyならlazy_priority_queueがよいよとのこと。

サンプルやコードを見ていると、なるほど優先度を高くする方向(min heapでは、値としては下がる方向)はサポートできるみたいな感じっぽい。

ヒープのデータ構造に違いがあり、lazy_priority_queueは2項ヒープとのこと、フィボナッチヒープと比べると、フィボナッチヒープの方が平均的には早いけど、ワースト時間で遅いものがあるみたいな感じっぽい。さきのC++拡張の2つともフィボナッチヒープ。

二項ヒープ - Wikipedia

フィボナッチヒープ - Wikipedia

多分2007年度の卒業論文(学部生)じゃないかと思うんだけど、グラフの彩色アルゴリズムの内容も基本的にはk-degenerationグラフの順序を求めているのと一緒だった。強いてあげるならば、なるべく次数降順に並ぶように順序を決めていた。

自分としてはここに安定結婚問題をもってきたいとおもっていて、適当につくったのが、結構いい値がでてて、精度保障できないかなとか思ってるけど、全然証明とかできない。

貪欲法と違うのは基本的に1色で塗れるだけ塗るというのをやってる。安定結婚問題に合わせて色を男性、頂点を女性とすると、貪欲法だと女性優先で、下記のコードだと男性優先なんじゃないかとおもっているが実際には貪欲法と変わらない。なんというか、うまいこと頂点毎の順序や色ごとの順序つくれないかなとおもっている。なんで安定結婚問題でやりたいかといえば、マッチングの質に関しての研究が進んでいるからというのが理由。意外と順序決めるのが早かったりしないかなとおもっている。

#!/usr/bin/env ruby
require 'lazy_priority_queue'
require 'optparse'

def degeneracy_order(graph, vset)
  q = MinPriorityQueue.new
  k = 0
  order = []
  used = {}
  d = {}
  vset.each do |v|
    dv = graph[v].size
    d[v] = dv
    q.push v, dv
  end
  until q.empty?
    v = q.dequeue
    used[v] = true
    k = d[v] if d[v] > k
    order << v
    graph[v].each do |u|
      d[u] -= 1
      unless used[u]
        q.change_priority u, d[u]
      end
    end
  end
  order.reverse
end

def build_graph(vset, eset)
  graph = {}
  vset.each do |v|
    graph[v] = []
  end
  eset.each do |u,v|
    graph[v] << u
    graph[u] << v
  end
  graph
end

def gs_coloring(graph, vset_order)
  match = {}
  c = -1
  until vset_order.empty?
    c += 1
    vset_order.reject! do |v|
      if graph[v].none?{|u| match[u] == c }
        match[v] = c
      end
      match[v]
    end
  end
  [c + 1, match]
end

opt_result = false

opt = OptionParser.new
opt.on('-r','print result.'){ opt_result = true }
opt.parse!(ARGV)

n,m = gets.split.map(&:to_i)

V = n.times.to_a
E = m.times.map{ gets.split.map(&:to_i) }

G = build_graph(V,E)
vset_order = degeneracy_order(G, V)
number, result = gs_coloring(G, vset_order)

puts number
puts V.map {|v| "#{v} #{result[v]}" } if opt_result