10

我对持久化单个有向图很感兴趣。这个问题不是要求一个全面的图形数据库解决方案，而是一个我可以用来保存和单个任意有向图的文档格式。 我不知道哪种表示法和文件格式是最明智的选择。

我主要担心的是：

  1. 表现力/灵活性——我希望能够表达不同类型的图表。虽然标准用例是一个简单的有向图，但应该可以表示树、循环图、多图。作为最低要求，我希望支持边缘和节点的标记和加权。用于描述higraph和边缘组合/超边缘的符号也是非常可取的，尽管我知道这样的解决方案可能不存在。

  2. Type System-Independence - 我对表示图形的结构质量很感兴趣。一些解决方案包括用于类型化边和节点的可扩展类型系统（例如RDF / OWL）。如果有明确定义的类型元素到基元（节点/边缘/属性）的规范分解，我只会对这种表示感兴趣。我在这里试图避免的是等价图的多种表示的能力，其中等价是不可辨别的。

  3. 规范表示- 应该有一种机制可以规范地表示图（以这样一种方式，可以使用规范表示的词汇等价来确定等价）。

  4. Presentation Independent - 我更喜欢不依赖于图形表示的符号。这将包括空间方向、颜色、字体等。我只对表示数据感兴趣。我不喜欢DOT 语言、DGML或SVG（至少对于这个特定目的）的一个特性是对视觉表示的关注。

  5. 标准化/开放/兼容- 我必须做的实施工作越少越好。如果格式是标准化的并且已经存在用于处理该格式的可靠工具，那么它是更可取的。伴随这一要求的是另一个要求，即格式应该是高度兼容的。微软 DGML的专有性质是我厌恶的一个原因，尽管 Visual Studio 工具和我主要使用 .NET（现在）工作的事实。W3C 发布 RDF 标准的事实是考虑将有限的 RDF 子集作为表示工具的动机。我也很欣赏GXL和GraphML，因为它们具有良好记录的 xml 模式，从而促进了将其数据与任何 xml 兼容的软件包集成的能力。

  6. 简单/可读性- 我欣赏人类可读的语法和易于解释。我也很欣赏简化解析的表示。出于这个原因，我喜欢GML，但我担心它不够主流，无法成为现实的选择。如果 JSON 或 YAML在表示复杂（非 DAG）结构的能力方面不受限制，我也会考虑使用JSON或YAML 。

  7. 效率/简洁表示- 值得考虑的是，无论我最终选择什么格式，都不可避免地必须通过某些网络进行持久化和传输。因此，文件大小是一个相关的考虑因素。

概述

我认识到我很可能无法找到满足我愿望清单上所有标准的解决方案。我只是要求最接近我想要的文件格式，并且不会限制不受支持的用例的可扩展性。

4

3 回答 3

1

我的想法：

  • 我缺少的是您特定的实际目的/领域。

  • 您在特定格式旁边提到了通用 JSON 格式（例如 GraphML，它是 XML 的一个应用程序）。所以我留下了一个问题，如果你考虑或不考虑制作自己的格式。

  • 没有“可用于确定等价的规范表示”解决图同构问题吗？

  • GraphML 似乎涵盖了你的很多理论要求，所以我建议你创建一个 JSON 版本。这也将涵盖要求 6。

  • 然后，您可以在 JSON 格式和 GraphML（可能还有其他格式）之间创建一个转换器。

  • 对于您的要求 7，这又完全取决于实际的图形大小。我的意思是，现在向该死的移动设备发送高达几 MB 的数据并不算多。您提到的（大约）任何格式的几 MB 图表已经是一个相对较大的野兽，具有数万个节点和边缘。

于 2013-05-25T08:14:50.860 回答
1

ObWindyPreamble：在 RDF 世界中，有无数种不同的表面语法格式可供选择。RDF 本身是数据的抽象元模型，而不是直接的“图形语法”。你当然可以直接在 RDF 中表示一个图（因为 RDF 模型是图），但是考虑到你想要表示不同类型的图，你最终可能不得不抽象出来，实际上创建一个 RDF 词汇表来表示不同类型的图表。

总而言之，我不相信 RDF 是最适合您的方式，但如果您选择其中一种，我会说 RDF 的Turtle 语法值得研究。它确实符合可读性和简单性，并且是一个标准（嗯，几乎...... W3C 正在努力对其进行标准化）并具有广泛的（开源）工具支持。

RDF 模型大致遵循集合语义，这意味着不能真正强制执行规范的语法表示：两个文件可以具有不同顺序的信息而不影响实际模型，甚至可以包含重复信息。但是，如果您在生成文件时强制执行简单的排序算法（大多数 RDF 解析器/编写器都支持该算法），您应该能够摆脱基于行的比较和基于表面语法确定图等价性。

举个简单的例子，假设我们有一个非常简单的有向标记图：

 A ---r1---> B ---r2---> C

您可以直接在 RDF 中表示它，如下所示（使用 Turtle 语法）：

 @prefix : <http://example.org/> .

 :A :r1 :B .
 :B :r2 :C .

在更抽象的建模中，您可以执行以下操作：

 @prefix g: <http://example.org/graph-model/> .
 @prefix : <http://example.org/> .

 :A a g:Vertex .
 :B a g:Vertex .
 :C a g:Vertex .

 :r1 a g:DirectedEdge ;
     g:from :A ;
     g:to :B .
 :r2 a g:DirectedEdge ;
     g:from :B ;
     g:to :C .

当然，上面只是一个简单的例子，但希望它说明这可能满足你愿望清单上的很多事情。

顺便说一句，如果您想要更简单，N-Triples也是一种 RDF 语法，它是基于行的，因此很容易以流方式处理。它比 Turtle 稍微冗长一些，但它可能使文件比较更容易。

于 2013-05-06T06:25:29.593 回答
1

平凡的图形格式怎么样：

于 2013-05-30T03:38:42.763 回答