エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

グラフの木分解〜グラフ理論とわたし

グラフを木分解します。

…。

木分解。わたしもひと月前まで聞いたこともありませんでした。
木分解とは。おおざっぱに言うと、グラフからルールに従って部分グラフの集合を取り出し、その部分グラフを木構造のノードとする木を作ること。

くわしいことはこことかを参照してみてください。

なぜこのようなことをやっているかというと。仕事でアルゴリズムの実装というのを引き受けまして。これがグラフ理論の論文でして。このひと月ほど集中的にグラフ理論の勉強をしているとこでして。
そのアルゴリズムの実装に木分解が必要になり、木分解のアルゴリズムのひとつである最小次数法というのを実装してみた次第。

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 。

いつか読むはずっと読まない:グラフ理論の本

自分で買ったグラフ理論関係の唯一の本。
現代数学小事典」のようにグラフ理論も載っている本というのは他にもあるんですが、グラフ理論の本としては、わたしが持ってるのはたぶんこれだけ。
…。持ってるだけでこれも積ん読山脈に埋もれているのですが…。

最短経路の本 レナのふしぎな数学の旅

最短経路の本 レナのふしぎな数学の旅