SPARQL 如何找到通过 RDF 图中多个节点的最短路径

Question

如何使用sparql设置多个节点并求出通过每个节点的最短路径？可以使用Cypher实现这个功能。但是，我不知道如何通过Sparql实现它，以便我可以在Jena中查询路径。

Answer 1

非常感谢您的热心帮助！最后我修改了jena(findShortestPath)的javaapi函数来实现这个功能

首先，为了实现任意两个节点之间的最短路径查询（不考虑关系方向），我修改了jena的javaapi函数（findShortestPath ) 如下。

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;
    }

在这个函数中，另一个函数用于将路径转换为三元组

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;
    }

最后，为了实现通过多个指定节点的最短路径查询，我列举了节点序列的可能组合。然后，计算每个组合每两个节点之间的最短路径之和，select所有总长度最短的组合作为最终结果。

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;
    }

节点的排列由以下函数生成。

    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();
            }
        }
    }

SPARQL 如何找到通过 RDF 图中多个节点的最短路径

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

sparql

jena