31

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

但是很多问题最好用图表来表示。例如，热模拟程序将使用通过电阻边缘相互连接的温度节点。

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

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

4

6 回答 6

15

你如何在内存中表示你的图表？
基本上你有两个（好的）选择：

其中邻接表表示最适合用于稀疏图，而矩阵表示最适合用于密集图。

如果您使用此类表示，则可以改为序列化这些表示。

如果它必须是人类可读的，您仍然可以选择创建自己的序列化算法。例如，您可以像使用任何“普通”矩阵一样写下矩阵表示：只需打印列和行，以及其中的所有数据，如下所示：

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

（这是一种非优化、非加权表示，但可用于有向图）

于 2008-09-09T13:04:14.093 回答
8

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 序列化。

于 2008-09-09T13:12:52.640 回答
5

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

0: foo
1: bar
2: bat
----
0 1
0 2
1 2
于 2008-09-09T12:58:56.417 回答
1

您可能熟悉的一个示例是 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 或任何其他首选的序列化格式或作为邻接矩阵来完成。

于 2008-09-09T13:03:53.627 回答
1

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

您需要考虑的下一个问题是您需要多少才能适应内存。在大多数情况下，图中边的数量远小于可能边的总数，邻接列表会更有效，因为您只需要存储实际存在的边。一个快乐的媒介是以压缩稀疏行格式表示邻接矩阵，其中您保留从左上角到右下角的非零条目的向量，相应的向量指示可以在哪些列中找到非零条目，以及第三个向量，指示列条目向量中每一行的开始。

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

压缩稀疏行实际上是一个邻接列表（列索引的功能相同），但该格式更适合矩阵运算。

于 2008-09-28T03:07:21.917 回答
0

在一个不那么学术、更实用的注释中，在CubicTest中，我们使用Xstream (Java) 来序列化与 xml 之间的测试。Xstream 处理图形结构的对象关系，因此您可能会从查看它的源代码和生成的 xml 中学到一两件事。不过，您对丑陋的部分是正确的，生成的 xml 文件看起来并不漂亮。

于 2008-09-09T13:01:23.150 回答