Programming Assignment 4: Supplement

Make a visual display of the change, with iterations in the greedy loop, of the allocation of houses to desert-dwellers and forest-dwellers. The simplest visual demonstration is text-based. Fix a maximum display size suitable for viewing in the full-screen (or maximized) mode. Suppose that this size is 100 × 100. Break the 1km × 1km square into a two-dimensional 100 × 100 grid of cells. For each house, find the cell to which this house belongs. If this house is allocated to a desert-dwelling family, write D in that cell. If this house is allocated to a forest-dwelling family, write F in that cell. (You may use any other characters for distingushing these two categories.) If a cell is not occupied by any house, let it contain a space symbol. Printing the 100 × 100 array of cells gives a visual image of the current allocation. Of course, because of poor resolution in a text-based display, a cell may contain two (or more) houses. You may ignore this phenomenon suitably. Indeed, if you restrict the number of houses to a few hundreds, such collisions are not expected to be frequent.

Each refining iteration of the loop, swaps a D with an F in the two-dimensional array. Keep on printing the two-dimensional array after each iteration. After the loop terminates, observe how the symbols D and F are arranged in the two-dimensional grid.

If you desire, and have the technical know-how, you may prepare a graphical visualization as well. For example, I have prepared this animation in order to demonstrate the working of the greedy algorithn. I have taken n₁ = 200 and n₂ = 300 (that is, two hundred desert-dweller families and three hundred forest-dweller families). Houses belonging to desert-dwellers are shown as red inverted triangles (it is quite hot in the desert), whereas those belonging to forest-dwellers are shown as green triangles (what other color can match a forest?). In each iteration, a House u and a House v are selected for swapping of allocation types. These houses are highlighted in the animation by circles. The outer circles indicate the conflict zones.

Preparation of such an animation takes quite some effort, and use of many utilities. I generated each individual plot by gnuplot. For example, the following lines read the coordinates of desert- and forest-dweller houses in the 59-th (not exactly) iteration from the two files A0059.dat and B0059.dat, and generate an image file C0059.jpg that shows the current allocation.

   set terminal jpeg size 1280,960
   set output "C0059.jpg"
   set key off
   set xrange [0:1]; set yrange [0:1]
   set xtics 0.1; set ytics 0.1
   set object circle at 0.237965,0.702096 size 0.02 back fc rgb "yellow" fs solid 0.6
   set object circle at 0.436236,0.817451 size 0.02 back fc rgb "cyan" fs solid 0.6
   set object circle at 0.237965,0.702096 size 0.1 back fc rgb "yellow" lw 3
   set object circle at 0.436236,0.817451 size 0.1 back fc rgb "cyan" lw 3
   plot "A0059.dat" pt 9 lc 6 ps 2, "B0059.dat" pt 11 lc 2 ps 2

If you have all these images, you can run an image viewer in the slideshow mode in order to see the changes going on in the allocation. Joining these images to a single video file is an involved task. I used many utilities like imagemagick (for image resizing and joining), jasper (for getting image sizes), mjpeg (for creating an intermediate video), transcode (for generating the final avi file), and perl (for scripting).

A potentially easier way to create such animations is writing Java applets.

See the animation

This supplement is not meant for submission.

---

Back | Home