Generates a Complete N-ary Tree given parameters (height, degree) in dot format. Visualize with graphviz.

complete_nary_tree.rb

#!/usr/bin/env ruby

class CompleteNaryTreeGenerator
  def self.generate_dot(height, degree)
    puts 'digraph {'

    # Convenience.
    d = degree
    h = height
    i = 1

    # TODO node zero

    # For each level j...
    0.upto(h) do |l|

      # For each node at level j...
      1.upto(d**l) do |j|

        # Figure out the node n.
        n = i
        puts "  #{dot_node(n)}"

        # And n's children.
        1.upto(d) do |c|
          child_index = d * (n - 1) + 1 + c
          puts "    #{dot_edge(n, child_index)}"
        end

        i += 1
      end

      puts
    end

    puts "}"
  end

  private

  def self.dot_node(n)
    "N#{n} [id=\"#{n}\"]\n"
  end

  def self.dot_edge(n1, n2, options = { dir: 'back' })
    s = options.merge(id: "#{n1}:#{n2}").map {|k,v| "#{k}=\"#{v}\"" }.join(' ')
    "N#{n1} -> N#{n2} [#{s}]\n"
  end

end

degree = ARGV.shift.to_i
degree = 2 if degree < 1

height = ARGV.shift.to_i
height = 3 if height < 1

CompleteNaryTreeGenerator.generate_dot(height, degree)