Рассчитать длину пути между узлами? - PullRequest
Новая
       23

Рассчитать длину пути между узлами?

8 голосов
/ 04 марта 2011

Как я могу получить длину пути между двумя узлами?Например, учитывая организационную иерархию, как я могу определить, насколько далеко отделены родительская и дочерняя организации?Рассмотрим следующие сценарии:

  1. OrgA -hasSubOrganization-> OrgB, OrgC

    Это очень упрощенный случай, когда я хочу получить все непосредственные суборганизации сущности.Следовательно, длина пути равна 1.

  2. OrgA -> OrgB -> OrgC

    или общий случай 

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

Я хочуРекурсивно просмотрите график и найдите каждую организацию, принадлежащую другой организации, через свойство hasSubOrganization.Чтобы получить рекурсивную информацию для всех организаций, я могу использовать пути к свойствам , например, оператор +: 

OrgA hasSubOrganization+ ?subOrg

Это даст мне все суборганизации вплоть до конечных узлов,Но моя конечная цель - построить организационную иерархию, но информация о «количестве узлов / шагов / уровней / скачков, которые есть у суборганизации» теряется.Это означает, что я не могу воссоздать структуру org для визуализации.

Как я могу получить информацию о "количестве узлов" в дополнение к названию суборганизации?

Ответы [ 2 ]

18 голосов
/ 25 сентября 2013

Это основано на том же методе, который используется для вычисления позиции элемента в списке RDF с использованием SPARQL, который описан в: Возможно ли получить позицию элемента в коллекции RDF вSPARQL?

Если у вас есть такие данные: 

@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 указывает длинупути.

1 голос
/ 05 марта 2011

Вы не можете сделать это, используя правильные пути, так как рабочая группа специально решила не делать эту информацию доступной, поскольку это делает реализацию намного более сложной.

Если вы хотите создать иерархию, она, вероятно, будет простостоль же эффективно сделать целую серию запросов SPARQL, где каждый запрос расширяет один лист иерархии и не использует пути свойств вообще, если ваша цель - просто визуализировать иерархию

Могут быть и другие подходы с использованием онтологии JenaAPI - я бы порекомендовал обратиться в их список рассылки jena-users@incubator.apache.org за дополнительной помощью экспертов

...