Обнаружение цикла в Hash в Ruby

Question

С помощью хэша у меня есть список «заданий», каждый с идентификатором и родителем. Задания с родителем не могут быть выполнены, пока их родитель не будет. Как бы я обнаружил петлю зависимостей?

Набор данных показан ниже:

jobs = [
  {:id => 1,  :title => "a",  :pid => nil},
  {:id => 2,  :title => "b",  :pid => 3},
  {:id => 3,  :title => "c",  :pid => 6},
  {:id => 4,  :title => "d",  :pid => 1},
  {:id => 5,  :title => "e",  :pid => nil},
  {:id => 6,  :title => "f",  :pid => 2},
]

Последовательность 'id' такова: 1> 2> 3> 6> 2> 3> 6 .... и т. Д.

Answer 1

Это называется "топологической сортировкой", и в Ruby она встроена . Это работает немного эффективнее, когда родители знают своих детей, а не когда дети знают своих родителей. Вот неэффективная версия; Вы можете ускорить его, переписав структуру данных (в хеш, который имеет :children вместо :pid, так что tsort_each_child может просто пойти node[:children].each вместо того, чтобы фильтровать весь массив).

Поскольку TSort предназначен для работы в качестве дополнения, нам нужно создать новый класс для данных (или поочередно улучшить или загрязнить Array). #tsort приведет к списку, отсортированному от детей к родителям; так как вы хотите, чтобы родители были раньше детей, мы можем просто #reverse результат.

require 'tsort'

class TSArray < Array
  include TSort
  alias tsort_each_node each
  def tsort_each_child(node)
    each { |child| yield child if child[:pid] == node[:id] }
  end
end

begin
  p TSArray.new(jobs).tsort.reverse
rescue TSort::Cyclic
  puts "Nope."
end

Answer 2

Различные алгоритмы обнаружения цикла в ориентированном графе предназначены для произвольных ориентированных графов.График, изображенный здесь, намного проще в том смысле, что у каждого ребенка не более родителя.Это позволяет легко определить, присутствует ли цикл, что можно сделать очень быстро.

Я интерпретировал этот вопрос как означающий, что, если цикл присутствует, вы хотите вернуть один, а не просто определениеприсутствует ли один.

Код

require 'set'

def cycle_present?(arr)
  kids_to_parent = arr.each_with_object({}) { |g,h| h[g[:id]] = g[:pid] }
  kids = kids_to_parent.keys
  while kids.any?
    kid = kids.first
    visited = [kid].to_set
    loop do
      parent = kids_to_parent[kid]
      break if parent.nil? || !kids.include?(parent)
      return construct_cycle(parent, kids_to_parent) unless visited.add?(parent)
      kid = parent 
    end
    kids -= visited.to_a
  end
  false
end

def construct_cycle(parent, kids_to_parent)
  arr = [parent]
  loop do
    parent = kids_to_parent[parent]
    arr << parent
    break arr if arr.first == parent
  end
end

Примеры

cycle_present?(jobs)
  #=> [2, 3, 6, 2]

arr = [{:id=>1, :title=>"a", :pid=>nil},
       {:id=>2, :title=>"b", :pid=>1},
       {:id=>3, :title=>"c", :pid=>1},
       {:id=>4, :title=>"d", :pid=>2},
       {:id=>5, :title=>"e", :pid=>2},
       {:id=>6, :title=>"f", :pid=>3}] 
cycle_present?(arr)
  #=> false

Пояснение

Вот метод с комментариями и puts утверждениями.

def cycle_present?(arr)
  kids_to_parent = arr.each_with_object({}) { |g,h| h[g[:id]] = g[:pid] }
  puts "kids_to_parent = #{kids_to_parent}"                                #!!
  # kids are nodes that may be on a cycle
  kids = kids_to_parent.keys
  puts "kids = #{kids}"                                                    #!!
  while kids.any?
    # select a kid
    kid = kids.first
    puts "\nkid = #{kid}"                                                  #!!
    # construct a set initially containing kid
    visited = [kid].to_set
    puts "visited = #{visited}"                                            #!!
    puts "enter loop do"                                                   #!!

    loop do
      # determine kid's parent, if has one
      parent = kids_to_parent[kid]
      puts "  parent = #{parent}"                                          #!!
      if parent.nil?                                                       #!!
        puts "  parent.nil? = true, so break"                              #!!
      elsif !kids.include?(parent)
        puts "  kids.include?(parent) #=> false, parent has been excluded" #!!
      end                                                                  #!!
      # if the kid has no parent or the parent has already been removed
      # from kids we can break and eliminate all kids in visited
      break if parent.nil? || !kids.include?(parent)
      # try to add parent to set of visited nodes; if can't we have
      # discovered a cycle and are finished
      puts "  visited.add?(parent) = #{!visited.include?(parent)}"         #!! 
      puts "  return construct_cycle(parent, kids_to_parent)" if
        visited.include?(parent)                                           #!!
      return construct_cycle(parent, kids_to_parent) unless visited.add?(parent)
      puts "  now visited = #{visited}"                                    #!!
      # the new kid is the parent of the former kid
      puts "  set kid = #{parent}"                                         #!!
      kid = parent 
    end

    # we found a kid with no parent, or a parent who has already
    # been removed from kids, so remove all visited nodes
    puts "after loop, set kids = #{kids - visited.to_a}"                   #!!
    kids -= visited.to_a
  end
  puts "after while loop, return false"                                    #!!
  false
end

def construct_cycle(parent, kids_to_parent)
  puts
  arr = [parent]
  loop do
    parent = kids_to_parent[parent] 
    puts "arr = #{arr}, parent = #{parent}                                 #!!
    arr << parent
    break arr if arr.first == parent
  end
end

cycle_present?(jobs)

отображает следующее:

kid = 1
visited = #<Set: {1}>
enter loop do
  parent = 
  parent.nil? = true, so break
after loop, set kids = [2, 3, 4, 5, 6]

kid = 2
visited = #<Set: {2}>
enter loop do
  parent = 3
  visited.add?(parent) = true
  now visited = #<Set: {2, 3}>
  set kid = 3
  parent = 6
  visited.add?(parent) = true
  now visited = #<Set: {2, 3, 6}>
  set kid = 6
  parent = 2
  visited.add?(parent) = false
  return construct_cycle(parent, kids_to_parent)

arr=[2], parent = 3
arr=[2, 3], parent = 6
arr=[2, 3, 6], parent = 2
  #=> [2, 3, 6, 2]