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

index

グラフの勉強だけじゃなくて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