Tree Drawing Algorithm Test

drawtree.rb

require 'opengl'
require 'glfw'
require_relative 'lib/nanovg'

require_relative 'tree'

OpenGL.load_lib()
GLFW.load_lib()
NanoVG.load_dll('libnanovg_gl3.dylib', render_backend: :gl3)

include OpenGL
include GLFW
include NanoVG

key = GLFW::create_callback(:GLFWkeyfun) do |window, key, scancode, action, mods|
  if key == GLFW_KEY_ESCAPE && action == GLFW_PRESS # Press ESC to exit.
    glfwSetWindowShouldClose(window, GL_TRUE)
  end
end

$vg = nil
$offset_x = 128 / 2
$offset_y = 50.0
$scale_x = 50.0
$scale_y = 100.0

def draw_node_nvg(node)
  color = nvgRGBA(128,128,0, 255)
  nvgBeginPath($vg)
  nvgCircle($vg, $offset_x + node.x * $scale_x, $offset_y + node.y * $scale_y, 20.0)
  nvgStrokeColor($vg, color)
  nvgStrokeWidth($vg, 5.0)
  color = nvgRGBA(128,255,0, 255)
  nvgFillColor($vg, color)
  nvgFill($vg)
  nvgStroke($vg)
end

def draw_branch_nvg(node_child, node_parent)
  color = nvgRGBA(255,128,64, 255)
  nvgLineCap($vg, NVG_ROUND)
  nvgLineJoin($vg, NVG_ROUND)
  nvgBeginPath($vg)
  nvgMoveTo($vg, $offset_x + node_child.x * $scale_x, $offset_y + node_child.y * $scale_y)
  nvgLineTo($vg, $offset_x + node_parent.x * $scale_x, $offset_y + node_parent.y * $scale_y)
  nvgClosePath($vg)
  nvgStrokeColor($vg, color)
  nvgStrokeWidth($vg, 10.0)
  nvgStroke($vg)
end

$tree = Tree.new(Node.new("Top",
                          Node.new("0L",
                                   Node.new("0L1L",
                                            Node.new("0L1L2L",
                                                     Node.new("0L1L2L3L",
                                                              Node.new("0L1L2L3L4L"),
                                                              Node.new("0L1L2L3L4R")),
                                                     nil),
                                            Node.new("0L1L2R")),
                                   Node.new("0L1R")),
                          Node.new("0R",
                                   Node.new("0R1L"),
                                   Node.new("0R1R",
                                            Node.new("0R1R2L",
                                                     Node.new("0R1R2L3L"),
                                                     Node.new("0R1R2L3R")
                                                    ),
                                            nil))))

if __FILE__ == $0

  if glfwInit() == GL_FALSE
    puts("Failed to init GLFW.")
    exit
  end

  # Mac OS X
  glfwWindowHint(GLFW_OPENGL_FORWARD_COMPAT, GL_TRUE)
  glfwWindowHint(GLFW_OPENGL_PROFILE, GLFW_OPENGL_CORE_PROFILE)
  glfwWindowHint(GLFW_CONTEXT_VERSION_MAJOR, 4)
  glfwWindowHint(GLFW_CONTEXT_VERSION_MINOR, 1)

  caption = "Draw Tree"
  if ARGV[0] == nil || ARGV[0] == "-knuth"
    caption += " (Knuth)"
  elsif ARGV[0] == "-ws"
    caption += " (Wetherell and Shannon)"
  elsif ARGV[0] == "-rt"
    caption += " (Reingold and Tilford)"
  end

  window = glfwCreateWindow( 1280, 720, caption, nil, nil )
  if window == 0
    glfwTerminate()
    exit
  end

  glfwSetKeyCallback( window, key )

  glfwMakeContextCurrent( window )

  nvgSetupGL3()
  $vg = nvgCreateGL3(NVG_ANTIALIAS | NVG_STENCIL_STROKES)
  if $vg == nil
    puts("Could not init nanovg.")
    exit
  end

  winWidth_buf  = ' ' * 8
  winHeight_buf = ' ' * 8
  fbWidth_buf  = ' ' * 8
  fbHeight_buf = ' ' * 8

  glfwSwapInterval(0)
  glfwSetTime(0)

  if ARGV[0] == nil || ARGV[0] == "-knuth"
    $tree.algorithm = KnuthTreeLayout.new
  elsif ARGV[0] == "-ws"
    $tree.algorithm = WetherellShannonMinWidthTreeLayout.new
  elsif ARGV[0] == "-rt"
    $tree.algorithm = ReingoldTilfordTreeLayout.new
  else
    $tree.algorithm = KnuthTreeLayout.new
  end
  $tree.calculate_layout
  draw_ctx = DrawContext.new
  draw_ctx.on_draw_node = method(:draw_node_nvg).to_proc
  draw_ctx.on_draw_branch = method(:draw_branch_nvg).to_proc

  while glfwWindowShouldClose( window ) == 0
    glfwGetWindowSize(window, winWidth_buf, winHeight_buf)
    glfwGetFramebufferSize(window, fbWidth_buf, fbHeight_buf)
    winWidth = winWidth_buf.unpack('L')[0]
    winHeight = winHeight_buf.unpack('L')[0]
    fbWidth = fbWidth_buf.unpack('L')[0]
    fbHeight = fbHeight_buf.unpack('L')[0]

    pxRatio = fbWidth.to_f / winWidth.to_f

    glViewport(0, 0, fbWidth, fbHeight)
    glClearColor(0.8, 0.8, 0.8, 1.0)
    glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT|GL_STENCIL_BUFFER_BIT)

    nvgBeginFrame($vg, winWidth, winHeight, pxRatio)
    nvgSave($vg)

    # render something here
    $tree.draw(draw_ctx)

    nvgRestore($vg)
    nvgEndFrame($vg)

    glfwSwapBuffers( window )
    glfwPollEvents()
  end

  nvgDeleteGL3($vg)

  glfwTerminate()

