¿Cómo serializar una estructura de gráfico?

Question

Los archivos planos y las bases de datos relacionales nos dan un mecanismo para serializar datos estructurados. XML es excelente para serializar datos de árbol sin estructura.

Pero muchos problemas se representan mejor mediante gráficos. Un programa de simulación térmica, por ejemplo, trabajará con nodos de temperatura conectados entre sí a través de bordes resistivos.

Entonces, ¿cuál es la mejor manera de serializar una estructura de gráfico? Sé que XML puede, en cierta medida, hacerlo, de la misma manera que una base de datos relacional puede serializar una compleja red de objetos: generalmente funciona, pero puede ponerse fea.

Conozco el lenguaje de puntos utilizado por el programa graphviz, pero no estoy seguro de que esta sea la mejor manera de hacerlo. Esta pregunta es probablemente el tipo de cosa en que la academia podría estar trabajando y me encantaría tener referencias a cualquier documento que discuta esto.

Answer 1

¿Cómo se representa el gráfico en la memoria?
Básicamente, usted tiene dos (bueno) opciones:

• an adjacency list representation
• an adjacency matrix representation

en el que la representación de la lista de adyacencia es la mejor opción para un gráfico escasa, y una representación de la matriz de los grafos densos .

Si usó tales representaciones, entonces podría serializar esas representaciones en su lugar.

Si tiene que ser humanamente legible, puede optar por crear su propio algoritmo de serialización.Por ejemplo, podría escribir la representación matricial como lo haría con cualquier matriz "normal": acaba de imprimir las columnas y filas, y todos los datos en él de este modo:

1 2 3 
1 #t #f #f 
2 #f #f #t 
3 #f #t #f 

(esto es un no representación optimizada y no ponderada, pero se puede usar para gráficos dirigidos)

Answer 2

XML es muy detallado. Cada vez que lo hago, hago mi propio. Aquí hay un ejemplo de un gráfico acíclico dirigido a 3 nodos. Es bastante compacto y hace todo lo que necesito que haga:

0: foo 
1: bar 
2: bat 
---- 
0 1 
0 2 
1 2 

Answer 3

En un plano más práctico menos académico, en CubicTest utilizamos Xstream (Java) para serializar pruebas hacia y desde XML. Xstream maneja las relaciones de objeto estructuradas por gráficos, por lo que puede aprender una o dos cosas al mirar su fuente y el xml resultante. Sin embargo, tiene razón acerca de feo, los archivos xml generados no se ven bonitos.

Answer 4

Un ejemplo que podría estar familiarizado es la serialización de Java. Esto se serializa de manera efectiva por gráfico, siendo cada instancia de objeto un nodo, y cada referencia es un borde. El algoritmo utilizado es recursivo, pero omitiendo los duplicados. Así que el pseudo código sería:

serialize(x): 
    done - a set of serialized objects 
    if(serialized(x, done)) then return 
    otherwise: 
     record properties of x 
     record x as serialized in done 
     for each neighbour/child of x: serialize(child) 

Otra forma de curso es como una lista de nodos y los bordes, lo que puede hacerse como XML, o en cualquier otro formato de serialización preferida, o como una matriz de adyacencia.

Answer 5

Normalmente, las relaciones en XML se muestran mediante la relación padre/hijo. XML puede manejar datos de gráficos pero no de esta manera. Para manejar gráficos en XML, debe usar los tipos de esquema xs:ID y xs:IDREF.

En un ejemplo, supongamos que node/@ id es un tipo xs: ID y que el enlace/@ ref es un tipo xs: IDREF. El siguiente XML muestra el ciclo de tres nodos 1 -> 2 -> 3 -> 1.

<data> 
    <node id="1"> 
    <link ref="2"/> 
    </node> 
    <node id="2"> 
    <link ref="3"/> 
    </node> 
    <node id="3"> 
    <link ref="1"/> 
    </node> 
</data> 

Muchas herramientas de desarrollo tienen soporte para ID y IDREF también. He utilizado JAXB (Java XML de Java Binding. Es compatible con éstos a través de los @XmlID y los @XmlIDREF anotaciones. Usted puede construir su gráfico usando objetos planos Java y luego usar JAXB para manejar la serialización real a XML.

Answer 6

listas de adyacencia y de adyacencia las matrices son las dos formas comunes de representar gráficos en la memoria. La primera decisión que debe tomar al decidir entre estos dos es para qué desea optimizarlas. Las listas de adyacencia son muy rápidas si necesita, por ejemplo, obtener la lista de Por otro lado, si está haciendo muchas pruebas de existencia de bordes o tiene una representación gráfica de una cadena de markov, probablemente favorecerá una matriz de adyacencia.

La siguiente pregunta es: nee Para tener en cuenta es cuánto debe caber en la memoria. En la mayoría de los casos, cuando el número de aristas en el gráfico es mucho más pequeño que el número total de aristas posibles, una lista de adyacencia va a ser más eficiente, ya que solo necesita almacenar los bordes que realmente existen. Un medio feliz es representar la matriz de adyacencia en formato comprimido de filas dispersas en el que se conserva un vector de las entradas distintas de cero de arriba a abajo a la derecha, un vector correspondiente que indica en qué columnas se pueden encontrar las entradas distintas de cero, y un tercer vector que indica el inicio de cada fila en el vector de entrada de columna.

[[0.0, 0.0, 0.3, 0.1] 
[0.1, 0.0, 0.0, 0.0] 
[0.0, 0.0, 0.0, 0.0] 
[0.5, 0.2, 0.0, 0.3]] 

se puede representar como:

vals: [0.3, 0.1, 0.1, 0.5, 0.2, 0.3] 
cols: [2, 3, 0, 0, 1, 4] 
rows: [0,  2, null, 4] 

fila escaso comprimido es efectivamente una lista de adyacencia (los índices de columnas funcionan de la misma manera), pero el formato se presta un poco más limpiamente a operaciones con matrices.