Solve a simple dependency graph in Ruby. This is useful to follow file dependency like: #include in C++

walk_dependency_graph.rb

# Walk a dependency graph
#
def walk(deps, available = [])
  # End condition
  return if deps.keys.size == available.size
  
  if available.size == 0
    deps.each do |f, h|
      next if h[:visited] == true
      next if h[:includes].size > 0
      deps[f][:visited] = true
      available << f
      puts "-> #{f}"
    end
  end
  
  deps.each do |f,h|
    next if h[:visited] == true
    next unless h[:includes].all? { |inc| available.index(inc) }
    
    deps[f][:visited] = true
    available << f
    puts "-> #{f}"
  end

  walk(deps, available)
end

# Dependency graph
deps = {
  'A' => {
    :includes => ['B','C'], # Dependency
    :visited => false       # Mark node visited
  },
  'B' => {
    :includes => ['C'],
    :visited => false
  },
  'C' => {
    :includes => [],
    :visited => false
  }
}

# Start walking
walk(deps, [])