如何序列化图形结构？

Question

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

但是很多问题最好用图表来表示.例如,热模拟程序将通过电阻边缘与彼此连接的温度节点一起工作.

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

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

Answer 1

你如何在内存中表示你的图表？
基本上你有两个(好的)选择:

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

其中邻接列表表示最好用于稀疏图,以及密集图的矩阵表示.

如果您使用了这样的表示,那么您可以序列化这些表示.

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

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

(这是一个非优化的非加权表示,但可以用于有向图)

Answer 2

通常,父/子关系显示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序列化.

Answer 3

XML非常冗长.每当我这样做,我就会自己动手.这是一个3节点有向无环图的例子.它非常紧凑,可以做我需要做的一切:

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