1

我正在研究一个 python 图形库,我正在使用邻接列表。我正在考虑使用 xml 来表示邻接列表,这样我就可以更轻松地存储到图形或从图形中读取。对于这样的图表:

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

邻接看起来像

A:[B,C]

B:[A,C]

出租车]

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

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

你觉得这合适吗?此外,您将如何处理图表可能不简单或方向性的问题?

4

1 回答 1

2

Welp,您可以像这样存储您的链接:

<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与 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>and <outlets>。或者<neighbor>,如果您不关心能够向后遍历,则只需在出口侧进行标记。

如果您希望能够遍历您的链接,您可以结合这两种方法。

这一切都归结为您希望数据具有的功能。

于 2013-01-28T19:15:49.363 回答