语句 khop().src().depth()
可以查询一个起点经过 K 步最短路径所到达的终点,即该起点的 KHop 邻居点,可设置 K 值(最短路径深度),支持对起点、所有边、所有邻居点进行过滤,可限制子查询的结果数量。
K 邻是图论中的基本概念,如果点 A 是点 B 的 KHop 邻居点,那么这个 K 值是唯一的。Ultipa 使用 BFS(广度优先)的方式查找最短路径。
(黄、绿、蓝节点分别为红色节点的 1步、2步、3步邻居)
K 邻查询是进行过改良、大幅提高性能后的图近邻查询功能,建议在进行邻居节点查询时,使用 KHop 来替换其他的路径搜索方式。
语法:
- 语句别名:支持,结构为 NODE
- 支持前缀 OPTIONAL,子查询无结果时返回
null
- 全部参数:
参数 | 类型 | 规范 | 描述 | 参数别名结构 |
---|---|---|---|---|
src() |
filter | / | 路径起点的过滤条件;多个点满足条件时会报错 | NODE |
depth() |
range | >0 | 设置路径的深度 depth(N) : 第 N 步 depth(:N) : 第 1~N 步 depth(M:N) : 第 M~N 步 |
不支持 |
node_filter() |
filter | / | 邻居点(非 src )的过滤条件 |
不支持 |
edge_filter() |
filter | / | 所有边的过滤条件 | 不支持 |
direction() |
string | left, right | 规定边的方向 | 不支持 |
limit() |
int | -1 或 >=0 | 子查询返回结果的条数,-1 表示返回所有结果 | 不支持 |
示例图集:(以下示例将在本图基础上运行)
create().edge_property(@default, "weight", int32)
insert().into(@default).nodes([{_id:"A", _uuid:1}, {_id:"B", _uuid:2}, {_id:"C", _uuid:3}, {_id:"D", _uuid:4}, {_id:"E", _uuid:5}, {_id:"F", _uuid:6}])
insert().into(@default).edges([{_uuid:1, _from_uuid:1, _to_uuid:3, weight:1}, {_uuid:2, _from_uuid:5, _to_uuid:2 , weight:1}, {_uuid:3, _from_uuid:1, _to_uuid:5 , weight:4}, {_uuid:4, _from_uuid:4, _to_uuid:3 , weight:2}, {_uuid:5, _from_uuid:5, _to_uuid:4 , weight:3}, {_uuid:6, _from_uuid:2, _to_uuid:1 , weight:2}, {_uuid:7, _from_uuid:6, _to_uuid:1 , weight:4}])
过滤路径深度
示例:查找点 D 的 3-Hop 邻居,携带全部信息
khop().src({_id == "D"}).depth(3) as n
return n{*}
| _id | _uuid |
|-----|-------|
| F | 6 |
示例:查找点 D 的 1~3-Hop 邻居,携带全部信息
khop().src({_id == "D"}).depth(:3) as n
return n{*}
| _id | _uuid |
|-----|-------|
| E | 5 |
| C | 3 |
| A | 1 |
| B | 2 |
| F | 6 |
分析:khop() 命令按照由浅至深的顺序返回邻居节点。本例中点 C、E 为 1-Hop 邻居,点 A、B 为 2-Hop 邻居,点 F 为 3-Hop 邻居。
示例:查找点 D 的 2~3-Hop 邻居,携带全部信息
khop().src({_id == "D"}).depth(2:3) as n
return n{*}
| _id | _uuid |
|-----|-------|
| A | 1 |
| B | 2 |
| F | 6 |
过滤邻居点
示例:查找点 D 的 3-Hop 邻居,要求最短路径不包含点 E,携带全部信息
khop().src({_id == "D"}).depth(3)
.node_filter({_id != "E"}) as n
return n{*}
| _id | _uuid |
|-----|-------|
| B | 2 |
| F | 6 |
分析:不包含点 E 时,相当于将点 E 及其邻边 2、3、5 从图中去掉,此时点 B 为点 D 的 3-Hop 邻居。
过滤边
示例:查找点 D 的 3-Hop 邻居,要求最短路径不包含边 5,携带全部信息
khop().src({_id == "D"}).depth(3)
.edge_filter({_uuid != 5}) as n
return n{*}
| _id | _uuid |
|-----|-------|
| E | 5 |
| B | 2 |
| F | 6 |
分析:不包含边 5 时,相当于将边 5 从图中去掉,此时点 E、B 均变成了 3-Hop 邻居。
过滤边方向
示例:查找点 D 的 1~2-Hop 邻居,要求边的方向为右,携带全部信息
khop().src({_id == "D"}).depth(:2)
.direction(right) as n
return n{*}
| _id | _uuid |
|-----|-------|
| C | 3 |
分析:边方向为右即表示出边,此时点 D 只有一个 1-Hop 邻居 C,由于 C 没有任何出边,因此从 2-Hop 开始点 D 没有任何邻居。
示例:查找点 D 的 1~2-Hop 邻居,要求边的方向为左,携带全部信息
khop().src({_id == "D"}).depth(:2)
.direction(left) as n
return n{*}
| _id | _uuid |
|-----|-------|
| E | 5 |
| A | 1 |
分析:边方向为左即表示入边,此时点 D 有一个 1-Hop 邻居 E,一个 2-Hop 邻居 A。
limit()
示例:查找 3 个点 D 的 1~3-Hop 邻居,携带全部信息
khop().src({_id == "D"}).depth(:3).limit(3) as n
return n{*}
| _id | _uuid |
|-----|-------|
| E | 5 |
| C | 3 |
| A | 1 |
使用 OPTIONAL
示例:查找点 D 的 2-Hop 邻居,要求边的方向为右,携带全部信息;如无结果则返回 null
optional khop().src({_id == "D"}).depth(2)
.direction(right) as n
return n{*}
null
分析:如不使用前缀 OPTIONAL,则无返回。