divide function for set in Ruby 2.3.1

The below is from Ruby 2.3.1 documentation for dividing a set into a set of its subsets based on certain criteria applied to each pair of elements in the original set. Basically, if two numbers in the set are within 1 unit of each other, they fall in the same subset in the set of subsets of the original set.

    require 'set'
numbers = Set[1, 3, 4, 6, 9, 10, 11]
set = numbers.divide { |i,j| (i - j).abs == 1 }
p set     # => #<Set: {#<Set: {1}>, 
          #            #<Set: {11, 9, 10}>,
          #            #<Set: {3, 4}>,

I think the problem on which I am working could use this function. This is the problem. There is a set S of n things together with a proximity function on pairs of things from S that has positive values for some of the pairs in this set. For pairs whose values for the proximity function is not specified, it may be assumed that these values are 0. There is also a threshold parameter. The objective of the program is to induce a partition (a set of pair-wise disjoint and mutually exhaustive subsets of the set) on the set S such that two things fall into the same subset if their proximity function value exceeds the threshold parameter (converse need not be true).

The input to this program is of this form

t<-threshold parameter (a float greater than 0)

n<- number of lines to follow (integer)

Thing_i_1 Thing_j_1 proximity_ij_1 (Thing_i_1 and Thing_j_1 are integers and proximity_ij_1 is float and is greater than 0)

.... .... Thing_i_n Thing_j_n proximity_ij_n

The output is the aforementioned set of pairwise disjoint and mutually exhaustive subsets of the original set such that two things with the proximity function value at least equal to the threshold parameter fall into the same subset.

I wrote the program below to accomplish this, but it fails to form subsets of the set in question. My input was this

Output should be {{1,2,5},{3},{4}} because 1,2 should fall into the same subset and so should 2,5 since proximity function value in each case exceeds the threshold parameter (so 1 and 5 effectively fall into the same subset), and 3 and 4 form subsets of their own.

require 'set'
t=gets.chomp.to_f
n=gets.chomp.to_i
edge=Struct.new(:n1,:n2)
se=Array.new
af=Array.new
sv=Set.new

for i in (0..n-1)
    s=gets.chomp.split(" ")
    se.insert(-1,edge.new(s[0],s[1]))

        af.insert(-1,s[2].to_f)

    if (sv.member? s[0])==false 
        sv.add(s[0])
    end
    if (sv.member? s[1])==false 
        sv.add(s[1])
    end
end

    c=sv.divide { |i,j|  (k=se.index(edge.new(i,j)))!=nil  && af[k]>=t }
p c

Output:

#<Set: {#<Set: {"5"}>, #<Set: {"2"}>, #<Set: {"1"}>, #<Set: {"3"}>, #<Set: {"4"}
>}>

The divide function does not seem to work. Am I doing anything wrong? Why am I getting five disjoint subsets instead of the expected three? I printed out the values of the condition in the divide block and got true exactly for 1,2 and 2,5 but yet 1, 2 and 5 end up in different subsets. Can someone help? Thank you.

Solution

divide will only divide where both block.call(a, b) && block.call(b, a). Make your se reflexive (i.e. insert also the edges 2-1, 4-3 and 5-2) and it will work. Alternately, make your block return true if either edge.new(i,j) or edge.new(j, i) is in se. There is also an error about types: you're creating an edge from strings (edge.new(s[0],s[1]), but testing against an edge from integers (edge.new(i,j)), so the membership test will fail.

That said, this is very unRubyish code. If I were to rewrite it, it would go like this:

require 'set'

Edge = Struct.new(:v1, :v2, :p)
edges = {}
vertices = Set.new

t = gets.chomp.to_f
n = gets.chomp.to_i
n.times do
  v1, v2, p = *gets.chomp.split
  v1 = v1.to_i
  v2 = v2.to_i
  p = p.to_f
  edge = Edge.new(v1, v2, p)

  edges[[v1, v2]] = edge
  vertices << v1 << v2
end

c = vertices.divide { |v1, v2|
  (edge = edges[[v1, v2]] || edges[[v2, v1]]) && edge.p >= t
}

p c
# => #<Set: {#<Set: {1, 2, 5}>, #<Set: {3}>, #<Set: {4}>}>

Basically - use a hash so you can always find an edge quickly by its indices, use << for putting things into other things, remember that the whole point of a set is that it won't insert the same thing twice, objects are truthy so you don't have to explicitly test for != nil, never ever using for :)