Floyd-Warshall algorithm in Prolog (original) (raw)

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 ?

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