Ruby code for Simple Tree Matching showing error

Question

I wrote a code for Simple Tree Matching for matching two DOM nodes. It is showing some error. I am not able to figure it out.

I am posting the code and the error trace.

def tree_match(node1,node2)
    # ------- Implementation of Simple Tree matching algorithm. 

    if node1.name!=node2.name
        puts 'in base case'
        return 0    
    elsif node1.children.empty? or node2.children.empty?
        return 0
    else
        dp = Array.new(node1.children.size) {Array.new(node2.children.size,0)}
        i=1
        j=0
        j = j+1
        node1.children.each do |child1|
            node2.children.each do |child2|

Line 180th. main error is in the code segment below.

                dp[i][j] = [dp[i-1][j],dp[i][j-1],(dp[i-1][j-1] + tree_match(child1,child2))].max
                j = j + 1
            end
            i = i+1
        end
        return 1+dp[dp[0].size-1][dp[1].size-1]
    end
end

ERROR:

in block (2 levels) in tree_match': undefined method[]' for nil:NilClass (NoMethodError) from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:187:in block in each' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:186:inupto' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:186:in each' from /<>/DomTreeParser.rb:179:inblock in tree_match' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:187:in block in each' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:186:inupto' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:186:in each' from /<path>/DomTreeParser.rb:178:intree_match' from /<>/DomTreeParser.rb:180:in block (2 levels) in tree_match' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:187:inblock in each' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:186:in upto' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:186:ineach' from /<>/DomTreeParser.rb:179:in block in tree_match' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:187:inblock in each' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:186:in upto' from /usr/local/lib/ruby/gems/2.0.0/gems/nokogiri-1.6.6.2/lib/nokogiri/xml/node_set.rb:186:ineach' from /<>/DomTreeParser.rb:178:in tree_match' from testDriver.rb:11:in'

EDIT: nil class error is on line 180. I have marked it.

I guess you should initialize j before the inner loop (i.e. before line 179). You are incrementing it over the whole 2D array. — undur_gongor
Yes.... but dp looks up i-1 and j-1 indices, so I have to start with indices 1 — Shashank

Piotr Kruczek Piotr Kruczek · Accepted Answer · 2015-06-09T13:56:01

You move past the boundaries of the array you created. Here

dp = Array.new(node1.children.size) {Array.new(node2.children.size,0)}

you initailize an array with node1.children.size, then iterate over each of them (node1.children) and try to assign dp[i][j] = ... in each step.

Since you start with i, j = 1, 1, here's what happens on the last step of the loop:

dp[i] returns nil because i == node1.children.size and indexes are numerated starting from 0. That's why you get

undefined method[] for nil:NilClass

when you call dp[i][j]

Can't really suggest a best course here since I don't see the entire code, but initializing a bigger Array should do the trick. Oh, and be sure to check out each_with_index

Ruby code for Simple Tree Matching showing error

Line 180th. main error is in the code segment below.

1 Answers