Sha256: a8f3ad8210a81b0cfc03325d0b10c8af3a0e73eff7d60a57ff12cd775ff51baa
Contents?: true
Size: 942 Bytes
Versions: 1
Compression:
Stored size: 942 Bytes
Contents
require 'tsort' module Pallets class Graph include TSort def initialize @nodes = {} end def add(node, dependencies) @nodes[node] = dependencies end def parents(node) @nodes[node] end def empty? @nodes.empty? end # Returns nodes topologically sorted, together with their order (number of # nodes that have to be executed prior) 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 private def tsort_each_node(&block) @nodes.each_key(&block) end def tsort_each_child(node, &block) @nodes.fetch(node).each(&block) end end end
Version data entries
1 entries across 1 versions & 1 rubygems
Version | Path |
---|---|
pallets-0.3.0 | lib/pallets/graph.rb |