end

tree.rb

class Node
  attr_reader :left, :right, :name
  attr_accessor :x, :y

  def initialize(name = nil, left = nil, right = nil)
    @name = name
    @left = left
    @right = right

    @x = -1
    @y = -1
  end

  def leaf?
    return @left == nil && @right == nil
  end

  def to_array_recursive(node, out)
    out << self
    to_array_recursive(node.right, out) if node.right != nil
    to_array_recursive(node.left, out) if node.left != nil
  end

  def to_array()
    nodes = []
    to_array_recursive(self, nodes)
    return nodes
  end

end

class LayoutContext
  attr_accessor :i, :node
  def initialize(i, node)
    @i = i
    @node = node
  end
end

class DrawContext
  attr_reader :i, :node
  attr_accessor :on_draw_node, :on_draw_branch

  def on_draw_node_default(node)
    puts "Draw node #{node.name}'s circle at (#{node.x}, #{node.y})"
  end

  def on_draw_branch_default(node_child, node_parent)
    puts "Draw branch from (#{node_child.x}, #{node_child.y}) to (#{node_parent.x}, #{node_parent.y})"
  end

  def initialize(on_draw_node_method = nil, on_draw_branch_method = nil)
    @on_draw_node   = on_draw_node_method == nil ? method(:on_draw_node_default).to_proc : on_draw_node_method
    @on_draw_branch = on_draw_branch_method == nil ? method(:on_draw_branch_default).to_proc : on_draw_branch_method
  end
end

class Tree
  attr_accessor :root, :algorithm

  def initialize(root = nil)
    @root = root
    @algorithm = nil
  end

  def calculate_layout
    ctx = LayoutContext.new(0, @root)
    return @algorithm.layout(ctx, @root, 0)
  end

  def draw(ctx)
    draw_recursive(ctx, @root)
  end

  def draw_recursive(ctx, node)
    ctx.on_draw_node.call(node)
    if node.left != nil
      draw_recursive(ctx, node.left)
      ctx.on_draw_branch.call(node.left, node)
    end
    if node.right != nil
      draw_recursive(ctx, node.right)
      ctx.on_draw_branch.call(node.right, node)
    end
  end
  private :draw_recursive

  def to_array
    return @root.to_array
  end
end

####################################################################################################

# Ref.: http://billmill.org/pymag-trees/

class KnuthTreeLayout
  def layout(ctx, node, depth)
    if node.left != nil
      layout(ctx, node.left, depth+1)
    end
    node.x = ctx.i
    node.y = depth
    ctx.i += 1
    if node.right != nil
      layout(ctx, node.right, depth+1)
    end
  end
end

class WetherellShannonMinWidthTreeLayout
  def initialize(depth_max = 10)
    @depth_max = depth_max
    @nexts = Array.new(depth_max) { 0 }
  end

  def layout(ctx, node, depth)
    return if node == nil
    node.x = @nexts[depth]
    node.y = depth
    @nexts[depth] += 1
    [node.left, node.right].each do |c|
      layout(ctx, c, depth+1)
    end
  end
end

class ReingoldTilfordTreeLayout
  def layout(ctx, node, depth)
    setup(node, 0)
  end

  def setup(node, depth = 0)
    node.x = -1
    node.y = depth
    children = [node.left, node.right].reject {|c| c == nil}

    case children.length
    when 0
      node.x = 0
    when 1
      setup(children[0], depth+1)
      node.x = children[0].x
    else
      setup(node.left, depth+1)
      setup(node.right, depth+1)
      node.x = fix_subtrees(node.left, node.right)
    end
  end

  def fix_subtrees(nl, nr)
    wl = contour(nl, :<)
    wr = contour(nr, :>)
    truncate_at = [wl.length, wr.length].min # See [Note] below.
    zipped = wl.zip(wr)[0, truncate_at]
    diff = (zipped.map { |xandy| xandy[0] - xandy[1] }).max + 1
    diff += (nr.x + diff + nl.x) % 2
    add_to_tree(nr, diff)
    return (nl.x + nr.x) / 2
  end

  def contour(node, comp, level = 0, cont=nil)
    if level == 0
      cont = [node.x]
    elsif cont.length < level + 1
      cont << node.x
    elsif cont[level].send(comp, node.x) # cont[level] < node.x or cont[level] > node.x
      cont[level] = node.x
    end
    children = [node.left, node.right].reject {|c| c == nil}
    children.each do |c|
      contour(c, comp, level+1, cont)
    end
    return cont
  end

  def add_to_tree(node, val = 0)
    node.x += val
    children = [node.left, node.right].reject {|c| c == nil}
    children.each do |c|
      add_to_tree(c, val)
    end
  end
end

=begin
[Note] 'zip' specification difference between Python and Ruby

Python : zip "The iterator stops when the shortest input iterable is exhausted."
         https://docs.python.org/3/library/functions.html#zip
    ex.)
    >>> x = [1, 2, 3]
    >>> y = [4, 5]
    >>> list(zip(x, y))
    [(1, 4), (2, 5)]

Ruby : zip "If the size of any argument is less than the size of the initial array, nil values are supplied."
       http://ruby-doc.org/core-2.3.1/Array.html#method-i-zip

    ex.)
    $ irb
    2.3.1 :001 > x = [1, 2, 3]
     => [1, 2, 3]
    2.3.1 :002 > y = [4, 5]
     => [4, 5]
    2.3.1 :003 > x.zip(y)
     => [[1, 4], [2, 5], [3, nil]]

=end