2

嗨，用 XML 表示图形的最佳方法是什么，其中一个节点可以是父节点的子节点，也可以是另一个子节点的父节点。它可以引用自己，并且多个节点可以有相同的父节点。一个节点可以有多个父节点。所有节点都来自同一类。我想有效地构建它，这样如果我可以从父节点了解子节点，我就可以转到特定的子标签，而不必遍历所有节点。是否可以？例如这里是一个概述，

A->B,C,D

B->C,D

它可能看起来像

<Node name=A>
 <childNode name=B>
 <childNode name=C>
 <childNode name=D>
</Node>

<Node name=B>
 <childNode name=C>
 <childNode name=D>
</Node>

那么还有比这更好的方法吗？每当我从 A 即 B 得到一个孩子时，我基本上必须遍历所有节点并将名称属性与 B 匹配以找到代表 B 的节点。我能以某种方式更快地做到这一点吗？

4

3 回答 3

7

既然你有一个图，而不是你最初想到的树，为什么不使用GraphML呢？

GraphML 是一种全面且易于使用的图形文件格式。它由描述图形结构属性的语言核心和添加特定应用数据的灵活扩展机制组成。

与许多其他图形文件格式不同，GraphML 不使用自定义语法。相反，它基于 XML，因此非常适合作为各种服务生成、归档或处理图的公分母。

于 2012-10-15T23:52:10.180 回答
0

好吧，我不能说我完全理解您的问题，但我认为您正在尝试从 XML 文件以高级语言重建（有向）图，对吗？了解您在高级语言中的表示形式会有所帮助。或者语言，实际上。假设 C++ 和邻接表：

我首先创建一个map<string, Node*>，将名称映射到节点。我的 XML 看起来像这样：

<edge from='A' to='B' />
<edge from='A' to='C' />
<edge from='A' to='D' />
<edge from='B' to='C' />
<edge from='B' to='D' />

这是相当紧凑的，我可以用 SAX 解析器来解析它，这总是很好的。当我按顺序读取边缘时，我检查我的地图中是否已经有节点：如果没有，我存储它们：

if(mapping.find(from) == map.end()) map.insert(make_pair(from, new Node()));
if(mapping.find(to) == map.end()) map.insert(make_pair(to, new Node()));

一旦两个末端节点都在地图中，我们可以通过以下方式添加边：

mapping[from]->add_egde_to(mapping[to]);

解析完成后，您将拥有地图中的节点，并按名称很好地排序。

无论如何，您可能想查看 Wikipedia's summary about graph representations，这可能会给您一些想法。

于 2012-10-15T23:47:06.297 回答
0

看看 RDF/XML。

RDF 是由三元组（主语、谓语、宾语）组成的语义网络（链接数据）的简单数据模型。它可以表示图形，并且可以以多种格式序列化，包括 xml、json (json-ld) 和 turtle。

于 2018-06-18T19:04:32.037 回答