読者です 読者をやめる 読者になる 読者になる

グラフを扱うためのライブラリを覗いてみる

アルゴリズム グラフ理論 Ruby

グラフの勉強だけじゃなくてRubyの勉強にもなりそうなソースだなーと思ったので、メモしておく。ファイルは2つとなっていて把握しやすい。

  • graph.rb
  • graph_algorithm.rb

graph.rb

  • module Graphとclass DirectedHashGraph、DirectedHashGraphを拡張したclass UndirectedHashGraphからなっている
  • each_vertexメソッドは、グラフの各頂点に対して操作を繰り返す
    • どういう操作かは自分でブロックを渡せる

定義はこんな感じになっている。

  def each_vertex(&block)
    for v, n in @vertices
      block.call(v)
    end
  end

@verticesはHashになっていて、forで回しているのは

each_pair{|key, value|}

と同じような感じ。blockはfunctionみたいなものだからそれをcallすることができる。

  • each_successing_vertexメソッドは引数にvとblockを渡せて面白い感じ
    • vを始点とする全ての辺の終点に対してある操作繰り返す
  def each_successing_vertex(v, &block)
    assure(v)
    @weights[v].each_key do |w|
      block.call(w)
    end
  end

終点となるような点はブロックの中の引数にしてあげるとよい。例えば1から出ていく頂点を出力していきたい、というような場合には

g.each_successing_vertex(1){|v|
  pp v
}

という感じで操作ができる。あとでdebugするときとかに簡単になって、いいなー。実装はこんな感じ。

  def each_successing_vertex(v, &block)
    each_vertices() do |w|
      block.call(w) if adjacent?(v, w)
    end
  end

あとassureってメソッドが何やってるか気になったので見てみることにした。vから出て行く枝にウエイトがない(枝が何もない状態)だったときにdefault(ここではnil)を付けておく、というような操作のようだ。俺の場合はinitializeでそれを「assure」してたかな。

  def assure(v)
    @weights[v]= Hash.new(parameter(:default)) if !@weights.has_key?(v)
  end
  • each_edgeメソッドはグラフの各辺に対して繰り返す
  • こんな感じ
g.each_edge{|u,v|
  puts "#{u} -> #{v}"
}

実装はこんな感じ。Hashをeachしていって、という感じでそのままな感じ。

  def each_edge(uniq= false, &block)
    i= 0
    each_vertex() do |v|
      j= 0
      each_vertex() do |w|
        block.call(v, w) if (!uniq || directed?() || j>=i) && adjacent?(v, w)
        j+= 1
      end
      i+= 1
    end
  end

module Graph

  • include(GraphAlgorithm)している
    • graph.rbのほうには構造に関するメソッドの類を記述するようにしているようで、アルゴリズムに関する部分はgraph_algorithm.rbに書いてあるようだ
  • includeするとそれがあたかも書いてあるかのようにできるらしい
    • だからmaximum_flowはmodule Graphに書いてないのにg.maximum_flowとかができるようになっている
    • 曖昧な知識

モジュールは「クラスAを継承してクラスBを作った。クラスBの提供する多くの機能を持つクラスCを作りたいが、意味的にクラスCがクラスBを継承するのは不自然」というようなケースで使用すると便利です。つまり、クラスCでも使用したいクラスBの機能をモジュールとして括りだし、クラスCからinlcudeするわけです。このことを、Mix-inと呼びます。モジュールを使用するとクラスの継承関係を縦断した機能追加を、よりスムーズに行うことができます。

http://www.namaraii.com/rubytips/?%A5%E2%A5%B8%A5%E5%A1%BC%A5%EB


graph_algorithm.rb

グラフの構造とは別にグラフに対するアルゴリズムをまとめたファイル。GraphAlgorithmHelperとGraphAlgorithmからなる。

  • 幅優先探索
  • 深さ優先探索
  • ダイクストラ法による最短路検索
  • warshall_floyd_shortest_paths(よく知らない)
  • 流量を最大にするようなpathを求める(maximum_flow)
  • グラフをGraphvizのDOT形式で出力

というメソッドが主なもの。

module GraphAlgorithm

  • depth_first_searchとかに渡す引数はHash