在Tinkerpop 3.1中寻找两个节点之间最短路径的最佳方法

Question

在Tinkerpop 3.1中寻找两个节点之间最短路径的最佳方法

9

我知道这个问题被问过很多次，但是我没有找到任何关于Tinkerpop的最新版本（3.1）的参考资料，其中包含了许多我们可以在遍历中使用的新有用功能。

假设我需要查找节点3和4之间的最短路径。这个遍历是否正确？

g.V(3).repeat(out()).until(id().is(4).and().simplePath()).path().limit(1)

我假设当我循环执行BFS搜索时(因此，第一个结果是最短路径)，就像使用loop()函数时的情况一样。

此外，在until步骤中有没有办法包含之前绑定的变量(通过使用as步骤)？更准确地说，我试图在遍历过程中选择两个节点，然后找到它们之间的最短路径，例如，

g.V().match(
__as('e0').out('Feedbacks').as('e1'),
__as('e0').repeat(out('Meets')).until(<I reach e1>).path().<get_length>.as('len')
).select('e0', 'e1', 'len')

最后，从之前的遍历中可以看出，我不清楚如何获得最短路径的长度。可以使用下面这个方法：

g.V(3).repeat(out()).until(id().is(4).and().simplePath()).path().size()

返回结果的大小（返回的行数），而

g.V(3).repeat(out()).until(id().is(4).and().simplePath()).path().by(__size())

返回一个错误。

这是我正在尝试的图表，如果有人想玩一下，可以试试。

graph = TinkerGraph.open()
e0 = graph.addVertex(T.id, 0, label, "User", "name", "e0")
e1 = graph.addVertex(T.id, 1, label, "User", "name", "e1")
e2 = graph.addVertex(T.id, 2, label, "User", "name", "e2")
e3 = graph.addVertex(T.id, 3, label, "User", "name", "e3")
e4 = graph.addVertex(T.id, 4, label, "User", "name", "e4")
e0.addEdge("Feedbacks", e2)
e0.addEdge("Meets", e1)
e2.addEdge("Feedbacks", e4)
e2.addEdge("Meets", e4)
e3.addEdge("Feedbacks", e0)
e3.addEdge("Meets", e2)
e4.addEdge("Feedbacks", e0)
g = graph.traversal()

- Alberto

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Kuppitz · Accepted Answer

你的最短路径查询还有一个稍微更短的变体：

g.V(3).repeat(out().simplePath()).until(hasId(4)).path().limit(1)

你的假设，第一条路径总是最短的，是正确的。要获取路径长度，可以使用count(local)：

g.V(3).repeat(out().simplePath()).until(hasId(4)).path().count(local)

更新

根据您的最新查询，这个应该解决问题：

g.V().as("e0").out("Feedbacks").as("e1").select("e0").
      repeat(out("Meets")).until(where(eq("e1"))).path().
      map(union(count(local), constant(-2)).sum()).as("len").
      select("e0","e1","len")

我从总路线长度中减去2，因为我认为您只对repeat()块遍历的路径长度感兴趣，而起始处的out().select()不应计入其中。如果不是这种情况，那么您可以将第三行简单替换为count(local).as("len")。。