python - SPARQL Floyd-Warshall（或其他 APSP）

Question

我需要一个高效的 SPARQL APSP 实现。我目前有一个由 py​​thon 驱动的 Floyd-Warshall 工作，但它在最内层循环的每次迭代中都使用更新。为了遍历节点，我将所有节点放在一个列表中，删除并单独处理每个节点。哎哟。不幸的是，Floyd-Warshall 似乎需要这种单独的节点处理。有谁知道更好的 APSP，或者更好的方法来做我所做的事情？代码如下。谢谢。

def SPARQL_floyd_warshall(sparqlw, base, edge):
    # Get number of nodes, use for getting "infinity"
    FWQ1 = """
        SELECT (COUNT(?s) AS ?c)
        WHERE
        {
          SELECT DISTINCT ?s
          WHERE
          { ?s """ + edge + """ ?o }
        }
    """
    ret = callGET(sparqlw, FWQ1)
    nodeCt = int(ret['results']['bindings'][0]['c']['value'])
    inf = str(nodeCt * (nodeCt - 1) + 1)

    # Initialize base graph
    FWQ2 = """
        DROP GRAPH <""" + base + """> ;

        INSERT
        {
          GRAPH <""" + base + """>
          { ?s <""" + base + """/dist> ?o }
        }
        WHERE
        {
          ?s0 """ + edge + """ ?o0 .
          ?s1 """ + edge + """ ?o1 .
          BIND ((URI(CONCAT(STR(?s0), "_", STR(?s1)))) AS ?s) .
          BIND ((IF(?s0 != ?s1, """ + inf + """, 0)) AS ?o)
        } ;

        DELETE
        {
          GRAPH <""" + base + """>
          { ?s <""" + base + """/dist> ?o }
        }
        INSERT
        {
          GRAPH <""" + base + """>
          { ?s <""" + base + """/dist> 1 } # Assuming weight is 1
        }
        WHERE
        {
          ?s0 """ + edge + """ ?o0 .
          BIND ((URI(CONCAT(STR(?s0), "_", STR(?o0)))) AS ?s) .
          {
            SELECT ?s ?o
            WHERE
            {
              GRAPH <""" + base + """>
              { ?s <""" + base + """/dist> ?o }
            }
          }
        }
    """
    callPOST(sparqlw, FWQ2)

    MakeList(sparqlw, base + "/nodeNames/1", "?s " + edge + " ?o")
    ret = RemoveFromList(sparqlw, base + "/nodeNames/1", "?s ?p ?o")
    while (len(ret) > 0):
        k = ret['s']
        print k
        MakeList(sparqlw, base + "/nodeNames/2", "?s " + edge + " ?o")
        ret = RemoveFromList(sparqlw, base + "/nodeNames/2", "?s ?p ?o")
        while (len(ret) > 0):
            i = ret['s']
            print '\t' + i
            MakeList(sparqlw, base + "/nodeNames/3", "?s " + edge + " ?o")
            ret = RemoveFromList(sparqlw, base + "/nodeNames/3", "?s ?p ?o")
            while (len(ret) > 0):
                j = ret['s']
                print '\t\t' + j
                FWQ3 = """
                    DELETE
                    {
                      GRAPH <""" + base + """>
                      { <""" + i + "_" + j + """> <""" + base + """/dist> ?dij }
                    }
                    INSERT
                    {
                      GRAPH <""" + base + """>
                      { <""" + i + "_" + j + """> <""" + base + """/dist> ?o }
                    }
                    WHERE
                    {
                      {
                        SELECT *
                        WHERE
                        {
                          GRAPH <""" + base + """>
                          {
                            <""" + i + "_" + k + """> <""" + base + """/dist> ?dik .
                            <""" + i + "_" + j + """> <""" + base + """/dist> ?dij .
                            <""" + k + "_" + j + """> <""" + base + """/dist> ?dkj .
                            BIND ((?dik + ?dkj) AS ?o) .
                            FILTER(?dik + ?dkj < ?dij)
                          }
                        }
                      }
                    };
                """
                callPOST(sparqlw, FWQ3)
                ret = RemoveFromList(sparqlw, base + "/nodeNames/3", "?s ?p ?o")
            ret = RemoveFromList(sparqlw, base + "/nodeNames/2", "?s ?p ?o")
        ret = RemoveFromList(sparqlw, base + "/nodeNames/1", "?s ?p ?o")

def MakeList(sparqlw, listName, criteria, graph = None):
    MLQ = """
        DROP GRAPH <""" + listName + """> ;

        INSERT
        {
          GRAPH <""" + listName + """>
          { """ + criteria + """ }
        }
        WHERE
        """ + ("{ GRAPH " + graph if graph else "") + """
          { """ + criteria + """ }
        """ + ("}" if graph else "")
    callPOST(sparqlw, MLQ)

def RemoveFromList(sparqlw, listName, criteria):
    RFLQ1 = """
        SELECT *
        WHERE
        {
          GRAPH <""" + listName + """>
          { """ + criteria + """ }
        }
        LIMIT 1
    """
    ret = callGET(sparqlw, RFLQ1)['results']['bindings']

    retDict = dict()

    if (len(ret) > 0):
        qVars = ret[0].keys()
        data = criteria
        for qVar in qVars:
            retDict[str(qVar)] = str(ret[0][qVar]['value'])
            if (ret[0][qVar]['type'] == "uri"):
                leading = "<"
                closing = ">"
            else:
                leading = closing = '"'
            data = data.replace('?' + str(qVar), leading + str(ret[0][qVar]['value']) + closing)

        RFLQ2 = """
            DELETE DATA
            {
              GRAPH <""" + listName + """>
              { """ + data + """ }
            }
        """
        callPOST(sparqlw, RFLQ2)

    return retDict