# Object::transitive_detect
# Transitive closure search of a (directed, eventually cyclic) graph.
# No requirement on graph implementation.
 
class Object
 
  # transitive closure visit
  # the required block gets passed an object and it returns:
  # - nil (or false, or []), if the object certainly does not match the condition
  # - the object itself, if the object matches the condition
  # - an array of delegates objects, if the condition match depends on one of them
  # Note: a simple variant of this method could return the path followed.
  def transitive_detect(&block)
    return nil unless self
    to_visit = self.is_a?(Array) ? self : [self]
    visited = []
    until to_visit.empty?
      obj = to_visit.pop
      result = block.call(obj)
      return result if result && !result.is_a?(Array)
      visited << obj
      result.each do |res|
        to_visit << res unless visited.include?(res)
      end if result
    end
    nil
  end
 
end
 
air_routes = {
  :rome => [:london, :amsterdam],
  :london => [:new_york, :paris],
  :paris => [:oslo, :rome, :london],
  :new_york => [:boston, :los_angeles],
  :boston => [:new_york],
  :los_angeles => [:new_york, :san_francisco],
  :miami => [:new_orleans],
  :new_orleans => [:miami],
}
 
def air_route_from_to(city1, city2, routes)
  found = city1.transitive_detect {|city| (city == city2) ? city : routes[city] }
  puts "From #{city1} to #{city2}: #{found ? 'Y': 'N'}"
end
 
cities = [:rome, :miami, :boston, :oslo, :new_orleans, :los_angeles]
cities.each do |c1|
  cities.each do |c2|
    air_route_from_to(c1, c2, air_routes)
  end
end