Search code examples
graphsparqlrdfowltriplestore

Show all paths of a tree in SPARQL

Consider a tree:

prefix : <http://example.org/random#>

    :A a :Black .
    :B a :Black .
    :C a :Red .
    :D a :Black .
    :E a :Red .
    :F a :Black .
    :G a :Black .
    :H a :Red .
    :A :hasChild :B .
    :A :hasChild :C .
    :B :hasChild :D .
    :C :hasChild :E .
    :C :hasChild :F .
    :F :hasChild :G .
    :F :hasChild :H .

Every bottom node represents one path.

How can I count the number of "class changes" when following the path from the root node :A to every bottom node?

A class change occurs if parent and child nodes have different classes red / black. The results should look like this:

?bottom  ?num
:D       0
:E       1
:G       2
:H       3

RDF Tree

I tried different approaches like:

prefix : <http://example.org/random>
SELECT ?bottom (COUNT(distinct IF(?type1 != ?type2,1,0)) AS ?num)
WHERE {

       :A :hasChild* ?child, ?mid, ?bottom .

        ?child a ?type1 .
        ?mid a ?type2 .


       FILTER NOT EXISTS {?bottom :hasChild ?x}


} group by ?bottom

That gives me:

bottom  num

E       "2"
D       "2"
G       "2"
H       "2"
Solution 
  • prefix : <http://example.org/random#> 

select (?end as ?bottom) (sum(?change) as ?num) 

where { 

?begin :hasChild* ?midI . 
FILTER NOT EXISTS { [] :hasChild ?begin } 
?midI :hasChild ?midJ . 
?midI a ?iType . 
?midJ a ?jType . 
BIND(IF(?iType != ?jType, 1, 0) as ?change) 
?midJ :hasChild* ?end . 
FILTER NOT EXISTS { ?end :hasChild [] } 

} group by ?begin ?end order by ?num

    answered by @Uninformeduser