-5

I have a group of squares on a 2d grid, here's an example

grid with group of squares

I need an algorithm to find out whether we are able to remove a square while keeping the entire group connected. Below is an image where I colored squares that are possible to remove in green, and squares that would make the group disconnected if removed in red.

group of squares colored by ability to remove with group staying connected

My current method is to remove the square from the group, and run a flood fill algorithm starting from an arbitrary square to see whether the group is connected or not. If the number of squares retrieved from the flood fill is less than the total number of squares for the group, we know that the group is not connected, in 2+ pieces. This is not very performant and it is better to be able to know whether a square is removable before actually removing it.

I noticed that we can tell whether the square is removable by just its surrounding 8 squares. Edit: As @KilianFoth pointed out in a comment, this is not always true. However, in my case I can ensure that there is no longer path connecting figure 1 for example.

Here are several examples, centered on the square in question.

6 examples of 3x3 grids showing whether the middle square is removable

I can create a list of booleans representing whether each surrounding square is in the group. It could be in the form [north, ne, e, se, s, sw, w, nw] going clockwise around, so number 6 on the image above would be [False, True, True, False, False, False, True, True]. I need a function/algorithm that can take in one of these lists, and output whether the square is removable or not. Here are examples from the above images.

[True, False, False, False, False, False, True, False] -> False (not removable) [True, False, False, False, False, False, True, True] -> True (removable) [True, False, True, False, False, False, True, True] -> False [True, True, True, False, False, False, True, True] -> True [True, True, True, False, True, False, True, True] -> False [False, True, True, False, False, False, True, True] -> False

If it works better, the bools can be variables like north or southeast.

My first thought was to check the cardinal directions, and if there are only two squares in our group, then it isn't removable. This works for examples 1, 4, and 6, but gets 2, 3 and 5 wrong. I know the algorithm needs to take diagonals into account, because 1 and 2 are the same only including cardinal directions.

How can I make an algorithm that tells me whether or not a square is removable from the group without causing disconnection?

Improve this question
17
  • 1
    "I noticed that we can tell whether the square is removable by just its surrounding 8 squares." - Your premise is wrong. The local context only defines a sufficient condition, not a necessary one. The squares that seemingly become disconnected e.g. in figure 1 might still be connected via a longer path. Commented Nov 26, 2020 at 19:01
  • @KilianFoth While this is true for what I wrote, in my case I can ensure that figure 1 is not connected by a longer path. If they were connected by a longer path, there would be a hole in the middle, and since my grid is tiled several groups of the same size, this would not be possible (size of hole < size of group). I should've included this in the question though thank you. Commented Nov 26, 2020 at 19:10
  • Since your examples show that diagonal connections don’t count I fail to see why you count the surrounding squares as 8. It’s seems there are only 4. Please define “connected” clearly. Commented Nov 26, 2020 at 20:09
  • (stackoverflow.com/questions/16003032/…) you might be able to use part of what is shown in the question and the answer from this SO question. Basically, take dijkstra's algorithm and perform a breadth first search that each "left over" square has a path to each other. Commented Nov 26, 2020 at 20:19
  • 2
    You wrote "However, in my case I can ensure that there is no longer path connecting figure 1 for example" - so you want to solve a different problem than the one described initially, but you missed to tell us precisely what you mean by "your case", Sorry, the problem statement is not clear from what you wrote. In case you mean you want to detect "disconnections by removals" in a 3x3 rectangle: that's trivial. This won't guarantee to be disconnections in any kind of bigger area, however, as you have been told. Voting to close as "unclear". Commented Nov 27, 2020 at 6:50

3 Answers 3

Reset to default
0

With help from a few comments, I realized that all I have to do was check to see if the surrounding squares are touching each other. I noticed a pattern with my bool lists above - if there is more than one chain/streak of True's (including carrying over between start and end of the list), then removing the square will cause a disconnected group. If there is more than one streak of True's, (checked by longest_true_chain != num_trues), then the surrounding squares are not connected and the square is not removable.

Here is my python code

def removable(bool_list): num_trues = bool_list.count(True) longest_true_chain = 0 current_true_chain = 0 for b in bool_list*2: # use *2 to include streaks carrying across nw to n (end to beginning of list) if b: current_true_chain += 1 else: longest_true_chain = max(longest_true_chain, current_true_chain) current_true_chain = 0 longest_true_chain = max(longest_true_chain, current_true_chain) return longest_true_chain >= num_trues
Improve this answer
3
  • Code doesn't seem to work with all true s Commented Nov 27, 2020 at 0:48
  • @RiaD Thanks I modified the last 2 lines and it should now. Commented Nov 27, 2020 at 1:26
  • 1
    I think this approach only works, if you group of squares does not contain holes. If it is allowed to contain holes, you cannot decide connectivity by just looking at the local neighborhood. Commented Nov 27, 2020 at 2:38
0

Idea #1

Apply morphological erosion repeatedly. After each step, count the number of connected components, and compare with the number from the previous step.

If the number of connected components have changed, a new disconnection has occurred. When that is detected, perform a more detailed check of each of the squares that were removed in the most recent round of morphological erosion, to find out which one(s) caused the disconnection.

This can be combined with all other approaches mentioned in other answers.

The benefit of using morphological erosion is that it is a "batch processing", i.e. it can remove a large number of squares in each step, as long as disconnection has not happened. Once a disconnection happened, though, a more detailed check is needed.

Idea #2

Random network flow check.

Randomly pick some pairs of squares. For each pair of squares, compute their path. On a new map, increment the score of each square along the path. Repeat.

If there are "bottlenecks", namely squares that appear to be quite essential to the connection between random pairs of squares, it might be the case that removing a square from these bottlenecks may cause a disconnection. However, this is not a failproof approach. It is a heuristics that sometimes give wrong result.

Improve this answer
-1

Consider a graph where vertices are squares and they are connected by an edge if the squares are connected on the grid. Then you need to find vertices which you can delete without losing connectivity. They are exactly all vertices except cut vertices by definition. There's a well known algorithm to find all cut vertices which is basically one DFS. It's described on the same wiki page.

Improve this answer
1
  • 2
    This is a solution for finding all of the potential removable squares in an efficient manner, not just testing one. Not sure if that is what the OP meant. Commented Nov 27, 2020 at 9:40

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.