class Dagwood::DependencyGraph
Attributes
dependencies[R]
Public Class Methods
new(dependencies)
click to toggle source
@param dependencies [Hash]
A hash of the form { item1: ['item2', 'item3'], item2: ['item3'], item3: []} would mean that "item1" depends on item2 and item3, item2 depends on item3 and item3 has no dependencies. Nil and missing values will be converted to [].
# File lib/dagwood/dependency_graph.rb, line 15 def initialize(dependencies) @dependencies = Hash.new([]).merge(dependencies.transform_values { |v| v.nil? ? [] : v.sort }) end
Public Instance Methods
merge(other)
click to toggle source
Returns a new graph containing all dependencies from this graph and the given graph. If both graphs depend on the same item, but that item's sub-dependencies differ, the resulting graph will depend on the union of both.
# File lib/dagwood/dependency_graph.rb, line 77 def merge(other) all_dependencies = {} (dependencies.keys | other.dependencies.keys).each do |key| all_dependencies[key] = dependencies[key] | other.dependencies[key] end self.class.new all_dependencies end
order()
click to toggle source
# File lib/dagwood/dependency_graph.rb, line 19 def order @order ||= tsort end
parallel_order()
click to toggle source
Similar to order
, except this will group items that have the same “priority”, thus indicating they can be done in parallel.
Same priority means:
1) They have the same exact same sub-dependencies OR 2) B comes after A and all of B's dependencies have been resolved before A
# File lib/dagwood/dependency_graph.rb, line 34 def parallel_order groups = [] ungrouped_dependencies = order.dup until ungrouped_dependencies.empty? # Start this group with the first dependency we haven't grouped yet group_starter = ungrouped_dependencies.delete_at(0) group = [group_starter] ungrouped_dependencies.each do |ungrouped_dependency| same_priority = @dependencies[ungrouped_dependency].all? do |sub_dependency| groups.reduce(false) { |found, g| found || g.include?(sub_dependency) } end group << ungrouped_dependency if same_priority end # Remove depedencies we managed to group ungrouped_dependencies -= group groups << group.sort end groups end
reverse_order()
click to toggle source
# File lib/dagwood/dependency_graph.rb, line 23 def reverse_order @reverse_order ||= order.reverse end
subgraph(node)
click to toggle source
Generate a subgraph starting at the given node
# File lib/dagwood/dependency_graph.rb, line 61 def subgraph(node) return self.class.new({}) unless @dependencies.key? node # Add the given node and its dependencies to our hash hash = {} hash[node] = @dependencies[node] # For every dependency of the given node, recursively create a subgraph and merge it into our result @dependencies[node].each { |dep| hash.merge! subgraph(dep).dependencies } self.class.new hash end
Private Instance Methods
tsort_each_child(node, &block)
click to toggle source
# File lib/dagwood/dependency_graph.rb, line 89 def tsort_each_child(node, &block) @dependencies.fetch(node, []).each(&block) end
tsort_each_node(&block)
click to toggle source
# File lib/dagwood/dependency_graph.rb, line 93 def tsort_each_node(&block) @dependencies.each_key(&block) end