SPARQL How can I find the shortest path through multiple nodes in a RDF graph

Question

How to use sparql to set multiple nodes and find the shortest path through each node? Cypher can be used achieve this function. However, I do not know how to achieve it by Sparql so that I can query paths in Jena.

Answer 1

Thanks so much for your kindly help! Finally, I modified the java api function of jena (findShortestPath) to achieve this feature.

First, in order to achieve the shortest path query between any two nodes (regardless of the direction of relationships), I modified the java api function of jena (findShortestPath) as follows.

private JSONObject findShortestPath(Model m, Resource start, Resource end) {
        int shortestLength = 20;
        JSONObject pathResult = new JSONObject();
        pathResult.put("length", shortestLength);
        pathResult.put("paths", new JSONArray());

        List<OntTools.Path> bfs = new LinkedList<>();
        ArrayList<ExtendedIterator> nodeStatementIter = new ArrayList<>();
        nodeStatementIter.add(m.listStatements(start, null, (RDFNode)null));
        nodeStatementIter.add(m.listStatements(null, null, start));
        for (var iter : nodeStatementIter) {
            while(iter.hasNext()) {
                Statement statement = (Statement) iter.next();
                if (! statement.getObject().isLiteral())
                bfs.add((new OntTools.Path()).append(statement));
            }
        }
        nodeStatementIter.clear();

        HashSet<Resource> passedNodes = new HashSet<>();
        passedNodes.add(start);

        while(!bfs.isEmpty()) {
            OntTools.Path candidate = bfs.remove(0);
            if (candidate.size() > shortestLength) {
                break;
            }

            Resource subject = candidate.getStatement(candidate.size() - 1).getSubject();
            Resource object = candidate.getStatement(candidate.size() - 1).getObject().isResource() ? candidate.getStatement(candidate.size() - 1).getObject().asResource() : null;
            ArrayList<Resource> resources = new ArrayList<>();
            resources.add(subject);
            if (object != null) {
                resources.add(object);
            }

            if (resources.contains(end)) {
//                solution = candidate;
                shortestLength = candidate.size();
                pathResult.put("length", shortestLength);
                pathResult.getJSONArray("paths").add(pathToTriples(candidate));
            } else {

                for (Resource resource : resources) {
                    if (! passedNodes.contains(resource)) {
                        nodeStatementIter.add(m.listStatements(resource, null, (RDFNode)null));
                        nodeStatementIter.add(m.listStatements(null, null, resource));
                        passedNodes.add(resource);
                        for (var iter : nodeStatementIter) {
                            while(iter.hasNext()) {
//                                Statement link = (Statement)iter.next();
                                Statement statement = (Statement) iter.next();
                                if (!candidate.contains(statement))
                                    bfs.add(candidate.append(statement));
                            }
                        }
                        nodeStatementIter.clear();
                    }
                }
            }
        }

        if (pathResult.getJSONArray("paths").size() == 0) {
            pathResult.put("length", Integer.MAX_VALUE);
        }

        return pathResult;
    }

In this function, another function is used to convert paths to triples

private ArrayList<ArrayList<String>> pathToTriples(OntTools.Path path) {
        ListIterator<Statement> statementListIterator = path.listIterator();
        ArrayList<ArrayList<String>> statements = new ArrayList<>();
        while (statementListIterator.hasNext()) {
            Statement next = statementListIterator.next();
            statements.add(new ArrayList<>(){{
                add(next.getSubject().toString());
                add(next.getPredicate().toString());
                add(next.getObject().toString());
            }});
        }
        return statements;
    }

Finally, in order to achieve the shortest path query through multiple specified nodes, I enumerated the possible combinations of the sequence of the nodes. Then, calculate the sum of the shortest path between every two nodes of each combination, and select all the combinations with the shortest total length as the final result.

