Graph Algorithms

MarkLogic 12 introduces support for functions to analyze graph-structured data.

Shortest Path

Many real-world problems can be represented as shortest path problems. Ones that quickly come to mind are navigational systems and network routing/circuit design.

In addition, recommendation systems and natural language processing applications can take advantage of shortest path operations in a knowledge graph by allowing discovery of relationships between people, words, or concepts. GraphRAG (Retrieval Augmented Generation) is a framework that has proven to give Large Language Models (LLM) a boost in quality of responses. Shortest path queries can help discover relevant facts in your knowledge graph and piece together information that may have been missed before.

Triples can be used to represent and resolve shortest path problems. Each subject and object can be considered as nodes separated by predicate edges. Crossing these edges comes at a cost, and finding the path with the least hops can be solved by the new shortestPath function.

xdmp:shortestPath is a magic property or property function (See: W3C’s SPARQL/Extensions/Computed Properties) that can help solve this problem. This magic property has the following named bindings:

To better understand this concept, let’s start with a simple set of data:

'use strict';

declareUpdate();

const sem = require("/MarkLogic/semantics.xqy");

let ttl = `@prefix p: <http://example.org/kennedy/> .
@prefix foaf: <http://xmlns.com/foaf/0.1/> .
p:john foaf:knows p:bob .
p:john foaf:knows p:alice .
p:john foaf:knows p:zak .
p:bob foaf:knows p:alice .
p:bob foaf:knows p:maia .
p:alice foaf:knows p:zak .
p:zak foaf:knows p:drew .
p:drew foaf:knows p:maia .`

let triples = sem.rdfParse(ttl, ['turtle', 'repair'])
sem.rdfInsert(triples)

Which could then be represented as:

The shortest path from john to maia would be the least number of edges to cross. That would be through bob. In SPARQL, this could be expressed as:

PREFIX xdmp: <http://marklogic.com/xdmp#>
PREFIX p: <http://example.org/kennedy/>
SELECT * 
where {
  (
    [xdmp:start ?s ]
    [xdmp:end ?o]
  ) xdmp:shortestPath (
    [xdmp:path ?path]
    [xdmp:length ?length]
  )
  FILTER (?s = p:john && ?o = p:maia )
}

which would then return

[{
  "s": "<http://example.org/kennedy/john>",
  "o": "<http://example.org/kennedy/maia>",
  "path": [{
      "s": "http://example.org/kennedy/john",
      "_:ANON9088488689022242345": "http://xmlns.com/foaf/0.1/knows",
      "o": "http://example.org/kennedy/bob"
    }, {
      "s": "http://example.org/kennedy/bob",
      "_:ANON9088488689022242345": "http://xmlns.com/foaf/0.1/knows",
      "o": "http://example.org/kennedy/maia"
    }
  ],
  "length": "\"2\"^^xs:unsignedLong"
}]

Note that the applying the FILTER to ?o is optional. This enables us to see all the shortest paths from a subject of a triple. The FILTER on ?s is optional as well. If left out, this allows discovery of all shortest paths that lead to an end object of a triple. If the FILTERs are omitted, it is ideal to apply a FILTER on ?length to return only the most relevant shortest paths.