如何将有向无环图(DAG)存储为JSON？

Question

我想将DAG表示为JSON文本，并想知道是否有人尝试过这种方式，以及他们在验证JSON是否实际上是DAG时处理过的任何问题。

Answer 1

标记每个节点，并制作一个边列表。也就是说，对于每个节点，存储它具有边的节点，例如：

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

您可以通过这种方式存储许多类型的图，而不仅仅是DAG，因此您需要对其进行后处理，以确保它没有循环。如果您多次看到某个节点不是DAG，只需选择一个节点DFS即可。然后删除您刚才看到的所有节点，并对剩余的节点重复上述操作。一直执行此操作，直到找到一个循环或删除了所有节点，在后一种情况下，图形为DAG。

请注意，这不会存储父节点，因为这是冗余信息。如果需要这些数据，您可以在加载图形后生成这些数据。

Answer 2

JSON没有表示DAG的原生工具，除非您制定自己的约定来表示链接数据。JSON-LD (一个W3C提议)就是一个试图做到这一点的JSON扩展。该提案可以在这里找到：http://json-ld.org/spec/latest/json-ld/。

Answer 3

严格地说，你不能直接用JSON做到这一点。您必须想出自己的方式来表示可以在数据结构中的其他位置通过引用标识的对象，然后必须对反序列化JSON字符串的结果进行后处理。

使用JSON不能做到这一点，原因很简单，因为JSON表达式是对象图，而且根本没有规定表示属性的值应该是数据结构中其他属性的值的概念。换句话说，图中的任何对象都不能有多个父对象，这意味着每个对象都恰好是另一个对象的一个属性的值。