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