如何将定向非循环图（DAG）存储为JSON？

我想将DAG表示为JSON文本，并且想知道是否有人尝试了这个以及他们处理的有关验证JSON实际上是否为DAG的任何问题。如何将定向非循环图（DAG）存储为JSON？

2012-03-27 828

如果我获得DAG，DAG可能没有单根。所以如果你不确定你是否看到它，你如何干掉这个模型。 – 2012-03-27 21:31:10

任何JSON对象肯定都是DAG。 – Pointy 2012-03-27 22:00:01

标记每个节点并创建一个边界列表。也就是说，对于每个节点商店，它有边缘节点，例如：

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

您可以存储多种图形的这种方式，不仅仅是DAG的，所以你需要进行后期处理它做确定它没有循环。只要选择一个节点即DFS，如果您看到任何节点不止一次，它就不是DAG。然后删除刚才看到的所有节点，然后重复其余节点。做到这一点，直到找到一个循环或者你已经删除了所有的节点，在后一种情况下，图形是一个DAG。

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

来源

2012-03-27 23:15:47

反向存储有什么缺点（数组值是“from”节点而不是“to”）？如果你想做一个拓扑排序，我会认为这会更好。 – 2016-04-04 09:47:13

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

你不能用JSON来实现它，原因很简单，JSON表达式是对象图，而且根本没有关于表达属性值应该是另一个属性值的规定在数据结构中。换句话说，图中没有任何对象可以有多个父对象，这意味着每个对象都是一个对象的一个属性的值。

来源

2012-03-27 21:29:26 Pointy

在DAG中，一个节点可以有两个父母。考虑用一种编程语言表示一个表达式（比如，JavaScript :-)，其中包含两个对单个变量的引用。传统上，表达式中的那两点将指向同一个节点。 DAG中没有周期（根据定义），因为（通常;不一定我猜）所有链接“点下”图表，所以你永远不会“返回”。它就像一棵树，除了类似的节点被合并。 – Pointy 2012-03-27 21:40:19

哈哈，这个评论是回答关于这个与周期有关的问题，所以我会把它留在那里。 – Pointy 2012-03-27 21:40:54

是的，我的基本CS理解失败;-)感谢您的解释。 – 2012-03-27 21:41:10

除非您自行约定表示链接的数据，否则JSON无法代表DAG。 JSON-LD（一个W3C提案）是一个JSON扩展，正试图完成这一任务。建议可以在这里找到：http://json-ld.org/spec/latest/json-ld/。

来源

2013-07-25 19:01:56 dave

如何将定向非循环图（DAG）存储为JSON？

回答

相关问题