Problem with sorting algorithm in RailsWizard

RailsWizard, a tool to generate rails templates, allows setting order of recipes by specifying which recipes should run before (run_before option) and after (run_after) given recipe, as described in https://github.com/intridea/rails_wizard/wiki/Recipe-Configuration

This is implemented in Recipe class:

module RailsWizard
  class Recipe
    extend Comparable

    def self.<=>(another)
      return -1 if another.run_after.开发者_运维百科include?(self.key) || self.run_before.include?(another.key)
      return 1 if another.run_before.include?(self.key) || self.run_after.include?(another.key)
      self.key <=> another.key # simple sort by name
    end
  end
end

However, this algorithm often provides a wrong order, see corresponding issue and a demo script for this problem: https://gist.github.com/987025

How would you fix this algorithm?

The problem with the algorithm is that the comparison operator does not define a Strict Weak Ordering.

Specifically, it lacks transitivity (if x < y, and y < z, then x < z). In your example gist:

• n < l by the before instruction
• l < m by the sort by keys
• m < n by the sort by keys

That last one, m < n, is a contradiction, since by transitivity, n < l < m. This breaks your sort.

We first need to fix the operator so that it never provides contradictory information. Second, I think we need to either propagate the transitive ordering so that transitivity is maintained across non-adjacent items, or we need to use an O(n^2) algorithm that compares every item against every other item.

Selection sort meets that criterion, so here's your code using selection sort, and a before? comparison operator.

require 'yaml'
hash = YAML.load '
a:
  after: 
  before: 
l:
  after: 
  before: 
n:
  after: 
  before: l
b:
  after: 
  before: 
m:
  after: 
  before: 
c:
  after: 
  before: 
z:
  after: 
  before: 
'
hash.each do |k,v|
  v.each do |vk,vv|
    v[vk] = (vv||'').split
  end
end

class Hash
  def without *ks
    delete_if { |k,v| ks.include? k }
  end
  def delete! *ks
    #print "\n\nwithout: #{ks.join(', ')}"
    replace without *ks
  end
end

def print_keys hash
  puts hash.map(&:first).join('  ')
end

def sort hash
  array = hash.to_a
  selection_sort array
  print_keys array
  Hash[array]
end

def selection_sort array
  (0...array.length).each do |i|
    min = i
    ((i+1)...array.length).each do |j|
      min = j if before?(array[j], array[min])
    end
    temp = array[min]
    array[min] = array[i]
    array[i] = temp
  end
end

def before? a, b
  b.last['after'].include?(a.first) || a.last['before'].include?(b.first)
end

def test hash
  puts nil,nil
  print_keys hash
  puts '-'*hash.count*3
  hash.count.times { hash = sort hash }
end

test hash

And this gives:

$ ruby sort_test.rb 


a  l  n  b  m  c  z
---------------------
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z