关于序列化：如何序列化图形结构？

How to serialize a graph structure?

平面文件和关系数据库为我们提供了一种序列化结构化数据的机制。 XML对序列化非结构化的树状数据非常有用。

但是许多问题最好用图形表示。例如，热仿真程序将与通过电阻性边缘相互连接的温度节点一起工作。

那么序列化图结构的最佳方法是什么？我知道XML在某种程度上可以做到这一点，就像关系数据库可以序列化复杂的对象网络一样：它通常可以工作，但很容易变得丑陋。

我知道graphviz程序使用的点语言，但是我不确定这是最好的方法。这个问题可能是学术界正在研究的问题，我很乐意参考任何讨论此问题的论文。

您如何在内存中表示图形？
基本上，您有两个(好的)选择：

邻接表表示
邻接矩阵表示

其中，邻接表表示最好用于稀疏图，矩阵表示最好用于稠密图。

如果使用这样的表示形式，则可以序列化这些表示形式。

如果必须可读，您仍然可以选择创建自己的序列化算法。例如，您可以像处理任何"常规"矩阵一样写下矩阵表示形式：只需打印出列和行以及其中的所有数据，如下所示：

1
2
3
4

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

(这是非优化，非加权的表示形式，但可用于有向图)

XML中的关系通常由父/子关系显示。 XML可以处理图形数据，但不能以这种方式。要处理XML中的图形，应使用xs：ID和xs：IDREF模式类型。

在一个示例中，假定node / @ id是xs：ID类型，而link / @ ref是xs：IDREF类型。以下XML显示了三个节点1-> 2-> 3-> 1的循环。

1
2
3
4
5
6
7
8
9
10
11

许多开发工具也支持ID和IDREF。我使用过Java的JAXB(Java XML绑定。它通过@XmlID和@XmlIDREF批注支持它们。您可以使用纯Java对象构建图形，然后使用JAXB来处理对XML的实际序列化。

XML非常冗长。每当我这样做时，我都会自己滚动。这是3节点有向无环图的示例。它非常紧凑，可以完成我需要做的所有事情：

1
2
3
4
5
6
7

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

邻接表和邻接矩阵是表示内存中图形的两种常用方法。在这两者之间做出决定时，您需要做的第一个决定就是要进行优化。如果需要，例如，获取顶点邻居的列表，则邻接列表非常快。另一方面，如果您要进行大量的边缘存在性测试或具有马尔可夫链的图形表示，那么您可能希望使用邻接矩阵。

您需要考虑的下一个问题是需要容纳多少内存。在大多数情况下，图形中的边数比可能的边总数小得多，因此邻接表将更加有效，因为您只需要存储实际存在的边即可。一个快乐的媒介是用压缩的稀疏行格式表示邻接矩阵，在该矩阵中，您从左上角到右下角保留了非零条目的向量，指示了可以在哪些列中找到非零条目的对应向量，以及第三个向量表示列输入向量中每行的开始。

1
2
3
4

[[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]]

可以表示为：

1
2
3

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]

压缩的稀疏行实际上是一个邻接表(列索引的功能相同)，但是格式更适合矩阵操作。

您可能熟悉的一个示例是Java序列化。这有效地通过图进行了序列化，每个对象实例是一个节点，每个引用是一个边。使用的算法是递归的，但是跳过重复项。因此，伪代码为：

1
2
3
4
5
6
7

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)

当然，另一种方式是作为节点和边的列表，可以将其作为XML或任何其他首选的序列化格式或作为邻接矩阵来完成。

在一个不太学术，更实用的注释上，在CubicTest中，我们使用Xstream(Java)在XML前后进行测试序列化。 Xstream处理图结构的对象关系，因此您可以通过查看它的源和生成的xml来学习一两个东西。您对丑陋的部分是正确的，但是生成的xml文件看起来并不漂亮。