DAG(Directed Acyclic Graph)를 JSON으로 저장하려면 어떻게 해야 합니까?

DAG(Directed Acyclic Graph)를 JSON으로 저장하려면 어떻게 해야 합니까?

DAG를 JSON 텍스트로 표현하고 싶습니다만, JSON이 실제로 DAG인지 아닌지를 검증하기 위해서, 이것을 시험해 본 사람이 있는지 어떤지, 또 대응한 문제가 있는지 알고 싶습니다.

각 노드에 라벨을 붙이고 가장자리 목록을 만듭니다.즉, 각 노드에 대해 다음과 같이 에지가 있는 노드를 저장합니다.

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

DAG뿐만 아니라 다양한 종류의 그래프를 저장할 수 있으므로 루프가 없는지 확인하기 위해 그래프를 후처리해야 합니다.DAG가 아닌 노드가 여러 번 나타나면 노드 DFS를 선택합니다.그런 다음 방금 본 노드를 모두 제거하고 나머지 노드에서도 반복합니다.루프를 찾거나 모든 노드를 제거할 때까지 이 작업을 수행합니다. 후자의 경우 그래프가 DAG입니다.

부모 노드는 용장정보이므로 저장되지 않습니다.데이터가 필요한 경우 그래프를 로드한 후 생성할 수 있습니다.

JSON에는 링크된 데이터를 나타내는 규칙을 만들지 않는 한 DAG를 나타내는 네이티브 기능이 없습니다.JSON-LD(W3C 프로포절)는 정확하게 이를 실현하기 위한 JSON 확장입니다.제안서는 http://json-ld.org/spec/latest/json-ld/에서 찾을 수 있습니다.

엄밀히 말하면 JSON에서는 직접 할 수 없습니다.데이터 구조 내의 다른 곳에서 참조로 식별할 수 있는 객체를 나타내는 독자적인 방법을 생각해 낸 후 JSON 문자열의 역직렬화 결과를 후처리해야 합니다.

JSON 표현식이 객체 그래프라는 단순한 이유 때문에 JSON에서는 이 작업을 수행할 수 없으며, 데이터 구조 내의 다른 속성의 값이 되어야 한다는 개념을 표현할 수 있는 조항도 없습니다.바꿔 말하면, 그래프 내의 어떤 개체도 둘 이상의 상위 개체를 가질 수 없습니다. 즉, 모든 개체는 다른 개체의 정확히 하나의 속성 값임을 의미합니다.

언급URL : https://stackoverflow.com/questions/9897956/how-do-you-store-a-directed-acyclic-graph-dag-as-json