题
平面文件和关系数据库为我们提供了一种序列化结构化数据的机制。XML 非常适合序列化非结构化树状数据。
但许多问题最好用图表来表示。例如,热模拟程序将使用通过电阻边缘相互连接的温度节点。
那么序列化图结构的最佳方法是什么?我知道 XML 在某种程度上可以做到这一点——就像关系数据库可以序列化复杂的对象网络一样:它通常有效,但很容易变得丑陋。
我知道 graphviz 程序使用的点语言,但我不确定这是最好的方法。这个问题可能是学术界可能正在研究的问题,我很想参考任何讨论这个问题的论文。
其他提示
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 Binding.它通过以下方式支持这些 @XmlID 和 @XmlIDREF 注释。您可以使用普通 Java 对象构建图形,然后使用 JAXB 处理到 XML 的实际序列化。
XML 非常冗长。每当我这样做时,我都会自己滚动。这是 3 节点有向无环图的示例。它非常紧凑,可以完成我需要它做的一切:
0: foo
1: bar
2: bat
----
0 1
0 2
1 2
您可能熟悉的一个示例是 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 或任何其他首选序列化格式或作为邻接矩阵来完成。
邻接表和邻接矩阵是在内存中表示图的两种常见方法。在这两者之间做出选择时,您需要做出的第一个决定是您想要优化的内容。例如,如果您需要获取顶点的邻居列表,则邻接列表非常快。另一方面,如果您正在对边的存在进行大量测试或有马尔可夫链的图形表示,那么您可能会喜欢邻接矩阵。
您需要考虑的下一个问题是您需要在内存中容纳多少内容。在大多数情况下,图中的边数远小于可能的边总数,邻接列表会更有效,因为您只需要存储实际存在的边。一个快乐的媒介是以压缩稀疏行格式表示邻接矩阵,其中保留从左上到右下的非零条目的向量,以及指示可以在哪些列中找到非零条目的相应向量,以及第三个向量指示列条目向量中每行的开始。
[[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]
压缩稀疏行实际上是一个邻接列表(列索引以相同的方式起作用),但该格式使其更适合矩阵运算。