Well, that’s why I focused on networkx since it is a pure python implementation.
I suppose there is value in providing a fast implementation of common algorithm like dijkstra in pure prolog, in the same way that networkx provide values in the python ecosystem where they strike a unique balance of convienience by using pure python constructs and usable speed.
The context of these kinds of discussions is broader than just pure absolute speed.
But I have to say that working on a non-backtracking constructs were not my favourite thing, especially with the fact that the retry feature of the debugger won’t work !
Sift up operations is used when adding elements to the heap.
As you can see, my own sift up operation does not need keysort either.
Sift down operation are used when removing an element from the heap.
Here, you need to find the minimum priority child which in a 4-ary heap can be any of the 4 children of the current node, which can be found simply (and slowly ^^) with a keysort.
Note that I also added an unrolled version of sift down operation which does the minimum of comparisons in order to find the min child of a node.
In general though, if you need a non-backtrackable mutable data structure and in particular one that needs quite some updates, writing the data structure in C(++) is the way to go. The nb_setarg/3 trick can efficiently deal with some simply cases and thus allow doing some stuff in Prolog that would otherwise need C extensions. Possibly we can extend that a little by adding more high level array operations to the compound, such as increment/decrement values, swap locations, shift blocks, etc. That might make sense. True, this is all a little ugly. It avoids the need for C code though and all issues related to distributing native code. Using Janus or JPL to use Python or Java are alternatives. I wonder where you get with a heap implemented in Python and used through Janus? Using the current version you can write the whole thing (including the Python code) is a single Prolog file
My gut feeling is that depth-first using iterative deepening is likely to win the shortest path challenge for pure Prolog. Could be wrong of course
