Mark Gilbert's Blog

Science and technology, served light and fluffy.

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:

Half Matrices Side By Side

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.

Half Matrix - Identifying the Islands

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.

 

My final answer
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.

An “adjoining” thought

As I was writing this post, it occurred to me that you might be able to make an argument that putting a 1 in an “adjoining cell” would connect the islands. 

Half Matrix - Identifying the Islands

To create a graph with islands, I removed a 1 from cell 4-2, which adjoins cell 4-3.  Obviously putting that 1 back to 4-2 would bridge the islands, but adding a 1 to one of the other adjoining cells – 5-3 or 6-2 in this case – would also work.  This bridging technique could be stated as “make sure there is at least one pair of adjoining cells in each island pair have 1s.”

However, being able to use the "adjoining cells" technique only works if you know where the islands are already, and that’s not obvious by just looking at the matrix – I had to effectively traverse the graph to see it.

Furthermore, it only works if the islands are actually adjoined in the matrix.  Imagine a graph if 6 nodes and NO edges.  In this case, the graph would have 6 islands.  The matrix would be all 0s, and I’m hard-pressed to figure out how to color the 6 islands in it – there wouldn’t be any 1s to guide me.  Even if I could color the islands, they wouldn’t be touching each other, and therefore I have no way to identify the “adjoining cells” to put 1s into.

Advertisements

February 15, 2012 - Posted by | F#

Sorry, the comment form is closed at this time.

%d bloggers like this: