Thank you for your answers!
First of all, my apologies for not clearly explaining my case.
Indeed I would like to use GeoSPARQL to keep the positions of millions
of nodes so that the visualisations are always reproducible. Thus there
is no relation between GeoSPARQL and the shortest path search.
- my data doesn't represent geometric map
- distances between the nodes and edges' weight are not correlated
- an edge's weight represents a confidence score (an annotation on the
RDF triple itself)
According to your replies, I assume that the shortest path should first
be computed by expanding and customizing Jena's Java method or JGraphT.
Then I could display the path found on the graph where the node
coordinates are relatively fixed thanks to GeoSPARQL.
Below I have put an example of an RDF data where score (weight) and
node's geometry information co-exist. For the scores, I have put in two
versions: RDF-star and standard RDF (using RDF Statement).
Regards,
Min
---------- Sample case ----------
Two possible paths from A to D with weight (score):
1. A -(1)-> B -(2)-> C -(3)-> D : 4 nodes, total weight = 6
2. A -(2)-> E -(1)-> D : 3 nodes, total weight = 3
I would like to find a path with maximum of weight, i.e. the first
path, even if the total number of noeds is higher.
---------- RDF data ----------
@prefix : <<http://example.com/>> .
@prefix geo: <<http://www.opengis.net/ont/geosparql#>> .
@prefix rdf: <<http://www.w3.org/1999/02/22-rdf-syntax-ns#>> .
# Node position using GeoSPARQL
:A geo:hasGeometry :pointA .
:B geo:hasGeometry :pointB .
:C geo:hasGeometry :pointC .
:D geo:hasGeometry :pointD .
:E geo:hasGeometry :pointE .
# Score annotation
# using RDF*
<< :A :active :B >> :score 1 .
<< :B :active :C >> :score 2 .
<< :C :active :D >> :score 3 .
<< :A :active :E >> :score 2 .
<< :E :active :D >> :score 1.
# using RDF statement (reification)
:AtoB rdf:type rdf:Statement ;
rdf:subject :A ;
rdf:predicate :active ;
rdf:object :B ;
:score 1 .
:BtoC rdf:type rdf:Statement ;
rdf:subject :B ;
rdf:predicate :active ;
rdf:object :C ;
:score 2 .
# ...etc
Le sam., mars 25 2023 at 09:12:44 +0100, Lorenz Buehmann
<buehm...@informatik.uni-leipzig.de> a écrit :
Hi, comments inline
On 24.03.23 18:30, Yang-Min KIM wrote:
Dear Jena community,
I would like to use GeoSPARQL, but before I proceed I need your
valuable advice.
What I want to do:
- Using GeoSPARQL, nodes have their own position (or zone).
In RDF and thus in Jena those are still plain RDF nodes in the RDF
graph, doesn't matter if those nodes have geospatial information
assigned or not
- Graph is weighted: edge has a value
Are you talking about edges aka triples in the RDF graph? The weight
is an RDF triple then? Or an annotation on the RDF triple itself? Or
an RDF Star triple?
- Find the shortest path between nodes in a weighted graph
How? Writing your own custom algorithm traversing the RDF graph?
Neither SPARQL as the dedicated query language for RDF not RDF itself
have algorithms or concepts of paths.
On the other hand, some triple stores nowadays provide extension to
traverse the graph more efficiently, but there is no standardized
method. For example, even Jena has some Java code do compute the/some
shortest path:
<https://jena.apache.org/documentation/javadoc/jena/org.apache.jena.core/org/apache/jena/ontology/OntTools.html#findShortestPath(org.apache.jena.rdf.model.Model,org.apache.jena.rdf.model.Resource,org.apache.jena.rdf.model.RDFNode,java.util.function.Predicate>)
But this implementation is no weighted, so you would have to extend
the code or just write your own custom Java code based on Jena's
Graph::find method for example. Even more simple, use JGraphT and
just write a wrapper for Jena - we did the same, so we could apply
JGraphT algorithms on a Jena Graph object. Indeed, efficiency can't
be the same as for other Graph databases with optimized index
structures.
My question is, what is the relation to GeoSPARQL in your current
problem? Does it matter for your weighted graph? Can you give an
example fore the RDF graph?
For instance, there is Dijkstra's algorithm allowing to find the
shortest paths considering weighted edges.
<<https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm>>
Here are my questions as a beginner:
1. What is the best way to integrate a weighted graph in Jena?
2. Maybe RDF* (RDF-star)? Is it compatible with GeoSPARQL?
3. How can we find a shortest path considering edge values?
Thank you for your time and have a great weekend.
Min
