Determine if nodes are connected in matrix in Prolog

Question

So what I get is a list that contains coordinates in a matrix. For example:

List 1: [[1, 1], [2, 1], [3, 1], [4, 1], [2, 2], [1, 3], [2, 3], [3, 3], [4, 3]]

List 2: [[1, 1], [2, 1], [3, 1], [4, 1], [1, 3], [2, 3], [3‚3], [4, 3]]

I need to figure out if all these nodes are connected to each other. That is, if I choose any arbitrary node, I can reach any other node. This is true for List 1 but not for List 2, as there is no way for me to get from any of the first 4 nodes to any of the last 4 nodes. In List 1, the node [2, 2] acts as a bridge and therefore it is true.

I managed to write a predicate that will return the neighbours for a specific cell, but I am not sure how to continue.

Edit: So here is what I have now:

getXY([X, Y], X, Y).

findNeighbours(A, A, B, B).
findNeighbours(_, [], A, A).
findNeighbours(Cell, [Head|Tail],Temp, Neighbours):-
    getXY(Cell, Cx, Cy),
    getXY(Head, Hx, Hy),
    isNeighbour(Cx, Cy, Hx, Hy),
    append([Head], Temp, Merged),
    findNeighbours(Cell, Tail, Merged, Neighbours), !.

findNeighbours(Cell, [Head|Tail],Temp, Neighbours):-
    getXY(Cell, Cx, Cy),
    getXY(Head, Hx, Hy),
    not(isNeighbour(Cx, Cy, Hx, Hy)),
    findNeighbours(Cell, Tail, Temp, Neighbours), !.

isNeighbour(Cx, Cy, Hx, Hy) :-
    Cx = Hx, Cy is Hy + 1
    ; Cx = Hx, Cy is Hy - 1
    ; Cx is Hx + 1, Cy = Hy
    ; Cx is Hx - 1, Cy = Hy.

Edit 2: You can only move 1 cell to the left/up/right/down. Each cell in the matrix has an X and Y coordinate. In List 1 I can reach any node from an arbitrary node, because there is always one neighbouring node. So, by reach I mean go from node A to node B only incrementing X or Y by 1.

@vmg, sure. It's probably overly complicated (Kinda new to prolog). I'll edit the main post straight away. — Zahand, Dec 02 '15 at 14:21
Please define *reach*. What does it mean to be able to *reach* one node from another? — lurker, Dec 02 '15 at 14:30

score 2 · Answer 1 · edited May 23 '17 at 12:07

let's put closure/3 to work

'all these nodes are connected'(L) :-
    forall((select(S,L,R),member(T,R)), closure(connected(L),S,T)).

connected(L, [Cx, Cy], [Hx, Hy]) :-
    member([Hx, Hy], L),
    isNeighbour(Hx, Hy, Cx, Cy).

yields

?- 'all these nodes are connected'([[1, 1], [2, 1], [3, 1], [4, 1], [2, 2], [1, 3], [2, 3], [3, 3], [4, 3]]).
true.

?- 'all these nodes are connected'([[1, 1], [2, 1], [3, 1], [4, 1], [1, 3], [2, 3], [3, 3], [4, 3]]).
false.

Some explanation: forall(:Cond, :Action)

For all alternative bindings of Cond, Action can be proven.

I've put this join as :Cond

select(S,L,R),member(T,R)

select coupled to member allows to apply :Action to each pair of coordinates. Action it's a proof of closure(R_2, X0,X), that is if X is reachable from X0, using as predicate R_2.

Since isNeighbour/4 receives [Hx, Hy] unbound, I pass the whole coordinates list, and let member/2 peek a coordinate to test...

Determine if nodes are connected in matrix in Prolog

1 Answers1