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

Question

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

假设我必须找到 a 节点 3 和 4 之间的最短路径。这是穿越音吗？

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

这里我假设当我循环时执行 BFS 搜索（因此，第一个结果是最短路径）作为 it seems that this was the case with the loop() function。

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

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()

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

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

returns 一个错误。

这是我正在试验的图表，如果有人想玩一下的话。

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()

Answer 1

您的最短路径查询有一个稍短的变体：

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()不应该被包括在内。如果不是这种情况，那么您只需将第 3 行替换为 count(local).as("len")..

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

Best way to find a shortest path between two nodes in Tinkerpop 3.1

shortest-path

gremlin

tinkerpop3