如何序列化图结构？

StackOverflow https://stackoverflow.com/questions/51783

  •  09-06-2019
  •  | 
  •  

题

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

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

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

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

有帮助吗？

解决方案

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

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

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

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

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

压缩稀疏行实际上是一个邻接列表（列索引以相同的方式起作用），但该格式使其更适合矩阵运算。

少一点学术性，多一点实用性， 立方测试 我们用 流媒体 (Java) 将测试序列化到 xml 或从 xml 序列化测试。Xstream 处理图形结构的对象关系，因此您可以通过查看它的源代码和生成的 xml 学到一两件事。你说得对 丑陋的 不过，生成的 xml 文件看起来不太漂亮。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top