计算节点之间的路径长度? [英] Calculate length of path between nodes?

问题描述

如何检索两个节点之间的路径长度?例如，给定组织层次结构，我如何确定上级组织和下级组织之间的距离?请考虑以下情形:

How can I retrieve the length of a path between two nodes? For instance, given an organizational hierarchy, how can I determine how far separated are a parent and an descendant organization? Consider the following scenarios:

1. OrgA -hasSubOrganization-> OrgB, OrgC

这是非常简单的情况，我想获取实体的所有直接子组织.因此，路径长度为1.

This is the very simplistic case where I want to get all the immediate suborganizations of an entity. Hence the path length is 1.

OrgA -> OrgB -> OrgC

或一般情况

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

我想递归地遍历该图，并通过hasSubOrganization属性找到属于另一个组织的每个组织.要获取所有子组织的递归信息，我可以使用属性路径，例如运算符:

I want to recursively traverse down the graph and find each organization belonging to another organization through the hasSubOrganization property. To get all the sub-organizations recursive I can use property paths, e.g., the + operator:

OrgA hasSubOrganization+ ?subOrg

这将把我所有的子组织带到叶节点.但是我的最终目标是建立组织层次结构，但是有关子组织的节点数/步骤数/级别/跳数丢失"的信息却丢失了.这意味着我无法重新创建可视化的组织结构.

This will give me all the suborganizations right down to the leaf nodes. But my ultimate goal is to build the organization hierarchy, but the information about the "Number of nodes/steps/levels/hops away a suborganization is" is lost. This means that I cannot recreate the org structure for a visualization.

除了子组织的名称，我如何捕获节点数"信息?

How can I capture the "number of nodes away" information in addition to the name of the suborganization?

推荐答案

这是基于使用SPARQL计算RDF列表中元素位置的相同技术，该技术描述如下:如果您有这样的数据:

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

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

描述了这样的层次结构:

which describes a hierarchy like this:

然后您可以使用如下查询:

then you can use a query like this:

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的可能方式数表示路径的长度.

The trick here is to recognize that any path from X to Y can be viewed as a (possibly empty) path from X to some intermediate node Z (nonempty means that you can choose X as Z) concatenated with a (non empty) path from Z to Y. The number of possible ways of picking Z indicates the length of the path.

这篇关于计算节点之间的路径长度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！