Floyd-Warshall algorithm in Prolog

General
1

Floyd-Warshall is a well known and simple algorithm for finding all the shortest paths in a graph through dynamic programming. Here is the pseudo-code:

let dist be a |V| × |V| array, initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

I’d like an implementation in a Prolog sympathetic way: immutable, perhaps using tabling, whilst hopefully conserving the conciseness of the original.

Does anyone have any such code, or might you fancy a stab at it?

2

Hello,
Here is my version using a list of list for a matrix with fully ground elements, meaning that you have to copy the matrix every time you do an update.
I think this is kind of the worst implementation anyone can think of, therefore kind of a good baseline ? :slight_smile:

It is immutable as requested but the conciseness is not quite as good as the original because of for loops, especially nested ones…

floyd_warshall(V, Graph, M4) :-
   length(M1, V),
   maplist(length_(V), M1),
   maplist(maplist(=(inf)), M1),
   foldl(edges, Graph, M1, M2),
   numlist(1, V, Vertices),
   foldl(vertices, Vertices, M2, M3),
   transitive(Vertices, M3, M4).

edges((U1-V1)-W, M1, M2) :-
   replace(U1, V1, M1, _, W, M2).

vertices(I, M1, M2) :-
   replace(I, I, M1, _, 0, M2).

transitive(Vertices, M1, M2) :-
   foldl(transitive(Vertices), Vertices, M1, M2).
transitive(Vertices, K, M1, M2) :-
   foldl(transitive(Vertices, K), Vertices, M1, M2).
transitive(Vertices, K, I, M1, M2) :-
   foldl(transitive_(K, I), Vertices, M1, M2).

transitive_(K, I, J, M1, M2) :-
   replace(I, J, M1, IJ1, IJ2, M2),
   nth2d(I, K, M1, IK),
   nth2d(K, J, M1, KJ),
   IKJ is IK + KJ,
   (  IJ1 > IKJ
   -> IJ2 = IKJ
   ;  IJ2 = IJ1
   ).

Here is a example query, (the graph comes from wikipedia):

?- graph(G), gtrace, floyd_warshall(4, G, M).
G = [2-1-4, 2-3-3, 1-3- -2, 3-4-2, 4-2- -1],
M = [[0, -1, -2, 0], [4, 0, 2, 4], [5, 1, 0, 2], [3, -1, 1, 0]].
prolog code with graph fact and helper predicates 
graph([
   (2-1)-4,
   (2-3)-3,
   (1-3)-(-2),
   (3-4)-2,
   (4-2)-(-1)
]).

length_(Len, List) :-
   length(List, Len).

nth2d(I, J, M, V) :-
   nth1(I, M, Row),
   nth1(J, Row, V).

replace(I, L1, Old, New, L3) :-
   nth1(I, L1, Old, L2),
   nth1(I, L3, New, L2).

replace(I1, I2, M1, Old, New, M2) :-
   replace(I1, M1, Row1, Row2, M2),
   replace(I2, Row1, Old, New, Row2).

PS: Seriously, why do you have to do this to me, you can’t expect me not to spend my holiday not optimizing this like I did with dijkstra :sob:

1 Like
3

By the way:

Does using clpfd variables for tracking distances count as immutable ?

I don’t think tabling will help here with the three nested for loops.

4

The Craft of Prolog by Richard O’Keefe, page 171 (except it says “Warshall’s algorithm” rather than “Floyd-Warshall algorithm”.
And there’s a discussion of the problem starting at page 167.

2 Likes
6

Thanks @kwon-young, I suspect the algorithm may need some re-thinking to be Prolog friendly, if it is at all possible. Yours is a functional version of the imperative code, and roughly O(V^5) I think.

I like the DSL @j4n_bur53 but the actual code looks imperative, mutable and non-backtrackable.

@peter.ludemann its the transitive closure algorithm. It is given on page 5 here. I think that the main difference is the min condition from above is replaced with a logical OR. O’Keefe accumulates results using a ordered set since the values are binary, otherwise it is similar to @kwon-young approach. I don’t think this works when distance is required because we cannot make the value of a member in a set implicit (e.g. if its in the set then true); there needs to be some kind of updating structure, or a reenvisioning of how the algorithm calculates.

7

To minimise the pain of Aoc 2024 Day 16 in Prolog, I suspect I’ll end up just biting the bullet and using nb_setarg/3. I’m really loathed to implement Djisktra yet again.

8

So I’m thinking of keeping distance state a bit like this. Say I have N vertices:

NN is N**2,
length(Dist0, NN),
maplist(=(10**5), Dist0),
Dist =.. [dist|Dist0].

I’ll pass Dist around. It can then be accessed using arg/3 or changed using setarg/3 or nb_setarg/3 (which I expect is faster). Pretty horrible, but needs must.

9

Note that 10**5 is not evaluated. I’d consider using a variable as initial value.

Yes. It is probably as good as it can be in Prolog. My only other hope would be using mode directed tabling. Possibly you an tweak that to do what you want, but it will always be a lot more expensive.

12

Each to their own I suppose, but under those guises you might as well implement it in C.

14

That rather depends on the SWI Prolog C API, but presumably it caters for that? Further, if memory is copied to Prolog at the end of the call then presumably all allocation can happen within the function. It largely depends on how the API works rather than whether its possible to free memory in an interop :slight_smile: