如何将有向无环图(DAG)存储为JSON? [英] How do you store a Directed Acyclic Graph (DAG) as JSON?

问题描述

我想将DAG表示为JSON文本，想知道是否有人尝试过此方法以及他们在验证JSON是否真的是DAG方面所处理的任何问题.

I want to represent a DAG as JSON text and wondering if anyone has tried this and any issues they dealt with in regards to validating if the JSON is actually a DAG.

推荐答案

标记每个节点并创建一个边缘列表.也就是说，对于每个节点，存储其具有边缘的节点，例如:

Label each node and make an edge list. That is, for each node store the nodes that it has edges to, for example:

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

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

You can store many kinds of graphs this way, not just DAGs, so you will need to post-process it to make sure that it has no loops. Just pick a node, DFS, if you see any node more than once it is not a DAG. Then remove all of the nodes you just saw and repeat with any remaining nodes. Do this until you find a loop or you've removed all of the nodes, in the latter case the graph is a DAG.

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

Note that this does not store parent nodes, since that is redundant information. You can generate those after loading the graph if you need that data.

这篇关于如何将有向无环图(DAG)存储为JSON?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！