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

Ruby で Tree構造(その2)

前に Ruby で Tree 構造を作る記事(参照)を書きましたが、もう少し汎用的に使えるものを作ってみました。

tree.rb

class Node
end

class Tree
  class Branch
    def initialize(parent)
      @parent = parent    #Node:親
      @children = []      #Array:子(要素はNode)
    end
    attr_accessor :parent, :children
  end
  
  class Something
  end
  
  def initialize(root)
    @root = root      #node
    @node = [root]    #Array:ノード(要素は Node)
    @lh = {root=>Branch.new(nil)}    #Hash:枝(Node=>Branch)
  end
  attr_reader :root

  #配列arで一気にTreeを作る
  def self.make(ar)
    raise "Argument is not Array." if ar.class != Array
    t = Tree.new(ar[0][0])
    ar.each do |ar1|
      ar1[1].each {|child| t.add(ar1[0], child)}
    end
    t
  end
  
  #tree図示(半角でないと表示がズレる)
  def put_out
    d = -1; st = ""
    ar = []
    dfs(@root) do |node, depth|
      lfs = "-- #{node} "
      if d < depth
        st += lfs
	ar.push(st.length)
	print lfs
	d = depth
      else
	l = ar[depth - 1]
	st = " " * l + lfs
	print("\n" + st)
	ar[depth] = st.length
	d = depth
      end
    end
    puts
  end
  
  #nodeに新しい子どもを付加する
  def add(node, newchild)
    raise "Already newchild exists." if @node.include?(newchild)
    @node << newchild
    raise "Parent #{node} does not exist." unless @lh[node]
    @lh[node].children << newchild
    @lh[newchild] = Branch.new(node)
  end
  
  #node以下を再帰的に消去
  def delete(node)
    raise "can not delete: no node" unless @node.include?(node)
    @lh[get_parent(node)].children.delete(node)
    delete1(node)
  end
  
  def delete1(node)
    ar = get_children(node)
    ar.each {|child| delete1(child)} unless ar.empty?
    @node.delete(node)
    @lh.delete(node)
  end
  private :delete1
  
  #node以下を新たな木としてTreeを作る
  def copy_tree(node)
    tree = Tree.new(node)
    dfs(node) do |nd|
      get_children(nd).each {|child| tree.add(nd, child)}
    end
    tree
  end
  
  #node以下に別の木treeを付加する
  def merge(node, tree)
    add(node, (tr = tree.root))
    tree.dfs(tr) do |nd|
      tree.get_children(nd).each {|child| add(nd, child)}
    end
  end
  
  #nodeをnewnodeで置き換える
  def replace(node, newnode)
    return if node == newnode
    @root = newnode if @root == node
    raise "Already newnode exists." if @node.include?(newnode)
    raise "Node does not exist." unless (num = @node.index(node))
    @lh[newnode] = @lh[node]
    a = @lh[get_parent(node)]
    a.children.map! {|i| (i == node) ? newnode : i} if a
    get_children(node).each {|child| @lh[child].parent = newnode}
    @lh.delete(node)
    @node[num] = newnode
  end
   
  #node a と b を入れ替える
  def exchange(a, b)
    raise "Argument does not exist." if !@node.include?(a) or !@node.include?(b)
    return if a == b
    x = Something.new
    replace(a, x); replace(b, a); replace(x, b)
  end
  
  #node a以下と b以下を再帰的に交換する
  def exchange_r(a, b)
    raise "Argument does not exist." if !@node.include?(a) or !@node.include?(b)
    return if a == b
    t1 = copy_tree(a)
    t2 = copy_tree(b)
    pa = get_parent(a)
    pb = get_parent(b)
    raise "Root can not recursive exchenge." if !pa or !pb
    delete(a)
    delete(b)
    merge(pa, t2)
    merge(pb, t1)
  end
  
  #nodeが存在すればtrue、しなければfalse
  def exist?(node)
    @node.include?(node)
  end
  
  #node以下で最も深い相対的深さを返す(@rootは入れない)
  def max_depth(node)
    max = 0
    bfs(node) {|nd, d| max = d if max < d}
    max
  end
  
  #startからgoalまでのnodeの経路を配列に入れて返す
  def get_nodes(start, goal)
    ar = [goal]
    return ar if start == goal
    node = get_parent(goal)
    until node == start 
      ar.unshift(node)
      node = get_parent(node)
    end
    ar.unshift(start)
    ar
  end
  
  #nodeの親nodeを返す
  def get_parent(node)
    @lh[node].parent
  end
  
  #nodeの子供たちnodeをArrayで返す
  def get_children(node)
    @lh[node].children
  end
  
  #深さ優先探索。見つければ相対的な階層数を返し、見つからなければfalseを返す。ブロックがあればトラバースする。
  #トラバースの引数は |node, depth|。ただしdepthは相対的な深さで、省略可能。
  def dfs(start, goal=nil)
    q = [[start, 0]]
    while !q.empty?
      node, depth = q.pop
      yield(node, depth) if block_given?
      return depth if node == goal
      get_children(node).reverse_each do |child|
	q.push([child, depth + 1])
      end
    end
    false
  end
  
  #幅優先探索。見つければ相対的な階層数を返し、見つからなければfalseを返す。ブロックがあればトラバースする。
  #トラバースの引数は |node, depth|。ただしdepthは相対的な深さで、省略可能。
  def bfs(start, goal=nil)
    q = [[start, 0]]
    while !q.empty?
      node, depth = q.shift
      yield(node, depth) if block_given?
      return depth if node == goal
      get_children(node).each do |child|
	q.push([child, depth + 1])
      end
    end
    false
  end
