计算节点之间的路径长度？

Question

如何检索两个节点之间的路径长度？例如,给定组织层次结构,如何确定父组织和后代组织分离的距离？请考虑以下方案:

1. OrgA -hasSubOrganization-> OrgB, OrgC

   这是一个非常简单的情况,我希望得到一个实体的所有直接子组织.因此路径长度为1.

2. OrgA -> OrgB -> OrgC

   或一般情况

   OrgA -> OrgB - - - - - - - - OrgZ
   

我想以递归方式遍历图表,并通过该hasSubOrganization属性查找属于另一个组织的每个组织.为了让所有子组织递归,我可以使用属性路径,例如+运算符:

OrgA hasSubOrganization+ ?subOrg

这将为我提供所有子组织,直到叶节点.但我的最终目标是构建组织层次结构,但有关"节点/步骤/级别/跳过子组织的数量"的信息将丢失.这意味着我无法为可视化重新创建组织结构.

除了子组织的名称之外,我如何捕获"节点数"信息？

Answer 1

这基于使用SPARQL计算RDF列表中元素位置的相同技术,如下所述:是否可以在SPARQL中获取RDF集合中元素的位置？

如果你有这样的数据:

@prefix : <http://example.org> .

:orgA :hasSuborganization :orgB, :orgC, :orgD.
:orgB :hasSuborganization :orgE, :orgF.
:orgE :hasSuborganization :orgG.
:orgG :hasSuborganization :orgH.

它描述了这样的层次结构:

然后你可以使用这样的查询:

prefix : <http://example.org> 

select ?super ?sub (count(?mid) as ?distance) { 
  ?super :hasSuborganization* ?mid .
  ?mid :hasSuborganization+ ?sub .
}
group by ?super ?sub 
order by ?super ?sub

得到这样的结果:

$ sparql --query query.rq --data subs.n3
----------------------------
| super | sub   | distance |
============================
| :orgA | :orgB | 1        |
| :orgA | :orgC | 1        |
| :orgA | :orgD | 1        |
| :orgA | :orgE | 2        |
| :orgA | :orgF | 2        |
| :orgA | :orgG | 3        |
| :orgA | :orgH | 4        |
| :orgB | :orgE | 1        |
| :orgB | :orgF | 1        |
| :orgB | :orgG | 2        |
| :orgB | :orgH | 3        |
| :orgE | :orgG | 1        |
| :orgE | :orgH | 2        |
| :orgG | :orgH | 1        |
----------------------------

这里的技巧是要认识到从X到Y的任何路径都可以被视为从X到某个中间节点Z的一条(可能是空的)路径(非空意味着你可以选择X作为Z)与一个(非空)路径连接起来Z到Y.选择Z的可能方式的数量表示路径的长度.