【自作Rubyライブラリ】Union-Find木

自作Rubyライブラリ

作っていこうと思った。
連載シリーズモノにしたい。

お題

今回はUnion-Find Treeを作る。
詳しいのは秋葉さんのスライドかしら？

実装

#
# Union-Find Tree's Node
#
class Node
  attr_accessor :parent, :rank
  def initialize(n)
    @parent = n
    @rank = 0
  end
end

#
# Union-Find Tree
#
class UnionFindTree
  def initialize(n)
    @nodes = (0..n).map { |i| Node.new(i) }
  end

  def unite(a, b)
    pa = find(a)
    pb = find(b)
    return if pa == pb

    if @nodes[pa].rank < @nodes[pb].rank
      @nodes[pb].parent = pa
    else
      @nodes[pa].parent = pb
      @nodes[pa].rank += 1 if @nodes[pa].rank == @nodes[pb].rank
    end
  end

  def same?(a, b)
    find(a) == find(b)
  end

  def find(x)
    return x if @nodes[x].parent == x
    @nodes[x].parent = find(@nodes[x].parent)
  end
end

参考

とあるブログを参考にしたのだけど、その実装だとテストが通らなかったからuniteを直した。
あとrubocopセンセイにredundantなreturnがあるよと言われたのでそれも直した。 リンクを貼るべきだと思うが、誤っていると思っているので参考リンクは貼らないことにする。

雑感

Rubyだと特に返したいわけでもない値がかえってしまうが、
戻り値に特に意味のないメソッドにおいてもどのパスでも同じ意味の値を返すようにしたほうがいいんだろうか
たとえばuniteではあるパスでは始祖ノードの値が、あるパスでは変更後のrankが返ったりしている。
まあ戻り値に意味がないつもりで書いてはいるのだけど。

rspecとか使ってちゃんとテストも一緒にあげたい。
そういうことをしようとするとGitHubになるんだろうか

その後

twitterにて疑問に答えてもらった(ありがとうございます