【Ruby】【アルゴリズム】ガーベジコレクション。多重配列を使わないグラフ構造。キューを使用したVer。

　
昨日は多重配列を用いずにグラフ構造を表現する方法を学んだので、
この知識を使って、以前実装したガーベッジコレクションのコードをより良くする。
　
より良く！

以前の奮闘振りはこちら↓
http://sekai.hateblo.jp/entry/2013/09/27/223134

問題

状態、'0'および、'A'～'I'に対して、
以下の状態遷移が定義されているとする。
'0'→'A'
'A'→'B'
'B'→'C'
'C'→'B'
'C'→'A'
'D'→'B'
'D'→'H'
'H'→'D'
'E'→'F'
'F'→'G'
'G'→'F'
'G'→'E'
'I'→'I'
この状態遷移は間違っており、遷移しない状態が存在する。
遷移しない状態を求めるプログラムを作成せよ。
ここで、'0' は開始状態である。

http://d.hatena.ne.jp/a-san/20090623/p1

ポイント

グラフ情報を多重配列ではなく、一次元配列で持つ

[#<Node:0x320cd30 @id=:start, @reachbles=[:A], @reached=false>, #<Node:0x320ccb8 @id=:A, @reachbles=[:Banana], @reached=false>, #<Node:0x320cc40 @id=:Banana, @reachbles=[:Car], @reached=false>, #<Node:0x320cbc8 @id=:Car, @reachbles=[:Banana, :A], @reached=false>, #<Node:0x320cb08 @id=:D, @reachbles=[:Banana, :H], @reached=false>, #<Node:0x320ca48 @id=:H, @reachbles=[:D], @reached=false>, #<Node:0x320c9d0 @id=:E, @reachbles=[:F], @reached=false>, #<Node:0x320c958 @id=:F, @reachbles=[:G], @reached=false>, #<Node:0x320c8e0 @id=:G, @reachbles=[:F, :E], @reached=false>, #<Node:0x320c820 @id=:I, @reachbles=[:I], @reached=false>]

　
未検査のものの検査は、キューを使う。

check_waiting_que = [start_node]
i = 0
while i < check_waiting_que.length
  check_waiting_que[i].reachbles.each do |reachble|
    reachble_node = @nodes.find{|node| node.id == reachble }
    check_waiting_que << reachble_node if !reachble_node.reached
  end
  check_waiting_que[i].reached = true
  i += 1
end

Array#selectを初めて使ったかも。便利。
　
　

コード全量

ガーベジコレクション後のメモリの状態も出力してみました。

DATA =[
  [:start, :A],
  [:A, :Banana],
  [:Banana, :Car],
  [:Car, :Banana],
  [:Car, :A],
  [:D, :Banana],
  [:D, :H],
  [:H, :D],
  [:E, :F],
  [:F, :G],
  [:G, :F],
  [:G, :E],
  [:I, :I]
]
class Node
  def initialize(id, reachbles)
    @id, @reachbles, @reached = id, [reachbles], false
  end
  attr_accessor :id, :reachbles, :reached
end
class MemorySpace
  def initialize(data)
    @nodes = []
    data.each do |element|
      node = @nodes.find{|node| node.id == element[0] }
      if node.nil?
        @nodes << Node.new(*element) 
      else
        node.reachbles << element[1]
      end
    end
   p @nodes
  end
  def garbage_collection
    start_node = @nodes.find{|node| node.id == :start }
    check_waiting_que = [start_node]
    i = 0
    while i < check_waiting_que.length
      check_waiting_que[i].reachbles.each do |reachble|
        reachble_node = @nodes.find{|node| node.id == reachble }
        check_waiting_que << reachble_node if !reachble_node.reached
      end
      check_waiting_que[i].reached = true
      i += 1
    end
    old_nodes = @nodes.dup
    @nodes.select!{|node| node.reached}
    #return garbage
    old_nodes.select{|node| !node.reached }.map{|node| node.id }
  end
  def show
    @nodes.each do |node|
      node.reachbles.each{|reachble| puts "[#{node.id}, #{reachble}]"}
    end
  end
end

memory_space = MemorySpace.new(DATA)
garbage = memory_space.garbage_collection
p garbage
p "----"
memory_space.show

　
■実行結果

[:D, :H, :E, :F, :G, :I]
"----"
[start, A]
[A, Banana]
[Banana, Car]
[Car, Banana]
[Car, A]