Withing a hash I have a list of 'jobs', each with an id and a Parent. Jobs with a parent cannot be executed until their parent is. How would I detect a loop of dependencies?
The data set is shown below:
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},
]
The sequence of 'id' is thus: 1 > 2 > 3 > 6 > 2 > 3 > 6.... etc
This is called "topological sort", and Ruby has it built in. It works a bit more efficiently when parents know their children rather than when children know their parent. Here's the inefficient version; you can speed it up by rewriting your data structure (into a hash that has :children instead of :pid, so that tsort_each_child can just go node[:children].each instead of having to filter the whole array).
Since TSort is designed to work as a mix-in, we need to make a new class for the data (or alternately refine or pollute Array). #tsort will result in a list that is sorted from children to parents; since you want parents before children, we can just #reverse the result.
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