Check if some elements in a matrix are cohesive

Question

I have to write a very little Python program that checks whether some group of coordinates are all connected together (by a line, not diagonally). The next 2 pictures show what I mean. In the left picture all colored groups are cohesive, in the right picture not:

I've already made this piece of code, but it doesn't seem to work and I'm quite stuck, any ideas on how to fix this?

def cohesive(container):
   co = container.pop()
   container.add(co)
   return connected(co, container)

def connected(co, container):
   done = {co}
   todo = set(container)
   while len(neighbours(co, container, done)) > 0 and len(todo) > 0:
       done = done.union(neighbours(co, container, done))
   return len(done) == len(container)

def neighbours(co, container, done):
   output = set()
   for i in range(-1, 2):
       if i != 0:
           if (co[0] + i, co[1]) in container and (co[0] + i, co[1]) not in done:
               output.add((co[0] + i, co[1]))
           if (co[0], co[1] + i) in container and (co[0], co[1] + i) not in done:
               output.add((co[0], co[1] + i))
   return output

this is some reference material that should return True:

cohesive({(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)})

and this should return False:

cohesive({(1, 2), (1, 4), (2, 2), (0, 3), (0, 4)})

Both tests work, but when I try to test it with different numbers the functions fail.

Answer 1

You can just take an element and attach its neighbors while it is possible.

def dist(A,B):return abs(A[0]-B[0]) + abs(A[1]-B[1])

def grow(K,E):return {M for M in E for N in K if dist(M,N)<=1}

def cohesive(E):
    K={min(E)} # an element 
    L=grow(K,E)
    while len(K)<len(L) : K,L=L,grow(L,E)
    return len(L)==len(E)

grow(K,E) return the neighborhood of K.

In [1]: cohesive({(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)})
Out[1]: True

In [2]: cohesive({(1, 2), (1, 4), (2, 2), (0, 3), (0, 4)})
Out[2]: False

Answer 2

Usually, to check if something is connected, you need to use disjoint set data structures, the more efficient variations include weighted quick union, weighted quick union with path compression.

Here's an implementation, http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html which you can modify to your needs. Also, the implementation found in the book "The Design and Analysis of Computer Algorithms" by A. Aho, allows you to specify the name of the group that you add 2 connected elements to, so I think that's the modification you're looking for.(It just involves using 1 extra array which keeps track of group numbers).

As a side note, since disjoint sets usually apply to arrays, don't forget that you can represent an N by N matrix as an array of size N*N.

EDIT: just realized that it wasn't clear to me what you were asking at first, and I realized that you also mentioned that diagonal components aren't connected, in that case the algorithm is as follows:

0) Check if all elements refer to the same group.

1) Iterate through the array of pairs that represent coordinates in the matrix in question.

2) For each pair make a set of pairs that satisfies the following formula:

|entry.x - otherEntry.x| + |entry.y - otherEntry.y|=1.

'entry' refers to the element that the outer for loop is referring to.

3) Check if all of the sets overlap. That can be done by "unioning" the sets you're looking at, at the end if you get more than 1 set, then the elements are not cohesive.

The complexity is O(n^2 + n^2 * log(n)).

Example:

(0,4), (1,2), (1,4), (2,2), (2,3)

0) check that they are all in the same group:

all of them belong to group 5.

1) make sets:

set1: (0,4), (1,4)

set2: (1,2), (2,2)

set3: (0,4), (1,4) // here we suppose that sets are sorted, other than that it should be (1,4), (0,4)

set4: (1,2), (2,2), (2,3)

set5: (2,2), (2,3)

2) check for overlap:

set1 overlaps with set3, so we get:

set1' : (0,4), (1,4)

set2 overlaps with set4 and set 5, so we get:

set2' : (1,2), (2,2), (2,3)

as you can see set1' and set2' don't overlap, hence you get 2 disjoint sets that are in the same group, so the answer is 'false'.

Note that this is inefficient, but I have no idea how to do it more efficiently, but this answers your question.

Answer 3

I'd tackle this problem differently... if you're looking for five exactly, that means:

1. Every coordinate in the line has to be neighbouring another coordinate in the line, because anything less means that coordinate is disconnected.
2. At least three of the coordinates have to be neighbouring another two or more coordinates in the line, because anything less and the groups will be disconnected.

Hence, you can just get the coordinate's neighbours and check whether both conditions are fulfilled.

Here is a basic solution:

def cells_are_connected(connections):
    return all(c > 0 for c in connections)

def groups_are_connected(connections):
    return len([1 for c in connections if c > 1]) > 2

def cohesive(coordinates):
    connections = []
    for x, y in coordinates:
        neighbours = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
        connections.append(len([1 for n in neighbours if n in coordinates]))
    return cells_are_connected(connections) and groups_are_connected(connections)

print cohesive([(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)]) # True
print cohesive([(1, 2), (1, 4), (2, 2), (0, 3), (0, 4)]) # False

No need for a general-case solution or union logic. :) Do note that it's specific to the five-in-a-line problem, however.

Answer 4

The logic in your connected function seems wrong. You make a todo variable, but then never change its contents. You always look for neighbours around the same starting point.

Try this code instead:

def connected(co, container):
   done = {co}
   todo = {co}
   while len(todo) > 0:
       co = todo.pop()
       n = neighbours(co, container, done)
       done = done.union(n)
       todo = todo.union(n)
   return len(done) == len(container)

todo is a set of all the points we are still to check.

done is a set of all the points we have found to be 4-connected to the starting point.