json - notacion - grafo mixto

¿Cómo se almacena un gráfico acíclico dirigido(DAG) como JSON?

Question

Quiero representar a un DAG como texto JSON y me pregunto si alguien ha intentado esto y los problemas que resolvió para validar si el JSON es en realidad un DAG.

Answer 1

Estrictamente hablando, no puedes hacerlo directamente con JSON. Tendría que encontrar su propia forma de representar objetos que puedan identificarse como referencia en cualquier otro lugar de la estructura de datos, y luego tendría que postprocesar el resultado de deserializar la cadena JSON.

No puede hacerlo con JSON por la sencilla razón de que la expresión JSON es el gráfico de objetos, y simplemente no hay disposiciones para expresar la noción de que el valor de una propiedad debe ser el valor de otra propiedad en otro lugar de la estructura de datos. Para decirlo de otra manera, ningún objeto en el gráfico puede tener más de un padre, lo que implica que cada objeto es el valor de exactamente una propiedad de otro objeto.

Answer 2

Etiquete cada nodo y haga una lista de bordes. Es decir, para cada nodo de almacenamiento los nodos que tiene bordes, por ejemplo:

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

Puede almacenar muchos tipos de gráficos de esta manera, no solo los DAG, por lo que deberá procesarlo posteriormente para asegurarse de que no tenga bucles. Simplemente elija un nodo, DFS, si ve cualquier nodo más de una vez, no es un DAG. Luego retire todos los nodos que acaba de ver y repita con los nodos restantes. Haga esto hasta que encuentre un bucle o haya eliminado todos los nodos, en este último caso, el gráfico es un DAG.

Tenga en cuenta que esto no almacena nodos principales, ya que es información redundante. Puede generarlos después de cargar el gráfico si necesita esos datos.

Answer 3

JSON no tiene instalaciones nativas para representar DAG, a menos que realice su propia convención para representar datos vinculados. JSON-LD (una propuesta de W3C) es una extensión JSON que está tratando de hacer exactamente eso. La propuesta se puede encontrar aquí: http://json-ld.org/spec/latest/json-ld/ .