Retrieving all paths in an OWL class hierarchy wit

I have an RDF graph of with a hierarchy three levels deep. I want to retrieve all the paths starting from the root of the class hierarchy (i.e., owl:Thing) down to classes in the third level without using a reasoner. For instance, I would like the path C₁ → C₂ → C₃ is a path, where each C_i is a class at the i^th level of the hierarchy.

I need to retrieve all the paths in the RDF graph using the breadth first search algorithm with no considerations to the object properties in the graph.

Given some data like this (where length of the class name is an indication of the depth of the class in the hierarchy):

@prefix : <http://example.org/> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .

:a a rdfs:Class .

:aa rdfs:subClassOf :a .
:ab rdfs:subClassOf :a .
:ac rdfs:subClassOf :a .

:aaa rdfs:subClassOf :aa .
:aab rdfs:subClassOf :aa .
:aac rdfs:subClassOf :aa .

:aaba rdfs:subClassOf :aab .
:aabb rdfs:subClassOf :aab .

:aba rdfs:subClassOf :ab .
:abb rdfs:subClassOf :ab .

You can use a SPARQL query to select the paths that you're looking for.

Using a SPARQL query

You can write a SPARQL query like this to get the following results:

prefix : <http://example.org/>
prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>

select ?c1 ?c2 ?c3 where { 
  values ?c1 { :a }
  ?c1 ^rdfs:subClassOf ?c2 .
  OPTIONAL {
    ?c2 ^rdfs:subClassOf ?c3 .
  }
}
order by ?c3 ?c2 ?c1

-------------------
| c1 | c2  | c3   |
===================
| :a | :ac |      |
| :a | :aa | :aaa |
| :a | :aa | :aab |
| :a | :aa | :aac |
| :a | :ab | :aba |
| :a | :ab | :abb |
-------------------

Using the camera ontology

This approach works with the camera ontology that has been mentioned in the comments, though the query requires a little extension to handle deeper class paths. Thus:

PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX owl: <http://www.w3.org/2002/07/owl#>
PREFIX : <http://www.xfront.com/owl/ontologies/camera/#>

select * where { 
  values ?c1 { owl:Thing } 
  ?c1 ^rdfs:subClassOf ?c2 .
  OPTIONAL { 
    ?c2 ^rdfs:subClassOf ?c3 .
    OPTIONAL { 
      ?c3 ^rdfs:subClassOf ?c4 .
    }
  }
}
order by ?c4 ?c3 ?c2

-----------------------------------------------------------
| c1        | c2                | c3      | c4            |
===========================================================
| owl:Thing | :Money            |         |               |
| owl:Thing | :Range            |         |               |
| owl:Thing | :Window           |         |               |
| owl:Thing | :PurchaseableItem | :Body   |               |
| owl:Thing | :PurchaseableItem | :Lens   |               |
| owl:Thing | :PurchaseableItem | :Camera | :Digital      |
| owl:Thing | :PurchaseableItem | :Camera | :Large-Format |
-----------------------------------------------------------

Using the Jena API

While the above SPARQL query produces the paths in the order that would expected from a breadth first traversal, there is actually no guarantee on how ARQ generates the results. We can also implement a Breadth First Search directly, using the Jena Model API to retrieve subclasses. Here's a straightforward implementation:

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.hp.hpl.jena.rdf.model.Model;
import com.hp.hpl.jena.rdf.model.ModelFactory;
import com.hp.hpl.jena.rdf.model.Resource;
import com.hp.hpl.jena.rdf.model.StmtIterator;
import com.hp.hpl.jena.vocabulary.OWL;
import com.hp.hpl.jena.vocabulary.RDFS;

public class BFSInRDFWithJena {

    public static List<List<Resource>> BFS( final Model model, final Queue<List<Resource>> queue, final int depth ) {
        final List<List<Resource>> results = new ArrayList<>();
        while ( !queue.isEmpty() ) {
            final List<Resource> path = queue.poll();
            results.add( path );
            if ( path.size() < depth ) {
                final Resource last = path.get( path.size() - 1 );
                final StmtIterator stmt = model.listStatements( null, RDFS.subClassOf, last );
                while ( stmt.hasNext() ) {
                    final List<Resource> extPath = new ArrayList<>( path );
                    extPath.add( stmt.next().getSubject().asResource() );
                    queue.offer( extPath );
                }
            }
        }
        return results;
    }

    public static void main( final String[] args ) throws IOException {
        final Model model = ModelFactory.createDefaultModel();
        try ( final InputStream in = BFSInRDFWithJena.class.getClassLoader().getResourceAsStream( "camera.owl" ) ) {
            model.read( in, null );
        }

        // setup the initial queue
        final Queue<List<Resource>> queue = new LinkedList<>();
        final List<Resource> thingPath = new ArrayList<>();
        thingPath.add( OWL.Thing );
        queue.offer( thingPath );

        // Get the paths, and display them
        final List<List<Resource>> paths = BFS( model, queue, 4 );
        for ( List<Resource> path : paths ) {
            System.out.println( path );
        }
    }
}

[http://www.w3.org/2002/07/owl#Thing]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#Window]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#Range]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#Money]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem, http://www.xfront.com/owl/ontologies/camera/#Camera]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem, http://www.xfront.com/owl/ontologies/camera/#Lens]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem, http://www.xfront.com/owl/ontologies/camera/#Body]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem, http://www.xfront.com/owl/ontologies/camera/#Camera, http://www.xfront.com/owl/ontologies/camera/#Digital]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem, http://www.xfront.com/owl/ontologies/camera/#Camera, http://www.xfront.com/owl/ontologies/camera/#Large-Format]