Class: Pallets::Graph

Inherits:
Object
  • Object
show all
Includes:
TSort
Defined in:
lib/pallets/graph.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



7
8
9
 
# File 'lib/pallets/graph.rb', line 7

def initialize
  @nodes = {}
end

Instance Method Details

#add(node, dependencies) ⇒ Object 



11
12
13
 
# File 'lib/pallets/graph.rb', line 11

def add(node, dependencies)
  @nodes[node] = dependencies
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


19
20
21
 
# File 'lib/pallets/graph.rb', line 19

def empty?
  @nodes.empty?
end

#parents(node) ⇒ Object 



15
16
17
 
# File 'lib/pallets/graph.rb', line 15

def parents(node)
  @nodes[node]
end

#sorted_with_order ⇒ Object

Returns nodes topologically sorted, together with their order (number of nodes that have to be executed prior)



25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/pallets/graph.rb', line 25

def sorted_with_order
  # Identify groups of nodes that can be executed concurrently
  groups = tsort_each.slice_when { |a, b| parents(a) != parents(b) }

  # Assign order to each node
  i = 0
  groups.flat_map do |group|
    group_with_order = group.product([i])
    i += group.size
    group_with_order
  end
end