Quiero representar un DAG como texto JSON y me pregunto si alguien ha intentado esto y cualquier problema que hayan tratado con respecto a validar si el JSON es realmente un DAG.¿Cómo se almacena un gráfico acíclico dirigido (DAG) como JSON?
Etiquete cada nodo y cree una lista de bordes. Es decir, para cada tienda nodo de los nodos que tiene bordes para, por ejemplo:
{
"a": [ "b", "c", "d" ],
"b": [ "d" ],
"c": [ "d" ],
"d": [ ]
}
Puede almacenar muchos tipos de gráficos de esta manera, no sólo los DAG, por lo que tendrá que procesar posteriormente para hacerla Seguro que no tiene bucles. Simplemente elija un nodo, DFS, si ve un nodo más de una vez, no es un DAG. Luego, elimine 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 los nodos principales, ya que esa es información redundante. Puede generarlos luego de cargar el gráfico si necesita esos datos.
¿Hay algún inconveniente en almacenarlo inversamente (teniendo los valores de la matriz como los nodos "de" en lugar de "a")? Pensaría que esto sería mejor si estás tratando de hacer un tipo topológico. –
Estrictamente hablando, no puede hacerlo directamente con JSON. Tendría que idear su propio modo de representar objetos que puedan identificarse por referencia en cualquier otro lugar de la estructura de datos, y luego tendría que postprocesar el resultado de deserializar la cadena JSON.
No se puede hacer 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 idea de que el valor de una propiedad debe ser el valor de otra propiedad en otros lugares en 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.
En un DAG, un nodo puede tener dos padres. Piense en la representación de una expresión en un lenguaje de programación (por ejemplo, JavaScript :-) con dos referencias a una sola variable. Tradicionalmente, esos dos puntos en la expresión se referirían al mismo nodo. No hay ciclos en un DAG (por definición) porque (generalmente, no necesariamente, supongo) todos los enlaces "apuntan hacia abajo" el gráfico, por lo que nunca "vuelve a subir". Es como un árbol, excepto donde se fusionan los nodos iguales. – Pointy
Ja, ja, ese comentario fue en respuesta a una pregunta sobre esto que tiene que ver con los ciclos, así que lo dejo allí. – Pointy
Sí, error básico de comprensión CS por mi parte ;-) Gracias por explicarme. –
JSON no tiene una función nativa para representar los DAG a menos que haga su propia convención para representar los datos vinculados. JSON-LD (una propuesta W3C) es una extensión JSON que intenta hacer exactamente eso. La propuesta se puede encontrar aquí: http://json-ld.org/spec/latest/json-ld/.
Puede que los DAG no tengan una sola raíz si obtengo el DAG correcto. Entonces, ¿cómo secar el modelo si no está seguro de verlo? –
Cualquier objeto JSON definitivamente será un DAG. – Pointy