我正在将 JanusGraph 与 Gremlin 和 this 一起使用数据集包含 2.6k 节点和 6.6k 边(两边各 3.3k 边)。我已经运行了 10 分钟的查询,但没有找到最短路径。
使用 Gephi,最短路径几乎是瞬时的。
这是我的查询:
g.V(687).repeat(out().simplePath()).until(hasId(1343)).path().limit(1)
最佳答案
使用 simplePath()
您的查询仍会处理比需要更多的路径。例如,如果 688
是 687
的直接邻居,也是 1000
的邻居,在另一条路径上相距 10 跳,为什么如果您早已经看到这个十字路口,您愿意沿着从 1000
到 688
的路径前进吗?
所以,你应该过滤掉你以前见过的任何十字路口(第一次出现的总是最近的):
g.V(687).store('x').
repeat(out().where(without('x')).aggregate('x')).
until(hasId(1343)).limit(1).path()
另外请注意,我交换了 limit(1)
和 path
;那是因为先收集所有路径然后只取第一个路径是浪费资源(CPU 和内存)。
更新:
如果其他人想尝试一下,这里是将数据集加载到 TinkerGraph 的代码:
g = TinkerGraph.open().traversal()
"http://nrvis.com/download/data/road/road-minnesota.zip".toURL().withInputStream {
new java.util.zip.ZipInputStream(it).with {
while (entry = it.getNextEntry()) {
if ("road-minnesota.mtx" == entry.getName()) {
it.eachLine {
if (it ==~ /[0-9]+ [0-9]+/) {
def (a, b) = it.split()*.toInteger()
g.V(a).fold().
coalesce(unfold(), addV().property(id, a)).
addE("road").
to(V(b).fold().coalesce(unfold(), addV().property(id, b))).inV().
addE("road").to(V(a)).iterate()
}
}
break
}
it.closeEntry()
}
}
}
还有查询和小基准:
gremlin> g.V(687).store('x').
......1> repeat(out().where(without('x')).aggregate('x')).
......2> until(hasId(1343)).limit(1).
......3> path().by(id)
==>[687,689,686,677,676,675,673,626,610,606,607,608,735,732,733,730,729,734,737,738,739,742,786,816,840,829,815,825,865,895,872,874,968,983,1009,1044,1140,1142,1148,1219,1255,1329,1337,1339,1348,1343]
gremlin> clock (100) {
......1> g.V(687).store('x').
......2> repeat(out().where(without('x')).aggregate('x')).
......3> until(hasId(1343)).limit(1).
......4> path().iterate()
......5> }
==>12.5362714
TinkerGraph 上的 12.5 毫秒对我来说看起来不错。预计它在 JG 上的运行时间会更长一些,但肯定不会超过 10 分钟。
关于graph - 如何使用 Gremlin 提高最短路径的性能?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50239642/