python - 定义一个 xml 来表示图的邻接列表？

Question

我正在开发一个 python 图形库，并且正在使用邻接列表。我正在考虑使用 xml 来表示邻接列表，这样我可以更轻松地存储或读取图表。对于这样的图表:

  A
  |\
  | \
  |  \
  B---C

邻接看起来像

A:[B,C]

B:[A，C]

C:[A,B]

问题来了，怎么转成xml呢？我的 xml 知识(非常)有限，所以我的看起来像:

<graph>
     <node>
     A
     <realtedto>[B,C]</relatedto>
     </node>
     ...
</graph>

您觉得这合适吗？另外，您将如何处理图表可能不简单或有方向性的问题？

Answer 1

好吧，您可以像这样存储链接:

<graph>
 <node id="A" />
 <node id="B" />
 <node id="C" />
 <links>
  <link first="A" second="B" />
  <link first="A" second="C" />
 </links>
</graph>

但是，你会遇到奇怪的情况，比如“A，B 与 B，A 相同吗”？如果你正在做查找。我可能永远不会采用上述方式。另一方面，如果您这样做，就不会存储重复的信息。 (有可能，如果您进行验证以防止逆转)。如果它是一个有向字母，那么该副作用可能是一个特征，因为在这种情况下 A,B IS 与 B,A 不同。

请记住，xml 隐式地将事物存储在层次结构中，而图不一定是没有转换的层次结构，因此不可能在没有某种扭曲的情况下“直接”表示。我可能会做这样的事情:

<graph>
<node id="A">
  <neighbors>
   <neighbor id="B" />
   <neighbor id="C" />
  </neighbors>
</node>
<node id="B">
  <neighbors>
   <neighbor id="A" />
  </neighbors>
</node>
<node id="C">
  <neighbors>
   <neighbor id="A" />
  </neighbors>
</node>
</graph>

不幸的是，您有重复的信息，但是您可以解决排序问题，并且如果您反序列化它，您总是可以引用节点的邻居来进行遍历。如果你想让它成为一个有向字母，你可以分开 <neighbors>进入<inlets>和<outlets> 。或者只是<neighbor>如果您不关心是否能够向后遍历，请在导出侧标记。

如果您希望能够迭代链接，您可以结合使用这两种方法。

这一切都取决于您希望数据具有的功能。