在三维网格模型上,寻找任意两个顶点间的最短路径是几何模型计算的基本问题也是目前网格模型有意义的分割、机器视觉模式识别等热点研究工作的基础问题。就如乘汽车旅行的人总希望找出到目的地的尽可能的短的行程一样，在实际业务场景中我们通常希望能快速找到两个点之间的关联关系。在图数据结构中，任意两点之间的最短路径的长度称为这两点之间的距离，距离越近代表这两点之间关联关系越大。例如在一张图中对于和存在违法犯罪的人员关系最紧密的人员可评为高风险人员。

在gStore 0.9版本中，gStore 加入了与数据图中结点间的路径相关的一系列高级功能，其中包括最短路径查询（企业版支持）。为了更好地演示环路查询的功能，使用以下的社交关系数据作为示例数据：

<Alice> <关注> <Bob> .

<Alice> <喜欢> <Bob> .

<Alice> <不喜欢> <Eve> .

<Bob> <关注> <Alice> .

<Bob> <喜欢> <Eve> .

<Carol> <关注> <Bob> .

<Carol> <喜欢> <Bob> .

<Carol> <不喜欢> <Francis> .

<Dave> <关注> <Alice> .

<Dave> <关注> <Eve> .

<Dave> <不喜欢> <Francis> .

<Eve> <喜欢> <Carol> .

<Francis> <喜欢> <Carol> .

<Francis> <不喜欢> <Dave> .

<Francis> <不喜欢> <Eve> .

查询从结点u到结点v的最短路径，gStore给出了两个函数

shortestPath(u, v, directed, pred_set)

shortestPathLen(u, v, directed, pred_set)

用于 SELECT 语句中，与聚合函数使用语法相同。

参数含义：

u , v ：变量或结点 IRI

directed ：布尔值，为真表示有向，为假表示无向（图中所有边视为双向）

pred_set：构成最短路径的边上允许出现的谓词集合。若设置为空 {} ，则表示允许出现数据中的所有谓词

返回值

shortestPath ：以 JSON 形式返回从结点 u 到 v 的一条最短路径（若可达）。若 u 或 v 为变量，对变量的每组有效值返回一条最短路径。

shortestPathLen：返回从结点 u 到 v 的最短路径长度（若可达）。若 u 或 v 为变量，对变量的每组有效值返回一个最短路径长度数值。

下面的查询返回从 Francis 到一个 Bob 喜欢、关注或不喜欢，且没有被 Francis 不喜欢的人（示例数据中即为 Alice）的最短路径，边上的关系可以是喜欢或关注：

SELECT (shortestPath(<Francis>, ?x, true, {<喜欢>, <关注>}) AS ?y)

WHERE

{

<Bob> ?pred ?x .

MINUS { <Francis> <不喜欢> ?x . }

}

下图标红的部分即为这条最短路径：

结果如下：（为方便阅读，省略了字符串最外层的双引号和内部双引号的转义）

{

"paths":[{

"src":"<Francis>",

"dst":"<Alice>",

"edges":

[{"fromNode":4,"toNode":3,"predIRI":"<喜欢>"},{"fromNode":3,"toNode":1,"predIRI":"<喜欢>"},{"fromNode":1,"toNode":0,"predIRI":"<关注>"}],

"nodes":

[{"nodeIndex":0,"nodeIRI":"<Alice>"},{"nodeIndex":1,"nodeIRI":"<Bob>"},{"nodeIndex":3,"nodeIRI":"<Carol>"},{"nodeIndex":4,"nodeIRI":"<Francis>"}]

}]

}

如果希望只输出最短路径长度，则使用下面的查询：

SELECT (shortestPathLen(<Francis>, ?x, true, {<喜欢>, <关注>}) AS ?y)

WHERE

{

<Bob> ?pred ?x .

MINUS { <Francis> <不喜欢> ?x . }

}

结果如下：（为方便阅读，省略了字符串最外层的双引号和内部双引号的转义）

{"paths":[{"src":"<Francis>","dst":"<Alice>","length":3}]}

ITPub博客

gStore高级功能之最短路径查询

最新文章