将此 JSON 转换为树并找到父级的路径

Question

data= {
"saturn": [
        "planet",
        "american_car",
        "car"
    ],
    "american_car": [
        "car",
        "gas_driven_automobile"
    ],
    "planet": [
        "large_object",
        "celestial_body"
    ],
    "large_object": [],
    "gas_driven_automobile": [
        "gas_powered_road_vehicle",
        "car"
    ],
    "car": [
        "vehicle",
        "motor_vehicle"
    ],
"vehicle": [],
"motor_vehicle": [],
"gas_powered_road_vehicle": [],
"celestial_body": []
};

我需要编写一个算法，如果我给输入"土星"，我需要获取从土星到不同父母的所有可能路径。 例如，

saturn ->planet ->large_object  
saturn ->american_car->car->vehicle
saturn ->american_car->car->motor_vehicle
saturn ->american_car->gas_driven_automobile->gas_powered_road_vehicle
saturn ->american_car->gas_driven_automobile->car->vehicle

以及所有其他可能的路径。

我正在考虑以某种方式将其转换为树，然后使用库来计算从子项到父项的路径。

正在编写算法，无法弄清楚如何开始将其转换为树。

Answer 1

使用 jq，您可以简单地定义一个递归函数：

def parents($key):
  if has($key)
  then if .[$key] == []  then [] else .[$key][] as $k | [$k] + parents($k) end
  else []
  end;

要使用它来生成 "->" 样式的输出，请使用 -r 命令行选项调用 jq，并像这样调用上面的函数：

["saturn"] + parents("saturn")
| join(" -> ")

更经济

def lineages($key):
  [$key] + (lineages(.[$key][]) // []);

lineages("saturn") | join(" -> ")