我想将 DAG 表示为 JSON 文本，并想知道是否有人尝试过这个，以及他们在验证 JSON 是否实际上是 DAG 时处理的任何问题。
问问题
17895 次
3 回答
41
标记每个节点并制作一个边列表。也就是说，对于每个节点，存储它具有边缘的节点，例如：
{
"a": [ "b", "c", "d" ],
"b": [ "d" ],
"c": [ "d" ],
"d": [ ]
}
您可以通过这种方式存储多种图形，而不仅仅是 DAG，因此您需要对其进行后处理以确保它没有循环。如果您多次看到任何节点不是 DAG，只需选择一个节点 DFS。然后删除您刚刚看到的所有节点并重复任何剩余的节点。这样做直到你找到一个循环或者你已经删除了所有的节点，在后一种情况下，图形是一个 DAG。
请注意，这不存储父节点，因为这是冗余信息。如果您需要该数据，您可以在加载图表后生成这些数据。
于 2012-03-27T23:15:47.807 回答
6
JSON 没有本地工具来表示 DAG，除非您制定自己的约定来表示链接数据。JSON-LD（一个 W3C 提案）是一个 JSON 扩展，它正试图做到这一点。该提案可以在这里找到：http: //json-ld.org/spec/latest/json-ld/。
于 2013-07-25T19:01:56.293 回答
2
严格来说，你不能直接用 JSON 来做。您必须想出自己的方式来表示可以通过数据结构中其他地方的引用来识别的对象，然后您必须对反序列化 JSON 字符串的结果进行后处理。
您不能使用 JSON 来执行此操作，原因很简单，即 JSON 表达式是对象图，并且根本没有规定可以表达属性的值应该是数据结构中其他位置的另一个属性的值的概念。换句话说，图中的任何对象都不能有多个父对象，这意味着每个对象都是另一个对象的一个属性的值。
于 2012-03-27T21:29:26.237 回答