how can I determine that all given coordinates of matrix are connected?

Question

Given a grid how can I determine if elements of a grid are all in a single region. In the below case is true because each element in the matrix has a neighbor.

Example1:

gridneighbours([[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[4,1],[4,2]]).
true.

However in my second example, Example2:

gridneighbours([[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[3,1],[4,1],[4,2]]).
false.

This is false because [3,1],[4,1],[4,2] are disjoint to the previous elements. Initially I tried using subset from Prolog to check for an existing element next to another by simply adding or subtracting from X or Y, however this doesn't work because elements of a split region would be next to each other. Also diagonals don't count as being next to each other.

Updated, added code: Here is what I got:

%Check right
neighbourcheck([X,Y|_],S) :- X1 is X + 1, subset([[X1,Y]],S).
%Check left
neighbourcheck([X,Y|_],S) :- X1 is X - 1, subset([[X1,Y]],S).
%Check Up
neighbourcheck([X,Y|_],S) :- Y1 is Y + 1, subset([[X,Y1]],S).
%Check Down
neighbourcheck([X,Y|_],S) :- Y1 is Y - 1, subset([[X,Y1]],S).
% Iterate through all sublists and check for neighbours
gridneighbour(S) :- forall(member(X,S), neighbourcheck(X,S)).

The reason why this doesn't work is because subset doesn't care if we have a match up with another element that is disjointed. i.e. [3,1] matches up with [4,1]. Running this code and using the examples above give:

• Example1: True
• Example2: True (clearly this should be false because [3,1],[4,1]and [4,2] are seperated).

Certainty

Answer 1

A naive approach that works can be outlined as follows:

• Start with two sets (lists?) of points: those that you know belong to a region, Region and the rest, Rest. At the beginning, you can pick any single point to belong to Region, and whatever remains is in Rest.
• Look in Rest for a point that is a neighbor to any point in Region.
  • if you find a neighbor, move it from Rest to Region and repeat
  • if you don't find a neighbor, stop
• If there are points in Rest at the end, then this is not a region.

Here is a simpler way to define neighbors/2:

neighbors([X1,Y1], [X2,Y2]) :-
    abs(X1-X2) + abs(Y1-Y2) =:= 1.

You can look for a point in one list that is a neighbor of a point in another list by simply trying out every possible combination:

% add_to_region(+Region0, +Rest0, -Region, -Rest)
%% Look in Rest0 for a neighbor to Region0;
%% Region is Region0 with the neighbor,
%% Rest is Rest0 without it
add_to_region(Region, Rest0, [B|Region], Rest) :-
    member(A, Region),
    select(B, Rest0, Rest),
    neighbors(A, B).

The call to member/2 picks each point in Region to A, by backtracking. The call to select/3 picks each point in Rest0 to B, with rest of the points in Rest. If the two points are neighbors, B is added to front of Region.

This will fail if there is no more neighbors to the current region in Rest, and succeed at least once if there are. You might want to call this with once(add_to_region(Region0, Rest0, Region, Rest)) so that you don't have unnecessary choice points. Using your examples:

?- once(
      add_to_region(
         [[1,1],[1,2],[1,3],[2,1]],
         [[2,2],[2,3],[3,1],[4,1],[4,2]],
         Region, Rest)).
Region = [[2, 2], [1, 1], [1, 2], [1, 3], [2, 1]],
Rest = [[2, 3], [3, 1], [4, 1], [4, 2]].

See how [2,2] was picked from Rest and added to Region.

?- add_to_region(
   [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]],
   [[3,1],[4,1],[4,2]],
   Region, Rest).
false.

This fails because none of the points in Rest is a neighbor to any of the points in Region.

Edit

As explained above is definitely doable, but with a slight modification, we can have an algorithm that is much easier to implement in Prolog. It goes like this:

set_region_rest(+Set, -Region, -Rest)

• Sort the set of points to standard order of terms; now you have an ordset.
• Split this set into a Region and a Rest that does not belong to it

To do the splitting, we will maintain one extra list. We will call it a list of Open nodes: nodes that we haven't explored yet. At the beginning, the first element of our input list is the only open node. The rest of the elements are passed as they are. The last two arguments, the Region, and the Rest, are the output arguments.

open_set_closed_rest(Open, Set, Closed, Rest)

• If the Open set is empty, so is the rest of the Closed set (now the Region); the remaining Set is the Rest.
• Otherwise:
  • Take the first pair of coordinates from the Open list; immediately put it at the front of the Closed coordinates.
  • Try to find any of the neighbors of this first pairs in the Set of coordinates; if you find any, append these to the front of the Open set; the rest of Set after removing the neighbors is the new Set.
  • Try again with the new Open set, the rest of the Closed set, the remaining Set, and the Rest.

To do this in Prolog, I will first clean up the coordinate representation. It is a bit annoying that they come in lists of two: it is far less writing if we used for example a pair instead: [X,Y] ---> X-Y. To do this, I add this predicate:

xy(XY) :-
        coordinates(C),
        maplist([[X,Y], X-Y]>>true, C, XY).
xy([1-1,1-3,1-2]).
xy([1-2,2-1,2-2]).
xy([1-1, 1-2, 1-3, 1-4, 1-5,
    2-1,                2-5,
    3-1,                3-5,
    4-1,                4-5,
    5-1, 5-2, 5-3, 5-4, 5-5]).
xy([1-1, 1-2, 1-3, 1-4, 1-5,
    2-1,                2-5,
    3-1,      3-3,      3-5,
    4-1,                4-5,
    5-1, 5-2, 5-3, 5-4, 5-5]).

coordinates([[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[4,1],[4,2]]).
coordinates([[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[3,1],[4,1],[4,2]]).

(I also put 4 additional test sets!)

So with this, I get:

?- xy(XY).
XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, ... - ...] [write] % press 'w' here
XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, 4-2] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 3-1, 4-1, 4-2] ;
XY = [1-1, 1-3, 1-2] ;
XY = [1-2, 2-1, 2-2] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-3, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5].

