0

为了数据交换的目的，我正在研究可能被认为是 XML 格式的有限深度图的表示形式。问题点是如何引用边缘标签中的节点。我看到的两种策略是 a) 使用唯一标识符或 b) 使用路径。

唯一 ID：

<graph id="g0">
  <node id="n0"/>
  <node id="n1"/>
  <edge from="n1" to="n0"/>
</graph>
<graph id="g1">
  <node id="n2"/>
</graph>
<edge from="n2" to="n1"/>

路径：

<graph id="0">
  <node id="0"/>
  <node id="1"/>
  <node id="2"/>
  <edge from="1" to="0"/>
  <edge from="2" to="1"/>
</graph>
<graph id="1">
  <node id="0"/>
</graph>
<edge from="1:0" to="0:2"/>

这类事情的标准程序是什么？从我收集到的信息来看，唯一标识符方法似乎更为普遍。我的问题是当图表变得非常大时，有：

  • 一个非常大的哈希表的必要性，该哈希表将对象映射到它们的 ID，以便从 XML 文件读取/写入边缘。
  • 文件本身比使用路径编写的文件大，因为如果边缘在图形内部，则不能省略冗余路径组件。

想法？

更新 1：

请注意，它不是一个平面图。它的一个或多个图形相互连接。它们每个都有本地索引的元素，但是将它们全部展平并跟踪它们的边缘有点麻烦。

更新 1.1：注意到 GraphML 中的子图，它们实际上使用了复杂的键，从而可以将本地节点 id 与全局节点分开。

更新 2：

是的，显然这不是格式良好的 XML，缺少标记和各种模式声明。

4

2 回答 2

3

有一个描述这种图的模式：见GraphML

例子：

<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"  
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
     http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
  <graph id="G" edgedefault="undirected">
    <node id="n0"/>
    <node id="n1"/>
    <node id="n2"/>
    <node id="n3"/>
    <node id="n4"/>
    <node id="n5"/>
    <node id="n6"/>
    <node id="n7"/>
    <node id="n8"/>
    <node id="n9"/>
    <node id="n10"/>
    <edge source="n0" target="n2"/>
    <edge source="n1" target="n2"/>
    <edge source="n2" target="n3"/>
    <edge source="n3" target="n5"/>
    <edge source="n3" target="n4"/>
    <edge source="n4" target="n6"/>
    <edge source="n6" target="n5"/>
    <edge source="n5" target="n7"/>
    <edge source="n6" target="n8"/>
    <edge source="n8" target="n7"/>
    <edge source="n8" target="n9"/>
    <edge source="n8" target="n10"/>
  </graph>
</graphml>
于 2009-07-06T19:07:28.957 回答
0

文件本身比使用路径编写的文件大，因为如果边缘在图形内部，则不能省略冗余路径组件。

这一点是过早优化。XML 解析器/编写器不会因大文件而窒息，如果存储大小是一个问题，XML 通常使用 ZIP 可以很好地压缩。

一个非常大的哈希表的必要性，该哈希表将对象映射到它们的 ID，以便从 XML 文件读取/写入边缘。

这是一个实施问题。如果您将 XML 读/写例程写入图形、节点和边缘类本身，而不是尝试将映射维护在单独的结构中，那么您当然可以避免使用这样的大型哈希表。图形很容易序列化和反序列化。

唯一的 ID 可能是要走的路。如果您以类似于您提出的分层方式的方式构建 ID，那么它也将是相对易于阅读的，这是 XML 的目标之一。

于 2009-07-06T19:09:21.887 回答