sparql - path between two resources

Question

Is it possible to count the number of the edges that connect two instance with a SPARQL query? I want to find a path.

Answer 1

You count the number of edges in a unique path using SPARQL's property paths and aggregate functions. For instance, with data like this, which contains two paths that we care about (a to c with two edges, and d to g with three edges):

@prefix : <https://stackoverflow.com/questions/19587520/sparql-path-between-two-instance/> .

:a :p :b .  # a to c is a path of length 2
:b :p :c .  

:d :p :e .  # d to g is a path of length 3
:e :p :f .
:f :p :g . 

you can use a query like the following one. Notice that I've used the specific property :p, rather than a variable. This is necessary, because 9.1 Property Path Syntax from the SPARQL 1.1 specification doesn't allow variables in property paths.

prefix : <https://stackoverflow.com/questions/19587520/sparql-path-between-two-instance/>

select ?start ?end (count(?mid) as ?length)
where {
  values (?start ?end) { (:a :c) (:d :g) }
  ?start :p+ ?mid .
  ?mid :p* ?end .
}
group by ?start ?end 

and get results like this:

$ sparql --query query.rq --data data.n3
------------------------
| start | end | length |
========================
| :d    | :g  | 3      |
| :a    | :c  | 2      |
------------------------

A fuller description of what's happening here can be found in:

• Calculate length of path between nodes? (which is actually look at paths in a tree)
• this answer to Finding all steps in property path (Note that the accepted answer says you can't do this, but the linked answer shows that you actually can); and
• the accepted answer to Is it possible to get the position of an element in an RDF Collection in SPARQL?.

The basic idea, though, is that if you have a path from ?start to ?end, then you've also got, for a bunch of different values of ?mid, a path from ?start to ?mid and a path from ?mid to ?end. The number of different values that you can pick for ?mid (if you allow one of the endpoints, and disallow the other) is exactly the length of the path.