Here is how one could try to write the above algorithms in code:

set_region_rest([A|As], Region, Rest) :-
        sort([A|As], [B|Bs]),
        open_set_closed_rest([B], Bs, Region, Rest).

This just sorted the input Set and split off the first element from it. The first element is the first coordinate pair in the Open set, the rest is the Set, then the output arguments.

Now, to split the Set into a Region and a Rest, we need to keep on growing the Region as long as we have coordinate pairs in the Open set. If the Open set is empty, this means our Region is complete, and the remaining Set is the Rest:

:- use_module(library(clpfd)).

open_set_closed_rest([], Rest, [], Rest).

To find out which neighbors of a coordinate are in the Set, we use ord_intersection/4, which gives us the neighbors in Set and the rest of Set at the same time.

NB: The 4 neighbor coordinates are listed sorted!

open_set_closed_rest([X-Y|As], Set, [X-Y|Closed0], Rest) :-
        X0 #= X-1, X1 #= X + 1,
        Y0 #= Y-1, Y1 #= Y + 1,
        ord_intersection([X0-Y,X-Y0,X-Y1,X1-Y], Set, New, Set0),
        append(New, As, Open),
        open_set_closed_rest(Open, Set0, Closed0, Rest).

This is it. With this, I get the following 6 solutions:

?- xy(XY), set_region_rest(XY, Region, Rest).
XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, 4-2],
Region = [1-1, 1-2, 1-3, 2-3, 2-2, 2-1, 3-1, 4-1, 4-2],
Rest = [] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 3-1, 4-1, 4-2],
Region = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6],
Rest = [3-1, 4-1, 4-2] ;
XY = [1-1, 1-3, 1-2],
Region = [1-1, 1-2, 1-3],
Rest = [] ;
XY = [1-2, 2-1, 2-2],
Region = [1-2, 2-2, 2-1],
Rest = [] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5],
Region = [1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5, 5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1],
Rest = [] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-3, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5],
Region = [1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5, 5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1],
Rest = [3-3].

By the way, using set_region_rest/3 as a building block, we can easily split a set of coordinates into regions:

set_regions([], []).
set_regions([X|Xs], [R|Rs]) :-
        set_region_rest([X|Xs], R, Rest),
        set_regions(Rest, Rs).

So now:

?- set_regions([1-1, 1-2, 1-3, 1-4, 1-5,      1-7,
                2-1,                2-5,      2-7,
                3-1,      3-3,      3-5,      3-7,
                4-1,                4-5,
                5-1, 5-2, 5-3, 5-4, 5-5,      5-7], R).
R = [[1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5,
      5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1],
     [1-7, 2-7, 3-7],
     [3-3],
     [5-7]].

Kesley

@Certainty [B|Region] is just the list Region with B at its head. You will see Rest0 below, in the call to select/3 (read the documentation to select/3!). If you are having trouble with Prolog syntax, maybe you should try to work your way through a tutorial first? – Kesley

@Certainty see the edit with a bit of explanation. – Kesley

Thanks Boris, I'm finding it easier to follow now. :) – Certainty

Assuming that we only know Head is in Region. How would we go about iterating through entire list using add_to_region? I've tried implementing some sort of recursion in add_to_region but not having any luck. – Certainty

@Certainty I will try to add a full solution. – Kesley

Answer 2

This problem can be viewed as an instance of union find algorithms. Such algorithms often make use of a special data structure, which basically serves the following two purposes:

1) For a point p, find a representant p* 
   in the data structure
2) For two representants p1* and p2* extend 
   the data structure by connecting both

Here is a Prolog implementation that uses a thread local fact linked/2 as the union find data structure. Here is an example run for the second grid problem:

?- regions(L).
L = [(1, 6),  (4, 2)].

Technical note: Prolog unification has also a built-in union find component, if you mention a variable X, it will be dereferenced, which is step 1). If you do the unification X=Y and X and Y are already dereferenced, one variable will link to another, which is step 2).

Chimney

Can you explain your "technical note" a bit better? Or solve the problem using that? – Kesley

Technical note should help understand the algorithm, you see an instance of the algorithm all the time working with Prolog. Try in a query X=Y, X=Z, T=W. The Prolog interpreter and its top-level will determine that X,Y,Z are connected and T,W are connected. But since the grid points are not Prolog variables, this cannot directly be used. Maybe indirectly somehow? – Chimney

If I understand your code (why on a link and not here?), you find the transitive closure of each region, and use that to find regions? – Kesley

Yeah, transitive, symmetric and reflexive closure is computed on the fly. But there are a lot of variations to the algorithm. For example I don't order the grid points, when a new link is established, I am just using the input order which might generate degenerate deref chains, and hence the algorithm is not always linear. – Chimney