Flatten a dependency graph in Ruby. This is a little something I built for managing Qt library dependencies in nixcrpkgs.

flatten_dependency_graph.rb

# Given an array of dependencies and a block for retrieving dependencies of an
# dependency, returns an array of dependencies with three guarantees:
#
# 1) Contains all the listed dependencies.
# 2) Has no duplicates.
# 3) For any dependency in the list, all of its dependencies appear before it.
#
# Guarantee 3 only holds if the underlying graph has no circul dependencies.  If
# there is a circular dependency, it will not be detected, but it will not cause
# an infinite loop either.
def flatten_deps(deps)
  work = deps
  expanded = {}
  output = {}
  while !work.empty?
    dep = work.last
    if expanded[dep]
      output[dep] = true
      work.pop
    else
      expanded[dep] = true
      deps = yield dep
      work.concat(deps)
    end
  end
  output.keys  # relies on Ruby's ordered hashes
end