グラフを木分解します。
…。
木分解。わたしもひと月前まで聞いたこともありませんでした。
木分解とは。おおざっぱに言うと、グラフからルールに従って部分グラフの集合を取り出し、その部分グラフを木構造のノードとする木を作ること。
くわしいことはこことかを参照してみてください。
なぜこのようなことをやっているかというと。仕事でアルゴリズムの実装というのを引き受けまして。これがグラフ理論の論文でして。このひと月ほど集中的にグラフ理論の勉強をしているとこでして。
そのアルゴリズムの実装に木分解が必要になり、木分解のアルゴリズムのひとつである最小次数法というのを実装してみた次第。
Graph
クラスを定義した graph.rb を用意します。
require 'Set' class Graph attr_reader :edges, :vertices def initialize @edges = {} @vertices = Set.new end def add_vertex(v) @vertices.add(v) end def delete_vertex(v) @edges.each do |vertex, edge| edge.delete(v) end @edges.reject! do |vertex, edge| edge.empty? end @edges.delete(v) @vertices.delete(v) end def delete_edge(v1, v2) @edges[v1].delete(v2) @edges[v2].delete(v1) end def add_edge(v1, v2) @edges[v1] ||= Set.new @edges[v1].add(v2) @edges[v2] ||= Set.new @edges[v2].add(v1) vertices.add(v1).add(v2) end end
木分解をする tree-decomposition.rb を用意。
require './graph' # 木分解するグラフの準備 g = Graph.new g.add_edge(1, 2) g.add_edge(1, 4) g.add_edge(2, 3) g.add_edge(2, 4) g.add_edge(2, 5) g.add_edge(3, 4) g.add_edge(4, 5) g.add_edge(4, 7) g.add_edge(5, 6) g.add_edge(5, 8) g.add_edge(5, 9) g.add_edge(6, 9) g.add_edge(7, 8) g.add_edge(7, 10) g.add_edge(8, 9) # 木分解の結果を格納する木 tree = Graph.new # 最小次数法を使って木分解する adj_v = nil nodes = [] n0 = g.vertices tree.add_vertex(:n0) while adj_v != g.vertices do # 次数が最小の頂点を選ぶ vi = g.vertices.min { |v1, v2| g.edges[v1].size <=> g.edges[v2].size } # 該当する頂点に隣接する頂点の集合 adj_v = g.edges[vi] # 該当する頂点と隣接する頂点からなる集合を木分解のノードにする ni = adj_v.dup.add(vi) tree.add_edge(:n0, ni) # 該当する頂点をグラフから取り除く g.delete_vertex(vi) # 該当する頂点の集合に対して完全グラフを作る adj_v.each do |source| adj_v.each do |target| if source != target g.add_edge(source, target) end end end # 既にあるノードが今回分解したノード ni によって最初のノード n0 と # 分離したら、ブランチを ni とのあいだに付け替える nodes.each do |n| if (! ((ni & n) - n0).empty?) && (tree.edges[n].include?(:n0)) tree.delete_edge(n, :n0) tree.add_edge(n, ni) end end # 分解済みのノードの一覧に追加 nodes << ni end # これ以上分解する要素がなくなったノード n0 を取り除く tree.delete_vertex(:n0) # 結果の出力 puts "# vertices" tree.vertices.each do |v| puts "- [ #{v.to_a.join(', ')} ]" end puts "---" puts "# edges" tree.edges.each do |v, e| puts "- #{v.to_a}: #{e.map(&:to_a)}" end
ここで用意しているグラフは上で参照してくださいと言った資料の中にある次のようなグラフです。
実行。
$ ruby tree-decomposition.rb # vertices - [ 7, 10 ] - [ 2, 4, 1 ] - [ 2, 4, 3 ] - [ 4, 5, 2 ] - [ 5, 7, 4 ] - [ 8, 5, 7 ] - [ 5, 9, 6 ] - [ 8, 9, 5 ] --- # edges - [7, 10]: [[8, 5, 7]] - [2, 4, 1]: [[4, 5, 2]] - [2, 4, 3]: [[4, 5, 2]] - [4, 5, 2]: [[2, 4, 1], [2, 4, 3], [5, 7, 4]] - [5, 7, 4]: [[4, 5, 2], [8, 5, 7]] - [8, 5, 7]: [[7, 10], [5, 7, 4], [8, 9, 5]] - [5, 9, 6]: [[8, 9, 5]] - [8, 9, 5]: [[8, 5, 7], [5, 9, 6]]
vertices 以下の8つの集合が木のノードです(ひとつのノードがグラフの複数の頂点を含んでいます)。
edges 以下がそれぞれのノードをつなぐブランチです。
わかりにくいと思うので。結果を図示。こんな感じ。木のノードが元のグラフの部分グラフになっています。
グラフ理論とわたし
趣味と言えるほどではないものの。ときどき数学の読み物を読んだりします。グラフ理論は本格的に学んだ覚えがないのですが、グラフ理論に触れるようなネタはプログラミングしたことがあります。
たとえば、これ。
…。本当に「ネタ」じゃないか orz 。