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

tipos de graficos estadisticos pdf

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.

Sé sobre 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 representas tu gráfico en la memoria?
Básicamente tienes dos (buenas) opciones:

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

en el que la representación de la lista de adyacencia se utiliza mejor para un gráfico disperso, y una representación de matriz para los gráficos densos.

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

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

 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 se puede usar para gráficos dirigidos)

Answer 2

En una nota menos académica, más práctica, en CubicTest utilizamos Xstream (Java) para serializar las 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, tienes razón acerca de la parte fea , los archivos xml generados no se ven bonitos.

Answer 3

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 lo que 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á haciendo muchas pruebas de existencia de bordes o tiene una representación gráfica de una cadena de markov, entonces probablemente favorecería una matriz de adyacencia.

La siguiente pregunta que debe considerar es cuánto necesita encajar 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]]

puede ser representado 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 columna funcionan de la misma manera), pero el formato se presta un poco más limpio a las operaciones de la matriz.

Answer 4

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 también admiten ID e IDREF. Utilicé JAXB de Java (Enlace XML de Java. Es compatible con las @XmlID y @XmlIDREF . Puede construir su gráfico utilizando objetos planos de Java y luego usar JAXB para manejar la serialización real en XML.

Answer 5

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. Entonces 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, 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 6

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 hacer:

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