Creating Class relation

Question

Given an array of modules, what is the best way to return an array that describes the normalized (minimal) ordering relations between the modules? Each element of the array should be an array of pairs of modules that have child-parent relation. The child-parent order within each pair matters, but the order among the pairs does not matter. Normalized ordering means that whatever can be derived from transitivity should be excluded from the array.

For example, given [Object, Comparable, Float, Fixnum, Integer], the answer would be:

[
  [Float, Object],
  [Float, Comparable],
  [Fixnum, Integer],
  [Integer, Object],
  [Integer, Comparable],
]

The five pairs in the array corresponds to the five edges in this Hasse diagram:

Hint: Module#<=>other returns -1, 0, 1 if there is an order relation, and nil if there is no order relation.

Answer 1

def ordering(mods)
  a = mods.permutation(2)
          .select { |m1,m2| (m1<=>m2) == -1 }
  a.reject { |m1,m2|
      mods.any? { |m| a.include?([m1,m]) && a.include?([m,m2]) } }
end

ordering([Object, Comparable, Float, Fixnum, Integer])
  #=> [[Float, Object],
  #    [Float, Comparable],
  #    [Fixnum, Integer],
  #    [Integer, Object],
  #    [Integer, Comparable]] 

mods = [Object, Comparable, Float, Fixnum, Integer, String, Array,
        Hash, Enumerable, Enumerator, Module, Method, IO, File]
ordering(mods)
  #=> [[Float, Object], [Float, Comparable],
  #    [Fixnum, Integer],
  #    [Integer, Object], [Integer, Comparable],
  #    [String, Object], [String, Comparable],
  #    [Array, Object], [Array, Enumerable],
  #    [Hash, Object], [Hash, Enumerable], [Hash, Object],
  #      [Hash, Enumerable],
  #    [Enumerator, Object], [Enumerator, Enumerable],
  #    [Module, Object],
  #    [Method, Object],
  #    [IO, Object], [IO, Enumerable],
  #    [File, IO]]

Answer 2

It looks like I could introduce the solution. It is far from being elegant, but you might find some parts of this code useful as hints.

I won’t use module comparision.

input = [Object, Comparable, Float, Fixnum, Integer]

First of all, let’s provide a function to build a whole list of class/module supers:

def grands klass
  klasses = klass.included_modules
  loop do
    break unless \
       klass.methods.include?(:superclass) && \
       (klass = klass.superclass)
    klasses << klass
  end 
  klasses
end

Now we would collect all the forward and backward descendants:

result = input.reduce({:fwd => {}, :bwd => {}}) { |memo, klass|
  grands(klass).each { |c| 
    next unless input.include? c
    (memo[:fwd][klass] ||= []) << c 
    (memo[:bwd][c] ||= []) << klass
  }
  memo
}
p result

# NB Below is the output of input _including_ Numeric in demo purposes

# { :fwd => {
#     Float   => [Comparable, Numeric, Object],
#     Fixnum  => [Comparable, Integer, Numeric, Object],
#     Numeric => [Comparable, Object],
#     Integer => [Comparable, Numeric, Object]
#   },
#   :bwd => {
#     Comparable => [Float, Fixnum, Numeric, Integer],
#     Numeric    => [Float, Fixnum, Integer],
#     Object     => [Float, Fixnum, Numeric, Integer],
#     Integer    => [Fixnum]
#   }
# }

It’s time to build the normalized hash:

normalized = Hash[result[:fwd].map { |k, v|
  [k, v.select { |c|
    (result[:bwd][c] & v).empty?
  }]
}]

That gives:

# {  
#    Float   => [Comparable, Object], 
#    Fixnum  => [Integer], 
#    Integer => [Comparable, Object]
# }

You requested an array as the result; the conversion is pretty straightforward and definitely is out of scope of this task.

Hope it helps.