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

发布于 2024-10-20 09:08:00 字数 701 浏览 6 评论 0原文

如何检索两个节点之间的路径长度？例如，给定一个组织层次结构，我如何确定父组织和子组织之间的距离有多远？考虑以下场景：

OrgA -hasSubOrganization->组织B，组织C
这是一个非常简单的情况，我想获取实体的所有直接子组织。因此路径长度为1。
OrgA ->组织B->组织C
或者一般情况
```
OrgA ->组织B - - - - - - - - 组织Z
```

我想递归地遍历图表并通过 hasSubOrganization 属性找到属于另一个组织的每个组织。为了让所有子组织递归，我可以使用属性路径，例如 + 运算符：

OrgA hasSubOrganization+ ?subOrg

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

除了子组织的名称之外，如何捕获“离开的节点数”信息？

原文

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:

OrgA -hasSubOrganization-> OrgB, OrgC
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
or the general case
```
OrgA -> OrgB - - - - - - - - OrgZ
```

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

慈悲佛祖 2024-10-27 09:08:00

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

如果您有这样的数据：

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

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

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

organization hierarchy

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

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

This is based on the same technique used to compute the position of an element in an RDF list using SPARQL that is described in: Is it possible to get the position of an element in an RDF Collection in SPARQL?

If you have data like this:

@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:

organization hierarchy

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

to get results like these:

$ 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        |
----------------------------

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.

回复收藏 0 原文