end



使い方

Node のクラスは何でもいいです。インスタンスのクラスは何でも(別に Node でなくとも)かまいません。

 t = Tree.new(:root)

まず Tree を作ります。引数はルート(最上部)になり、ここでは Symbol である :root にしました(別に例えば 1 でもかまいません)。

t.add(:root, "nya"); t.add(:root, "fnyanya")
t.add("nya", 4)
t.add("fnyanya", 5)
t.add(:root, 6)
t.add(6, 7)
t.add("fnyanya", "nora"); t.add("nora", "konora")

t.put_out

Tree#add(a, b) で、aに子供bを追加していきます(bが Tree に既に存在する場合は追加できません)。Tree#put_out で木を表示します(Node の出力が半角英数でないと、表示がズレます)。

-- root -- nya -- 4 
        -- fnyanya -- 5
                   -- nora -- konora 
        -- 6 -- 7 

こんな感じです。

p t.bfs(:root, 7)    #=>2
p t.bfs("nora", :root)    #=>false

Tree#bfs(start, goal) は、幅優先探索でstartからgoalを探します。見つかれば相対的な深さを返し、見つからなければfalseを返します。
Tree#bfs(start) {|node, depth| ...} は、startから幅優先探索でnodeを順にトラバースします。depthは相対的な深さで、省略可能です。

t.dfs(:root) {|node, d| p [node, d]}

#[:root, 0]
#["nya", 1]
#[4, 2]
#["fnyanya", 1]
#[5, 2]
#["nora", 2]
#["konora", 3]
#[6, 1]
#[7, 2]

Tree#dfs(start, goal) と Tree#bfs(start) {|node, depth| ...} は深さ優先探索で、後は Tree#bfs と同じです。

t.delete("fnyanya")
t.replace(6, "nyoro")
t.get_parent("nya")    #=>:root
t.get_children("fnyanya")    #=>[5, "nora"]
t.get_nodes(:root, "konora")    #=>[:root, "fnyanya", "nora", "konora"]
t.exchange("nora", 6)
t.exist?("nora")

Tree#delete(node) はnode以下を再帰的に消去します。Tree#replace(a, b) は a を b に置き換えます。Tree#get_parent(node) は親nodeを与えます。Tree#get_children は子供たちの入った Array を返します。Tree#get_nodes(start, goal) は startからgoalまでのnodeの経路を配列に入れて返します(必ず到達できる必要があります)。Tree#exchange(a, b) はノード a と b を交換します。Tree#exist?(node) は node が存在すればtrue、存在しなければfalseを返します。

t.copy_tree("fnyanya")
t.merge(node, tree)

Tree#copy_tree(node) は node 以下を新しい Tree として生成します。
Tree#merge(node, tree) は、node の下に tree をマージします。

t.max_depth(node)

Tree#max_depth(node) は node 以下の最も深い相対的な深さを与えます。

ar = [[:root, ["nya", "fnyanya", 6]], ["nya", [4]], ["fnyanya", [5, "nora"]],
    ["nora", ["konora"]], [6, [7]]]
t = Tree.make(ar)
t.put_out

Tree.make(ar) は、配列で Tree を一気に作ります。この例は上のと同じ Tree を作ります。子供は親が登場したあとに与えられるよう、配列の順序に気をつけて下さい。