Преобразуйте этот JSON в дерево и найдите путь к родителю. - PullRequest
Новая
       22

Преобразуйте этот JSON в дерево и найдите путь к родителю.

1 голос
/ 31 мая 2019 
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

и все другие возможные пути.

Я думал о том, чтобы каким-то образом преобразовать это в дерево, а затем использовать библиотеку для вычисления пути от дочернего элемента к родительскому.

Работая над написанием алгоритма, не могу понять, с чего начать при преобразовании этого в дерево.

1 Ответ

0 голосов
/ 31 мая 2019

Используя , вы можете просто определить рекурсивную функцию: 

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

Чтобы использовать его для вывода вывода в стиле "->", вызовите jq с параметром командной строки -r и вызовите вышеуказанную функцию следующим образом: 

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

Экономичнее 

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


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