Floyd and Warshall's algorithms in Prolog

I want to program this algorithms in Prolog, and first I need to create a matrix from a list of graphs. I've done this before (also with help of some of y开发者_运维问答ou, guys), but now I don't know how to store it inside a list of lists (which I suppose it's the best approach in prolog's case). I think I can be able to continue from there (with the triple for loop in each of the algorithms). The logic of the program is not difficult for me, but how to work with data. Sorry for being a bother and thanks in advance!

My matrix generator:

graph(a,b).
graph(a,a).
graph(b,c).
graph(b,d).
graph(c,d).
graph(a,e).
graph(e,f).

matrix :- allnodes(X),printmatrix(X).

node(X) :- graph(X,_).
node(X) :- graph(_,X).
allnodes(Nodes) :- setof(X, node(X), Nodes).

printedge(X,Y) :-    graph(Y,X), write('1 ').
printedge(X,Y) :- \+ graph(Y,X), write('0 ').

printmatrix(List):- member(Y, List),nl,member(X, List),printedge(X,Y),fail.

Your previous question Adjacency Matrix in prolog dealt with the visual display (row over row) of the adjacency matrix of a graph. Here we address how to realize/represent the adjacency matrix as a Prolog term. In particular we will adopt as given the allnodes/1 predicate shown above as a means of getting a list of all nodes.

Prolog lacks any native "matrix" data type, so the approach taken here will be to use a list of lists to represent the adjacency matrix. Entries are organized by "row" in 0's and 1's that denote the adjacency of the node corresponding to a row with that node corresponding to a column.

Looking at your example graph/2 facts, I see that you've included one self-edge (from a to a). I'm not sure if you intend the graph to be directed or undirected, so I'll assume a directed graph was intended and note where a small change would be needed if otherwise an undirected graph was meant.

There is a "design pattern" here that defines a list by applying a rule to each item in a list. Here we do this one way to construct each row of the "matrix" and also (taking that as our rule) to construct the whole list of lists.

/* construct adjacency matrix for directed graph (allow self-edges) */
adjacency(AdjM) :-
    allnodes(L),
    adjMatrix(L,L,AdjM).

adjMatrix([ ],_,[ ]).
adjMatrix([H|T],L,[Row|Rows]) :-
    row_AdjM(H,L,Row),
    adjMatrix(T,L,Rows).

row_AdjM(_,[ ],[ ]).
row_AdjM(X,[Y|Ys],[C|Cs]) :-
    (   graph(X,Y)
     -> C = 1
     ;  C = 0
    ),
    row_AdjM(X,Ys,Cs).

If an undirected graph were meant, then the call to graph(X,Y) should be replaced with an alternative ( graph(X,Y); graph(Y,X) ) that allows an edge to be considered in either direction.