Appendix:

Permuting a string

Clearing marked nodes

When dealing with nodes with loops we have to mark the nodes we have already visited to avoid infinite recursion. This is fine if we only ever want to ru the function once but if we wish to run the function again we must clear these marks. The general method is much the same as marking:

Check, Unmark, Recurse

void unmark(some_args) {
  if (node_has_not_been_visited)
    return;                          //Check 

  // Mark this node as NOT visited;  //Unmark 

  umark(some_other_args);            //Recurse
}

Flood fill example

In our flood fill example we may imaging that the number of pixels changes in some way: perhaps as new material is removed or deposited. We therefore need to reset our image before recalculating the islands. Note how we follow the order Check, Unmark, Recurse.

Connectivity of a mesh

Consider an array of nodes each of which is linked to each of its four neighbours to form a mesh. If we arbitrarily take the top edge of the mesh as our base we may then travel to the opposite (bottom) edge via a path made up of neighbouring nodes: we say that the top and bottom edges are connected:

0-0-0-0-0
| | | | |
0-0-0-0-0
| | | | |
0-0-0-0-0
| | | | |
0-0-0-0-0

Notes:

• There are no explicit bonds in this example: we just assume that any two adjacent nodes are automatically connected with each other.
• We are just using the "0" character as a conveniently shaped blob, they are not supposed to indicate that the array element representing the node will actually have the value zero. In our example it will have the value plus or minus one.

0-0-0-0-0      0     0-0            0-0            0-0   
| | | | |      |       |              |              |
0-0-0-0-0      0-0-0   0      0-0-0   0      0   0   0   
| | | | |  ->  |   |   |  ->  |   |   |  ->  |   |   |                 
0-0-0-0-0      0   0-0-0      0   0-0-0      0   0-0-0   
| | | | |      |   |   |      |              |                 
0-0-0-0-0      0-0-0   0      0-0            0-0      

Notice how in the third example the route doubles back on itself. In the third example we have removed one bond to disconnect the top and bottom edges. Also, we don't require that every top node be connected to every bottom node, just one.

Flood-fill can easily tell us if a mesh is connected in this way: we simply go along the top row flood-filling the nodes to one, then go along the bottom row lookign for nodes whose value is one. If we find one it's conected to the top, if we dont find any the msh has become disconnected (or has not yet become connected depending whether we are destroying or growing the mesh).