Calculate path length between nodes?

Question

How can I get the path length between two nodes? For example, given the organizational hierarchy, how can I determine how far apart are the parents and the descendant organization? Consider the following scenarios:

• OrgA -hasSubOrganization-> OrgB, OrgC

  This is a very simplified case when I want to get all the immediate suborganizations of an entity. Therefore, the path length is 1.

• OrgA -> OrgB -> OrgC

  or general case

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

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

 OrgA hasSubOrganization+ ?subOrg 

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

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

Answer 1

This is based on the same method used to calculate the position of an element in an RDF list using SPARQL, which is described in: Is it possible to get the position of an element in an RDF collection in SPARQL?

If you have such data:

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

 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 these results:

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

Here we must admit that any path from X to Y can be considered as a (possibly empty) path from X to some intermediate node Z (non-empty means that you can choose X as Z) combined with a (non-empty) path from Z to Y The number of possible ways to select Z indicates the path length.

Answer 2

You cannot do this using the right paths, since the working group specifically chose not to provide this information, as it greatly complicates the implementation.

If you want to generate a hierarchy, it will probably be just as effective to make a whole series of SPARQL queries, where each query extends one sheet of the hierarchy and does not use property paths at all, if your goal is to simply visualize the hierarchy

There may be other approaches using the Jena Ontology API - I would recommend asking for additional help on my mailing list [e-mail]