Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

使用HugeGraph怎么求解最短路径? #29

Closed
huxiaoqing0704 opened this issue Aug 23, 2018 · 10 comments
Labels

Comments

@huxiaoqing0704
Copy link

@huxiaoqing0704 huxiaoqing0704 commented Aug 23, 2018

使用HugeGraph怎么求解最短路径,是通过gremlin的语法实现吗,还是有直接的java api.

@javeme javeme added the question label Aug 23, 2018
@javeme

This comment has been minimized.

Copy link
Contributor

@javeme javeme commented Aug 23, 2018

hugegraph提供了最短路径的Restful API shortestpath,其URL地址形如:http://localhost:8080/graphs/hugegraph/traversers/shortestpath
详见traverser文档3.1.1 Shortest Path:
https://hugegraph.github.io/hugegraph-doc/clients/restful-api/traverser.html

当然hugegraph也支持通过gremlin来实现最短路径:

g.V("src_v_id")
 .repeat(out().simplePath()).until(hasId("target_v_id")
 .or().loops().is(gte(4))).hasId("target_v_id")
 .path().limit(1)

其中src_v_idtarget_v_id替换为查询顶点的ID,gte(4)表示做大深度为4,可以根据数据量大小进行调整。

@huxiaoqing0704

This comment has been minimized.

Copy link
Author

@huxiaoqing0704 huxiaoqing0704 commented Aug 24, 2018

@javeme 非常感谢您的回答,我这边还有以下几个疑问:

1、您gremlin的那个实现,如果做最大深度为4以内的,方向是both的,是不是应该下面的写法?我看您那个中间是用的or(),是不是应该是and()?再就是您那个是gte(4),是不是应该是lte(4)?

g.V("src_v_id")
 .repeat(both().simplePath()).until(hasId("target_v_id")
 .and().loops().is(lte(4))).hasId("target_v_id")
 .path().limit(1)

2、使用hugegraph的Restful API查询最短路径的性能跟grelin的性能对比一样吗?哪个更好一些?这两种不同的调用方式,底层最短路径的算法实现是一样的吗?

@javeme

This comment has been minimized.

Copy link
Contributor

@javeme javeme commented Aug 24, 2018

@huxiaoqing0704

如果做最大深度为4以内的,方向是both的,是不是应该下面的写法?

是的,使用both()替换out()即可。

我看您那个中间是用的or(),是不是应该是and()?再就是您那个是gte(4),是不是应该是lte(4)?

方法until()的含义是直到条件满足则停止,上述给出gremlin语句的意思是:只要找到目标顶点或者到达深度为4则停止。所以应该使用orgte。更多gremlin说明可参考Tinkerpop官网

使用hugegraph的Restful API查询最短路径的性能跟gremlin的性能对比一样吗?哪个更好一些?

建议使用Restful API的shortestpath,其性能好于gremlin方式的实现,当然gremlin方式则更加通用。两者的底层实现原理是一样的。

@huxiaoqing0704

This comment has been minimized.

Copy link
Author

@huxiaoqing0704 huxiaoqing0704 commented Aug 25, 2018

@javeme 非常感谢您的答复。我还有几个问题需要咨询一下:
1、我现在使用gremlin做最短路径查询,使用withRemote方式连接gremlin-server,发现数据量100w+的时候查找最短路径就很慢了,想请教一下,影响最短路径的查询性能有哪些因素?gremlin-server的内存设置大小有关系吗?或者还有别的哪些因素?
2、如果使用gremlin的方式查找最短路径,HugeGraph和Titan DB、Janusgraph这块儿性能是不是一样的?
3、查找最短路径的底层实现原理能说明一下吗?这块儿数据是加载到内存中计算吗?

@huxiaoqing0704

This comment has been minimized.

Copy link
Author

@huxiaoqing0704 huxiaoqing0704 commented Aug 27, 2018

@javeme
之前的这个语句是拿一条最短路径,如果拿全部的最短路径怎么实现?
g.V("src_v_id") .repeat(both().simplePath()).until(hasId("target_v_id") .and().loops().is(lte(4))).hasId("target_v_id") .path().limit(1)

@javeme

This comment has been minimized.

Copy link
Contributor

@javeme javeme commented Oct 25, 2018

@huxiaoqing0704 多条最短路径可以增加limit的数,-1为不限制。

g.V("src_v_id")
 .repeat(both().simplePath()).until(hasId("target_v_id")
 .and().loops().is(lte(4))).hasId("target_v_id")
 .path().limit(10) // 10条最短路径
@javeme javeme added the gremlin label Oct 30, 2018
@ZhiqinYang

This comment has been minimized.

Copy link

@ZhiqinYang ZhiqinYang commented Apr 12, 2019

@huxiaoqing0704 多条最短路径可以增加limit的数,-1为不限制。

g.V("src_v_id")
 .repeat(both().simplePath()).until(hasId("target_v_id")
 .and().loops().is(lte(4))).hasId("target_v_id")
 .path().limit(10) // 10条最短路径

这个不是全部最短路把, 这个查询的因该是 4度以内的全部可达路径吧

@javeme

This comment has been minimized.

Copy link
Contributor

@javeme javeme commented Apr 12, 2019

多条最短路径可以增加limit的数,-1为不限制。

g.V("src_v_id")
 .repeat(both().simplePath()).until(hasId("target_v_id")
 .and().loops().is(lte(4))).hasId("target_v_id")
 .path().limit(10) // 10条最短路径

这个不是全部最短路把, 这个查询的因该是 4度以内的全部可达路径吧

@huxiaoqing0704 是最短路径的,可以使用小图进行验证看看效果。

@zhoney

This comment has been minimized.

Copy link
Contributor

@zhoney zhoney commented Jun 28, 2019

Close this issue now due to having not been updated in a long time. Feel free to reopen it if needed.

@zhoney zhoney closed this Jun 28, 2019
@1315861791

This comment has been minimized.

Copy link

@1315861791 1315861791 commented Sep 5, 2019

@javeme @ZhiqinYang 向高手请教一下:如何在一个语句中实现1个点到多个目标点的最短路径?(一个起点,多个终点,到每个终点的最短路径)如何在这个上面扩展啦?
g.V("src_v_id")
.repeat(both().simplePath()).until(hasId("target_v_id")
.and().loops().is(lte(4))).hasId("target_v_id")
.path().limit(1)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants
You can’t perform that action at this time.