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

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

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

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

解决方案

回答

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

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

回答

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

回答

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

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或者任何其他首选的序列化格式或者作为邻接矩阵来完成。

回答

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

• 邻接表表示
• 邻接矩阵表示

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

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

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

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的循环。

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

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

回答

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

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

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

可以表示为：

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]

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