List as graph in prolog

Question

I'm trying to generate all possible 'ways' from one element in matrix to another, Main conditional says that Element in matrix can be connected with other only if elements share at least one corner so in that matrix

[[1,2,3]
 [5,4,6]
 [8,9,7]]

1 can be only conected with 2,4,5 but 4 is conected with all elements. Is it possible to represent that list as graph without using attract? Or maybe I can find out any easier way to do it

---

Thanks for all answers. Ok i set forth :-) Now with predicates I generated all 'edges' but i cannot use them anywhere, I could not figure out, how to add to accumulator(list) infomrations of each cell with such pattern ([row:R1,column:C1,value:V1], [row:R2,column:C2,value:V2]).

Answer 1

Enumeration of a finite set can be done easily using Prolog backtracking:

adjacent_pos((R,C), (Ra,Ca)) :-
     (R > 1, Ra is R-1 ; Ra is R ; Ra is R+1),
     (C > 1, Ca is C-1 ; Ca is C ; Ca is C+1),
     once(Ra \= R ; Ca \= C).

Using paired nth1/3 we can access a cell:

cell(Mat, (R,C), Cell) :-
     nth1(R, Mat, Row),
     nth1(C, Row, Cell).

So, in a matrix NxM of distinct elements:

adjacent(Mat, Elem, Adj) :-
     cell(Mat, Pe, Elem),
     adjacent_pos(Pe, Pa),
     cell(Mat, Pa, Adj).

simple test:

test :-
   M = [[1,2,3],
        [5,4,6],
        [8,9,7]],
   findall(A, adjacent(M,1,A), L1), writeln(L1),
   findall(A, adjacent(M,4,A), L4), writeln(L4).

yields:

?- test.
[2,5,4]
[1,2,3,5,6,8,9,7]
true.

Note that the test R > 1 and C > 1 could be avoided, demanding to nth1/3 failure the 'out of band' test. The same is true for the upper limit, omitted indeed, with the added benefit that we are not limited to a predefined matrix size.

Answer 2

Here's a (long, but simple) solution to consider.

Firstly, it helps to have an auxiliary predicate to retrieve an element from the Row,Col position in a matrix as a list of lists, such as:

get_matrix_entry_nth0(RowInd, ColInd, Matrix, Entry) :-
    nth0(RowInd, Matrix, Row),
    nth0(ColInd, Row, Entry).

Secondly, it can also help to use this predicate to define the entries relative to ones indexed by Row and Col in terms of directions, such as:

up_left_entry(R-C, Matrix, E) :-
    PrevR is R - 1,
    PrevC is C - 1,
    get_matrix_entry_nth0(PrevR, PrevC, Matrix, E).

up_entry(R-C, Matrix, E) :-
    PrevR is R - 1,
    get_matrix_entry_nth0(PrevR, C, Matrix, E).

up_right_entry(R-C, Matrix, E) :-
    PrevR is R - 1,
    NextC is C + 1,
    get_matrix_entry_nth0(PrevR, NextC, Matrix, E).

right_entry(R-C, Matrix, E) :-
    NextC is C + 1,
    get_matrix_entry_nth0(R, NextC, Matrix, E).

down_right_entry(R-C, Matrix, E) :-    
    NextR is R + 1,
    NextC is C + 1,
    get_matrix_entry_nth0(NextR, NextC, Matrix, E).

down_entry(R-C, Matrix, E) :-
    NextR is R + 1,
    get_matrix_entry_nth0(NextR, C, Matrix, E).

down_left_entry(R-C, Matrix, E) :-    
    NextR is R + 1,
    PrevC is C - 1,
    get_matrix_entry_nth0(NextR, PrevC, Matrix, E).

left_entry(R-C, Matrix, E) :-
    PrevC is C - 1,
    get_matrix_entry_nth0(R, PrevC, Matrix, E).

With these auxiliary predicates in place, the solution is fairly straightforward:

matrix_path([R|Rs], P) :-
    % determine rows, cols
    length([R|Rs], Rows),
    length(R, Cols),
    % defer to matrix_path/4 to compute all paths starting with 0,0
    matrix_path(0-0, Rows-Cols, [R|Rs], P).

matrix_path/2 is the entry-point to the program. This single-clause predicate pre-determines the number of rows and columns in the given matrix, and defers processing to matrix_path/4 which starts computation from the 0,0 (top-left) element.

matrix_path(R-C, Rows-Cols, Matrix, P) :-
    C >= Cols, !,
    % end of column, proceed to next row
    NextRow is R + 1,
    NextRow < Rows,
    matrix_path(NextRow-0, Rows-Cols, Matrix, P).

The first clause of matrix_path/4 checks if the number of columns has been exceeded; if so, a cut (!) is used to exclude the clauses below, and re-starts the computation in the next row and resets the column index to 0.

matrix_path(R-C, _, Matrix, adj(S, T)) :-
    % get this entry
    get_matrix_entry_nth0(R, C, Matrix, S),
    % get each adjacent entry
    (   up_left_entry(R-C, Matrix, T)
    ;   up_entry(R-C, Matrix, T)
    ;   up_right_entry(R-C, Matrix, T)
    ;   right_entry(R-C, Matrix, T)
    ;   down_right_entry(R-C, Matrix, T)
    ;   down_entry(R-C, Matrix, T)
    ;   down_left_entry(R-C, Matrix, T)
    ;   left_entry(R-C, Matrix, T)
    ).

The second clause of matrix_path/4 simply tries to retrieve all possible 'paths' from the given entry. Some may fail (such as looking up in the top row), but Prolog will backtrack to find all solutions that work.

matrix_path(R-C, Rows-Cols, Matrix, P) :-
    % get the entry for the next column in this row
    NextC is C + 1,
    matrix_path(R-NextC, Rows-Cols, Matrix, P).

The last clause of matrix_path/4 simply shifts processing relative to the item in the next column in the same row.

Running a simple example:

?- matrix_path([[1,2],[3,4]], P).
P = adj(1, 2) ;
P = adj(1, 4) ;
P = adj(1, 3) ;
P = adj(2, 4) ;
P = adj(2, 3) ;
P = adj(2, 1) ;
P = adj(3, 1) ;
P = adj(3, 2) ;
P = adj(3, 4) ;
P = adj(4, 1) ;
P = adj(4, 2) ;
P = adj(4, 3) ;
false.

Note that if you want all adjacent pairs immediately without backtracking, wrap the call in a findall/2, like this:

?- findall(P, matrix_path([[1,2],[3,4]], P), Ps).
Ps = [adj(1, 2), adj(1, 4), adj(1, 3), adj(2, 4), adj(2, 3), adj(2, 1), adj(3, 1), adj(3, 2), adj(..., ...)|...].