Xquery:计算作者之间的距离

Question

我想计算书籍作者之间的距离。一起出版一本书的作者有距离1。此外，如果A和B没有一起出版一本书，但它们都与C一起出版，那么A和B之间的距离为2。

。

这是一个XML文件：

<root>
     <book title="book1">
          <author> Thibaut </author>
          <author> Luc </author>
     </book>
     <book title="book2">
          <author> Luc </author>
          <author> Jay </author>
     </book>
     <book title="book3">
          <author> Jay </author>
          <author> Henry </author>
     </book>
</root>

根据此XML，作者" thibaut"和其他人之间的距离如下：

• thibaut和1的luc距离（因为他们在一起有发布者书1 .. thibaut-> luc）
• Thibaut和Jay 2的距离（因为Thibaut/Luc都有出版商，Luc/Jay共同出版商，因此Thibaut和Jay之间的距离是2 ... Thibaut- Thibaut-> Luc-> Luc-> Jay）
）
• Thibaut和Henry 3的距离（因为Thibaut-> Luc-> Jay-> Henry）
• 我的XML示例很短，但是距离的距离可能会更高

对于我的XML文件中的每个作者X，我需要与其他所有作者计算距离（x！= y，所以不是同一个作者）Anabody是否知道如何在Xquery中进行编码？还是对算法有想法？

任何帮助都赞赏，谢谢！

Answer 1

您需要以某种方式表示内存中的图形，以便可以在其上运行最短路径算法。实际上，您的上面文档可以看作是图表表示，但可能是多余的（同一对作者可能一起出版了多本书）。

更好的图表可以是（除其他）邻接列表，邻接矩阵或入射矩阵。请参阅此处：http：//en.wikipedia.org/wiki/graph_(abstract_data_type)

由于您的图形可能稀疏，因此您应该选择邻接列表。邻接列表是形式的节点 -> list [node]，这意味着它将每个节点映射到其相邻节点的列表。在Java中，您将选择一张地图（例如hashmap）将其存储在内存中。为了运行图形算法，数据结构的查找时间应较低。Xquery没有地图，但是您可以创建XML片段作为变量的值。这是一个例子：

let $a := 
  <map>
    <author>
        <name>Luc</name>
        <coauthors>
          <name>Thibault</name>
        </coauthors>
    </author>
    <author>
      <name>Jay</name>
      <coauthors>
        <name>Henry</name>
        <name>Luc</name>
      </coauthors>
      ...
    </author>
  </map>    

请注意，这不是完整的图表表示，而只是边缘的一个子集。您需要定义一个子程序，该子程序从输入文档中计算此中间体结果。然后，您可以定义一个实用程序功能，该功能为您提供了使用此中间结果的给定作者名称的紧密相邻作者。基于此，您可以实现最短的路径算法。

请注意，上面的图表表示对查找相邻节点不会有效，我相信很难为相邻节点编码有效的查找功能。上面提到的查找功能将需要在最坏情况下遍历整个中间结果（如果您查找最后作者的相邻节点）。如果您担心运行时，我建议使用您选择的通用编程语言（例如Java）。如果图表表示不适合内存，请使用某种磁盘索引结构（例如，由关系数据库提供）。