Computational Physics Week 1: Course work

Comments and questions to John Rowe.

Time allocation: seven hours plus remaining in-lab time.

Connectivity of a mesh

We consider an N by N 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

(Notice that there are no explicit bonds in this example: we just assume that any two adjacent nodes are automatically connected with each other.)

If we remove a few nodes the top and bottom edges will eventually become disconnected:

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.

Requirements

To represent and solve this problem we need the following:

1. A way to represent the nodes - this could simply be an integer array of ones for where there is a node and zero where there isn't.
   Class discussion about dealing with edges.

2. A way to remove nodes at 'random'.

3. A way to tell if the top and bottom edges are connected.

Pseudo-random numbers

We will want to remove nodes at 'random' so we will need to be able to generate 'random' numbers to decide which bond is to be broken. (We have briefly seen this before in the wins example program.)

The include file stdlib.h defines the rand() function that returns a pseudo-random integer in the range 0 to RAND_MAX. We can therefore write the following rather poor number to generate a pseudo-random integer in the range 0 to M:

/*  Can you see the problem with this function? */
int
randint(int m) {
  long l =  rand() % m;
  return l;
}

Initialising the pseudo-randomiser

As it stands, rand() always prints out the same pseudo-random sequence every time you run the program. If you don't want this you can initiase it with the srand() function. The classic example is to use the current time as the initialiser:

#include <time.h>

int main() {
  /* Variable declarations */
  srand(time(NULL));

  /* Code */
}

Notice that the time() function is declared in time.h and that srand() is called only once per program.

The program

Do this one stage at a time and test it as you go.

1. Allocate an array for the nodes and initialize the nodes to 1. You may assume a fixed array size.

2. Write a routine to draw a mesh diagram as above. (Don't bother to represent the bonds, just the nodes.)

3. Use the function above to write a routine to remove nodes at random and print the resulting meshes to the screen.

4. Add a test to see if the mesh is top-bottom connected and call it after each removal (ie your main loop will be remove-print-test until the test is negative).

Working out which nodes are connected to the top edge

Once we start talking about whether a node is connected to the top edge we have three possible states for a node:

• Missing.
• Connected to the top row.
• Not (yet) connected to the top row.

(We say not yet connected because our algorithm initially assumes all nodes are not connected to the top.) Thus our array can now have three values, say zero, one or two. Can you think of a good and non-confusing way of specifying which of the three possible array values corresponds to each possible state?

The test function

Your test function will be called inside your main loop, after each disconnection. The steps are:

1. Initialise each non-missing node to 'not yet connected'.

2. Go along the top row connecting each node and its neighbours:
   1. Connect the nodes.
      Class discussion about connecting the nodes.

   2. Write a function to go along the bottom row and see if any is connected, if one is return '1', otherwise return '0'.

   Notice that your test function will have to call at least one other function and possibly more.