如何序列化图结构? [英] How to serialize a graph structure?
问题描述
平面文件和关系数据库为我们提供了一种序列化结构化数据的机制. XML对序列化非结构化的树状数据非常有用.
Flat files and relational databases give us a mechanism to serialize structured data. XML is superb for serializing un-structured tree-like data.
但是许多问题最好用图形表示.例如，一个热仿真程序将使用通过电阻性边缘相互连接的温度节点.
But many problems are best represented by graphs. A thermal simulation program will, for instance, work with temperature nodes connected to each others through resistive edges.
那么序列化图结构的最佳方法是什么?我知道XML在某种程度上可以做到这一点，就像关系数据库可以序列化复杂的对象网络一样:它通常可以工作，但很容易变得难看.
So what is the best way to serialize a graph structure? I know XML can, to some extent, do it---in the same way that a relational database can serialize a complex web of objects: it usually works but can easily get ugly.
我知道graphviz程序使用的点语言，但是我不确定这是最好的方法.这个问题可能是学术界可能正在研究的事情，我很乐意参考任何讨论此事的论文.
I know about the dot language used by the graphviz program, but I'm not sure this is the best way to do it. This question is probably the sort of thing academia might be working on and I'd love to have references to any papers discussing this.
推荐答案
如何在内存中表示图形?
基本上，您有两个(好的)选择:
How do you represent your graph in memory?
Basically you have two (good) options:
- an adjacency list representation
- an adjacency matrix representation
其中稀疏图最好使用邻接表表示，而稠密图最好用矩阵表示.
in which the adjacency list representation is best used for a sparse graph, and a matrix representation for the dense graphs.
如果使用这样的表示形式，则可以序列化这些表示形式.
If you used suchs representations then you could serialize those representations instead.
如果必须是可读性，您仍然可以选择创建自己的序列化算法.例如，您可以像处理任何普通"矩阵一样写下矩阵表示形式:只需打印出列和行以及其中的所有数据，如下所示:
If it has to be human readable you could still opt for creating your own serialization algorithm. For example you could write down the matrix representation like you would do with any "normal" matrix: just print out the columns and rows, and all the data in it like so:
1 2 3
1 #t #f #f
2 #f #f #t
3 #f #t #f
(这是未经优化的，非加权的表示形式，但可用于有向图)
(this is a non-optimized, non weighted representation, but can be used for directed graphs)
这篇关于如何序列化图结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