public JSONObject findShortestPathBetweenMultipleNodes(Model m, List<Resource> nodes) {
        ArrayList<ArrayList<JSONArray>> nodePairPathMatrix = new ArrayList<>();
        ArrayList<ArrayList<Integer>> nodePairLengthMatrix = new ArrayList<>();

        for (int i = 0; i < nodes.size(); i++) {
            nodePairPathMatrix.add(new ArrayList<>(){{
                for (int j = 0; j < nodes.size(); j++) {
                    add(null);
                }
            }});
            nodePairLengthMatrix.add(new ArrayList<>(){{
                for (int j = 0; j < nodes.size(); j++) {
                    add(Integer.MAX_VALUE);
                }
            }});
        }


        for (int i = 0; i < nodes.size()-1; i++) {
            for (int j = i+1; j < nodes.size(); j++) {
                Resource source = nodes.get(i);
                Resource target = nodes.get(j);
                JSONObject shortestPath = findShortestPath(m, source, target);
                JSONArray paths = shortestPath.getJSONArray("paths");

                nodePairPathMatrix.get(i).set(j, paths);
                nodePairPathMatrix.get(j).set(i, paths);
                nodePairLengthMatrix.get(i).set(j, shortestPath.getInteger("length"));
                nodePairLengthMatrix.get(j).set(i, shortestPath.getInteger("length"));
            }
        }

        ArrayList<ArrayList<Integer>> permutationsOfNodes = permutationByMaxNum(nodes.size());
        Integer minLength = Integer.MAX_VALUE;
        ArrayList<ArrayList<JSONArray>> nodePairPathListWithMinLength = new ArrayList<>();
        for (var permutation : permutationsOfNodes){
            Integer length = 0;
            ArrayList<JSONArray> nodePairPathList = new ArrayList<>();
            for (int permutationItemIndex = 1; permutationItemIndex < permutation.size(); permutationItemIndex++) {
                int end = permutation.get(permutationItemIndex);
                int start = permutation.get(permutationItemIndex-1);
                Integer curNodePairLength = nodePairLengthMatrix.get(start).get(end);
                if (curNodePairLength.equals(Integer.MAX_VALUE) || nodePairLengthMatrix.get(start).get(end).equals(Integer.MAX_VALUE)){
                    length = Integer.MAX_VALUE;
                    break;
                }
                length += nodePairLengthMatrix.get(start).get(end);
                nodePairPathList.add(nodePairPathMatrix.get(start).get(end));
            }
            if (length < minLength) {
                minLength = length;
                nodePairPathListWithMinLength.clear();
                nodePairPathListWithMinLength.add(nodePairPathList);
            } else if (length.equals(minLength)) {
                nodePairPathListWithMinLength.add(nodePairPathList);
            }
        }

        Set<List<String>> tripleResults = new HashSet<>();
        for (var equalTotalLengthNodePairPathListWithMinLength : nodePairPathListWithMinLength) {
            for (var nodePairPathList : equalTotalLengthNodePairPathListWithMinLength) {
                for (int i = 0; i < nodePairPathList.size(); i++) {
                    JSONArray nodePairPathWithEqualLength = nodePairPathList.getJSONArray(i);
                    for (int j = 0; j < nodePairPathWithEqualLength.size(); j++) {
                        JSONArray nodePairPath = nodePairPathWithEqualLength.getJSONArray(j);
                        List<String> triple = nodePairPath.toJavaList(String.class);
                        tripleResults.add(triple);
                    }
                }
            }
        }
        JSONObject result = new JSONObject();
        result.put("triples", tripleResults);
        result.put("length", minLength);

        return result;
    }

The permutations of nodes are generated by the following functions.

    private ArrayList<ArrayList<Integer>> permutationByMaxNum (int maxNum) {
        Stack<Integer> stack = new Stack<>();
        ArrayList<ArrayList<Integer>> results = new ArrayList<>();

        ArrayList<Integer> sourceList = new ArrayList<>();
        for (int i = 0; i < maxNum; i++) {
            sourceList.add(i);
        }
        permutateFunction(results, sourceList, maxNum, 0, stack);
        return results;
    }

    private static void permutateFunction(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> sourceList, int targetNumber, int curNumber, Stack<Integer> stack) {
        if(curNumber == targetNumber) {
//            System.out.println(stack);
            results.add(new ArrayList<>(stack));
            return;
        }

        for (int j : sourceList) {
            if (!stack.contains(j)) {
                stack.add(j);
                permutateFunction(results, sourceList, targetNumber, curNumber + 1, stack);
                stack.pop();
            }
        }
    }