¿Cómo serializar una estructura gráfica?

Question

Los archivos planos y las bases de datos relacionales nos brindan un mecanismo para serializar datos estructurados.XML es excelente para serializar datos en forma de árbol no estructurados.

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

Entonces, ¿cuál es la mejor manera de serializar una estructura gráfica?Sé que XML puede, hasta cierto punto, hacerlo, de la misma manera que una base de datos relacional puede serializar una red compleja de objetos:Por lo general, funciona, pero puede volverse feo fácilmente.

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

Answer 1

¿Cómo representas tu gráfica en la memoria?
Básicamente tienes dos (buenas) opciones:

• una representación de lista de adyacencia
• una representación matricial de adyacencia

en el que la representación de lista de adyacencia se utiliza mejor para gráficos dispersos y una representación matricial para gráficos densos.

Si utilizó tales representaciones, entonces podría serializar esas representaciones.

Si tiene que ser legible por humanos aún puedes optar por crear tu propio algoritmo de serialización.Por ejemplo, podría escribir la representación matricial como lo haría con cualquier matriz "normal":simplemente imprima las columnas y filas, y todos los datos que contiene, así:

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

(Esta es una representación no optimizada y no ponderada, pero puede usarse para gráficos dirigidos)

Answer 2

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 se debe utilizar el xs: identificación y xs:IDREF tipos de esquema.

En un ejemplo, supongamos que node/@id es un tipo xs:ID y que link/@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 también son compatibles con ID e IDREF.He utilizado JAXB de Java (Java XML Binding.Los apoya a través de la @XmlID y el @XmlIDREF anotaciones.Puede crear su gráfico utilizando objetos Java simples y luego usar JAXB para manejar la serialización real a XML.

Answer 3

XML es muy detallado.Siempre que lo hago, hago el mío.A continuación se muestra un ejemplo de un gráfico acíclico dirigido de 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 4

Un ejemplo que quizás le resulte familiar es la serialización de Java.Esto se serializa efectivamente por gráfico, donde cada instancia de objeto es un nodo y cada referencia es una arista.El algoritmo utilizado es recursivo, pero omitiendo duplicados.Entonces el pseudocó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, por supuesto, es como una lista de nodos y bordes, que se puede hacer como XML, o en cualquier otro formato de serialización preferido, o como una matriz de adyacencia.

Answer 5

Las listas de adyacencia y las matrices de adyacencia 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 optimizar.Las listas de adyacencia son muy rápidas si necesita, por ejemplo, obtener la lista de vecinos de un vértice.Por otro lado, si está realizando muchas pruebas para determinar la existencia de bordes o tiene una representación gráfica de una cadena de Markov, entonces probablemente prefiera una matriz de adyacencia.

La siguiente pregunta que debes considerar es cuánto necesitas guardar en la memoria.En la mayoría de los casos, donde el número de aristas en el gráfico es mucho menor que el número total de aristas posibles, una lista de adyacencia será más eficiente, ya que solo necesita almacenar las aristas que realmente existen.Un buen punto medio es representar la matriz de adyacencia en formato de fila dispersa comprimido en el que se mantiene un vector de las entradas distintas de cero desde la parte superior izquierda a la inferior 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]

La fila dispersa comprimida es efectivamente una lista de adyacencia (los índices de las columnas funcionan de la misma manera), pero el formato se presta un poco más claramente a las operaciones matriciales.

Answer 6

En una nota menos académica y más práctica, en Prueba cúbica usamos Xstream (Java) para serializar pruebas hacia y desde xml.Xstream maneja relaciones de objetos estructuradas en gráficos, por lo que puede aprender un par de cosas al observar su fuente y el xml resultante.Tienes razón sobre el feo Sin embargo, en parte, los archivos xml generados no se ven bonitos.