gistfile1.rb

#!/usr/bin/env ruby
Graph = Struct.new :v, :gid, :pgid, :row, :height

CAUSE_WEIRD_BEHAVIOUR = true

class Dendrogramer

  def initialize inputs
    calculate_graphs_for inputs
  end

  def calculate_graphs_for raw_input
    @graphs = {}
    @inputs = raw_input.reverse.collect do |graphs_at_step|
      graphs_at_step.collect do |graph|
        gid = graph[:gid]
        @graphs[gid] ||= Graph.new *(%w{v gid pgid}.collect { |arg| graph[arg.to_sym] })
      end
    end
  end

  def process
    build_children
    allocate_height
    process_initial_cliques
  end

  def build_children
    @children = {}
    for_each_graph_in_input do |child|
      next if child.gid == 1
      parent = @graphs[child.pgid]
      @children[parent] ||= []
      @children[parent] << child unless @children[parent].include? child      
    end    
  end

  def allocate_height
    @inputs.each_with_index do |graphs, line_num|
      graphs.each do |graph|
        graph.height ||= line_num+1 if CAUSE_WEIRD_BEHAVIOUR
      end
    end
  end

  def process_initial_cliques
    first_row = @inputs.shift
    first_row.each do |graph|
      is_clique = graph.v.size > 1
      process_first_row_vertex graph if not is_clique
    end
  end

  def process_first_row_vertex graph
    sibling = sibling_of graph
  end

  def sibling_of graph
    parent = @graphs[graph.pgid]
    puts "parent.object_id = #{parent.object_id}"
    puts "@children.keys = #{@children.keys.collect(&:object_id).inspect}"
    puts "@children.has_key? #{@children.has_key? parent}"
    puts "@children.keys.include? #{@children.keys.include? parent}"
    children_of_parent = @children[parent]
    raise "wtf" if children_of_parent.nil?
  end
  
  def for_each_graph_in_input    
    @inputs.each do |graphs|
      graphs.each do |graph|
        yield graph
      end
    end
  end
end

input = 
[{:v=>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], :gid=>1, :pgid=>nil}],
[{:v=>[1, 2, 3, 4, 5, 6], :gid=>2, :pgid=>1}, {:v=>[7, 8, 9, 10, 11, 12], :gid=>3, :pgid=>1}],
[{:v=>[1, 2, 3, 4, 5, 6], :gid=>2, :pgid=>1}, {:v=>[7, 8, 10, 11, 12], :gid=>4, :pgid=>3}, {:v=>[9], :gid=>5, :pgid=>3}],
[{:v=>[7, 8, 10, 11, 12], :gid=>4, :pgid=>3}, {:v=>[9], :gid=>5, :pgid=>3}, {:v=>[1, 2, 3, 4, 5, 6], :gid=>2, :pgid=>1}],
[{:v=>[7, 8, 10, 11, 12], :gid=>4, :pgid=>3}, {:v=>[9], :gid=>5, :pgid=>3}, {:v=>[1, 2, 3, 5, 6], :gid=>6, :pgid=>2}, {:v=>[4], :gid=>7, :pgid=>2}],
[{:v=>[9], :gid=>5, :pgid=>3}, {:v=>[1, 2, 3, 5, 6], :gid=>6, :pgid=>2}, {:v=>[4], :gid=>7, :pgid=>2}, {:v=>[7, 8, 10, 11, 12], :gid=>4, :pgid=>3}],
[{:v=>[9], :gid=>5, :pgid=>3}, {:v=>[1, 2, 3, 5, 6], :gid=>6, :pgid=>2}, {:v=>[4], :gid=>7, :pgid=>2}, {:v=>[7, 8, 10, 11], :gid=>8, :pgid=>4}, {:v=>[12], :gid=>9, :pgid=>4}],
[{:v=>[9], :gid=>5, :pgid=>3}, {:v=>[4], :gid=>7, :pgid=>2}, {:v=>[7, 8, 10, 11], :gid=>8, :pgid=>4}, {:v=>[12], :gid=>9, :pgid=>4}, {:v=>[1, 2, 3, 5, 6], :gid=>6, :pgid=>2}],
[{:v=>[9], :gid=>5, :pgid=>3}, {:v=>[4], :gid=>7, :pgid=>2}, {:v=>[7, 8, 10, 11], :gid=>8, :pgid=>4}, {:v=>[12], :gid=>9, :pgid=>4}, {:v=>[1, 2, 5], :gid=>10, :pgid=>6}, {:v=>[3, 6], :gid=>11, :pgid=>6}],
[{:v=>[9], :gid=>5, :pgid=>3}, {:v=>[4], :gid=>7, :pgid=>2}, {:v=>[12], :gid=>9, :pgid=>4}, {:v=>[1, 2, 5], :gid=>10, :pgid=>6}, {:v=>[3, 6], :gid=>11, :pgid=>6}, {:v=>[7, 8, 10, 11], :gid=>8, :pgid=>4}],
[{:v=>[9], :gid=>5, :pgid=>3}, {:v=>[4], :gid=>7, :pgid=>2}, {:v=>[12], :gid=>9, :pgid=>4}, {:v=>[1, 2, 5], :gid=>10, :pgid=>6}, {:v=>[3, 6], :gid=>11, :pgid=>6}, {:v=>[11], :gid=>12, :pgid=>8}, {:v=>[7, 8, 10], :gid=>13, :pgid=>8}]

Dendrogramer.new(input).process