Shortest Paths algorithm

[lucaspg96]

Implement the Minimal Paths (MP) algorithm over a graph

[lucaspg96]

Divergence between MinimalPaths result and Dijkstra. To identify the error, just run:

def main(args: Array[String]): Unit = {
    val graph = NTripleParser.parse("src/main/resources/dbpedia.nt")
    
    val fromNode = graph.getNodeByURI("person@en")
    val toNode = graph.getNodeByURI("Tony Award@en")
    
    val nodes = List(fromNode, toNode)

    graph.getLinksAsStream
      .foreach(link => link match {
        case Relation(_, l, t) =>
          if ((l.uri.endsWith("#type") && (t.uri.endsWith("#Class") || t.uri.endsWith("Property"))) ||
            (l.uri.endsWith("#range") && t.uri.contains("XMLSchema#")))
            link.setWeight(100)
          else if (l.uri.contains("rdf-schema#subClassOf"))
            link.setWeight(1)
          else if (l.uri.contains("rdf-schema#sub"))
            link.setWeight(10)

        case Attribute(_, l, _) =>
          if(l.uri.endsWith("#label"))
            link.setWeight(10)

        case _ =>
      })

    MinimalPathsClosure(graph)(nodes)

    val path = new DijkstraStrategy(graph).run(nodes.head.getId, nodes(1).getId)

    print("Dijkstra cost: "+path.getDistance(nodes(1).getId)+"| Path: ")
    path.printPathTo(nodes(1).getId)

  }