Class: Dagwood::DependencyGraph

Inherits:
Object
  • Object
show all
Includes:
TSort
Defined in:
lib/dagwood/dependency_graph.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(dependencies) ⇒ DependencyGraph

Returns a new instance of DependencyGraph.

Parameters:

  • 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 [].



15
16
17
 
# File 'lib/dagwood/dependency_graph.rb', line 15

def initialize(dependencies)
  @dependencies = Hash.new([]).merge(dependencies.transform_values { |v| v.nil? ? [] : v.sort })
end

Instance Attribute Details

#dependencies ⇒ Object (readonly)

Returns the value of attribute dependencies.



9
10
11
 
# File 'lib/dagwood/dependency_graph.rb', line 9

def dependencies
  @dependencies
end

Instance Method Details

#merge(other) ⇒ Object

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.



77
78
79
80
81
82
83
84
85
 
# 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 ⇒ Object 



19
20
21
 
# File 'lib/dagwood/dependency_graph.rb', line 19

def order
  @order ||= tsort
end

#parallel_order ⇒ Object

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



34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# 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 ⇒ Object 



23
24
25
 
# File 'lib/dagwood/dependency_graph.rb', line 23

def reverse_order
  @reverse_order ||= order.reverse
end

#subgraph(node) ⇒ Object

Generate a subgraph starting at the given node



61
62
63
64
65
66
67
68
69
70
71
72
 
# 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