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

Question

我想将DAG表示为JSON文本,并想知道是否有人尝试过此以及他们处理的有关验证JSON是否实际上是DAG的任何问题.

Answer 1

标记每个节点并创建边缘列表.也就是说,为每个节点存储它具有边缘的节点,例如:

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

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

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

Answer 2

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