# Mark Gilbert's Blog

## Solving The Island Problem, Part II

Last Wednesday, we held our monthly FLUNK meeting, and I showed off my implementation of Grand Theft Wumpus.  When I got around to talking about how I solved the island problem, a very interesting conversation developed.  Eventually the conversation became focused on answering the question – what did my technique actually do?  (For a full refresher, see the section titled "Solving the Island Problem" in my previous post.)

For the remainder of this post, I’ll use the convention of referring to individual cells in the matrices using the form "X-Y", where "X" is the 1-indexed row number, and "Y" is the 1-indexed column number.  A 1 in a given cell means that there is an undirected edge that connects nodes X and Y.

The "technique" that I’ll evaluate is representing the graph as a half-matrix, where only the edges below the diagonal are shown.  The technique is broken up into two phases – analysis and bridging.

Q: Does the analysis technique identify the islands?
A: No.

If you look at the half-matrices for the connected graph and the island graph, the change is rather minute:

My technique says to add 1s so that every row (or column) end up with at least a single 1.  Removing the 4-2 edge doesn’t open up the 4th row.  In fact, it’s no clearer what the islands are in my graph now than before.

In this image, the edges that form one island is represented by the green box, and the second by the blue box.  The two aren’t separated by a gap that removing the 4-2 edge opened up (i.e., a newly blanked row).

Q: Does the analysis technique even tell us if there islands at all?
A: No.

As before, the matrix representation doesn’t make it any easier to see if we have a single graph that connects every node.  The half-matrix for the connected graph has a complete empty row 3, and a completely empty column 5.  No clues there.

Q: Does the bridging technique connect the islands in a minimal way?  In other words, am I guaranteed that we won’t be building bridges to nodes that were already part of a connected graph?
A: No.

The analysis technique will identify row 3 as having no 1s in the original, connected graph’s half-matrix.  That would have triggered a 1 to be added to cells 3-1, 3-2, or 3-3 (it will pick one of these at random).  However, the original graph was already connected – there should be no need to add another edge at all.

And now I can answer the original question: What does this technique do?

It ensures that by the end we will have a single graph that connects all of the nodes.  It won’t be necessarily a minimal graph, but we can be assured there won’t be any islands left.