Как вы храните Directed Acyclic Graph (DAG) как JSON?

Ответ 1

Обозначьте каждый node и создайте список ребер. То есть для каждого node храните узлы, к которым привязаны ребра, например:

{
  "a": [ "b", "c", "d" ],
  "b": [ "d" ],
  "c": [ "d" ],
  "d": [ ]
}

Вы можете хранить много видов графиков таким образом, а не только DAG, поэтому вам нужно будет выполнить пост-обработку, чтобы убедиться, что у него нет циклов. Просто выберите node, DFS, если вы видите какой-либо node более чем один раз, это не DAG. Затем удалите все узлы, которые вы только что видели, и повторите с любыми оставшимися узлами. Сделайте это до тех пор, пока не найдете цикл или вы не удалите все узлы, в последнем случае граф является DAG.

Обратите внимание, что это не сохраняет родительские узлы, поскольку это избыточная информация. Вы можете сгенерировать их после загрузки графика, если вам нужны эти данные.

Ответ 2

JSON не имеет собственного средства для представления DAG, если вы не создадите собственное соглашение для представления связанных данных. JSON-LD (предложение W3C) - это расширение JSON, которое пытается сделать именно это. Предложение можно найти здесь: http://json-ld.org/spec/latest/json-ld/.

Ответ 3

Строго говоря, вы не можете делать это напрямую с JSON. Вам придется придумать свой собственный способ представления объектов, которые могут быть идентифицированы по ссылке в другом месте структуры данных, а затем вам придется выполнить пост-обработку результата десериализации строки JSON.

Вы не можете сделать это с помощью JSON по той простой причине, что выражение JSON является графиком объекта, и просто нет положений для выражения понятия, что значение свойства должно быть значением другого свойства в другом месте данных состав. Другими словами, ни один объект в графе не может иметь более одного родителя, что означает, что каждый объект является значением точно одного свойства одного другого объекта.