CS21003 Algorithms ICS29003 Algorithms Laboratory |
Autumn 2012, L-T-P: 3-1-0 L-T-P: 0-0-3 |

## Programming Assignment 4

Mr. Contractor's sons have finished furnishing the houses, and it is time for the government of CSA to allocate these houses to suitable families. In CSA, there is a high mountain range. On one side of the range, there is an arid desert, and on its other side, there is a dense forest. People of one tribe inhabit the desert, and people of another tribe live in the forest. Both the tribes are underdeveloped. The government of CSA plans to relocate them in the new furnished houses and provide them with modern amenities.

Although people from each tribe live peacefully among themselves, there is constant quarrel between people of different tribes. For example, the mountain passes are major areas of conflict between the desert-dwellers and the forest-dwellers. Because of economic constraints, the CSA government is forced to let people from both tribes share the same city. Suppose that there are

n_{1}families of desert-dwellers andn_{2}families of forest-dwellers, chosen by the government for relocation in the city. Here,n=n_{1}+n_{2}is the total number of houses in the city.In order to minimize inter-tribe conflicts, the CSA government fixes a safe separation distance δ, and tries to minimize pairs of houses (

i,j) within the distance δ, such thatiis allocated to a desert-dweller family, andjto a forest-dweller family. Finding the smallest possible such pairs appears to be a very difficult computational problem (NP-complete). So, any reasonably good solution is fine with the CSA government. The following greedy algorithm is used to find such a suboptimal solution.

- Start with any allocation of
n_{1}houses to desert-dwellers, and the remainingn_{2}houses to forest-dwellers. Then, run the following loop for refining this allocation gradually.- Locate a house
ufrom Part 1 such that movinguto the other part maximizes the reduction in the conflicting (i,j) pairs of houses. Let this switching decrease the number of conflicting pairs byr. We denote this asr= Gain(u).- Then, choose a house
vfrom Part 2, such that moving this house to Part 1 maximizes the reduction of conflicting (i,j) pairs of houses. Letsdenote the reduction in the conflicting pairs for this choice ofv. Denotes= Gain(v).- The houses
uandvchosen above should not themselves be within the distance δ.- Each of
randsmay be positive, negative, or zero. However, if their sumr+sis positive, then switch Houseuto Part 2 and Housevto Part 1 in order to reduce the number of conflicting pairs of houses (the number of cross edges between the two parts). Since such a switch gives a strictly better solution, this process stops after finitely many (at mostn_{1}n_{2}) iterations.- Break the loop when no further refinement is possible by vertex switches. The parts at this stage are taken as the suboptimal solution. That is, the houses in Part 1 are given to the desert-dwelling families, and the houses in Part 2 to the forest-dwelling families.
Write a program to do the following tasks.

- Read
n_{1},n_{2}and δ from the user.- Generate the locations of the houses randomly within the unit square (assume that the city has size one km by one km).
- Generate an undirected graph
G= (V,E) as follows. The vertices inGare the houses. For two verticesiandj, the edge (i,j) exists if and only if the distance between these two houses is less than the safety margin δ. Store this graph in the adjacency-list form.- Generate an initial partition of the
nnodes, such that Part 1 containsn_{1}vertices and Part 2 contains the remainingn_{2}vertices.- Run the refinement loop on this partition. Stop when no further refinement is possible by vertex switches. Notice that if
uis a vertex in Part 1, then the gain obtained by movinguto Part 2 is the number of neighbors ofuin Part 2 minus the number of its neighbors in Part 1. Likewise, the gain in moving a vertexvfrom Part 2 to Part 1 is the number of neighbors ofvin Part 1 minus the number of its neighbors in Part 2. Verticesuandvare not switched if they are neighbors of one another, because such a switch may lead to an infinite loop.- Print the partition found in this way.
- Demonstrate that the final solution need not be unique. It depends on the choice of the initial partition (and also on the choice of the vertices
uandvin the refinement loop---indeed, any choice with Gain(u) + Gain(v) > 0 would work, that is, you do not have to maximize these gains). Try with different randomly chosen initial partitions, and notice the potential changes in the solution and even in the final numbers of cross edges that we arrive at from different initial partitions.## Sample output

n1 = 25 n2 = 35 delta = 0.1 Houses are located at: (0.3513,0.6496) (0.5777,0.6754) (0.6155,0.9963) (0.0052,0.9712) (0.8958,0.1373) (0.0600,0.6710) (0.9512,0.3586) (0.9652,0.9837) (0.0758,0.7010) (0.5971,0.2942) (0.6828,0.4132) (0.7872,0.4427) (0.5084,0.8581) (0.0335,0.1357) (0.6262,0.0791) (0.3297,0.9775) (0.7287,0.9074) (0.6529,0.3442) (0.9037,0.6580) (0.3154,0.7995) (0.7953,0.3754) (0.4705,0.7465) (0.7340,0.4357) (0.7302,0.8098) (0.1368,0.3272) (0.1040,0.8196) (0.7404,0.8912) (0.2623,0.2489) (0.7493,0.2958) (0.3845,0.3755) (0.3749,0.7142) (0.3530,0.1036) (0.6217,0.0058) (0.4477,0.5254) (0.6638,0.7631) (0.3249,0.4591) (0.1385,0.7954) (0.2056,0.8725) (0.2311,0.9358) (0.6823,0.3678) (0.2631,0.7863) (0.1874,0.0035) (0.6775,0.4497) (0.2524,0.4268) (0.7455,0.6369) (0.8023,0.1204) (0.3511,0.1553) (0.2239,0.9728) (0.1611,0.6717) (0.4982,0.8249) (0.4348,0.8230) (0.2840,0.5733) (0.6184,0.4897) (0.4458,0.8495) (0.4255,0.1281) (0.2174,0.6886) (0.9144,0.4048) (0.6921,0.5919) (0.8545,0.9445) (0.0187,0.6001) Number of cross edges = 21 +++ Switching node 12 to Part 2: Gain = 3 +++ Switching node 26 to Part 1: Gain = 2 Number of cross edges = 16 +++ Switching node 21 to Part 2: Gain = 2 +++ Switching node 30 to Part 1: Gain = 1 Number of cross edges = 13 +++ Switching node 4 to Part 2: Gain = 1 +++ Switching node 32 to Part 1: Gain = 1 Number of cross edges = 11 +++ Switching node 6 to Part 2: Gain = 1 +++ Switching node 34 to Part 1: Gain = 1 Number of cross edges = 9 +++ Switching node 19 to Part 2: Gain = 1 +++ Switching node 39 to Part 1: Gain = 1 Number of cross edges = 7 +++ Switching node 1 to Part 2: Gain = 0 +++ Switching node 28 to Part 1: Gain = 2 Number of cross edges = 5 +++ Switching node 2 to Part 2: Gain = 0 +++ Switching node 42 to Part 1: Gain = 2 Number of cross edges = 3 +++ Switching node 3 to Part 2: Gain = 0 +++ Switching node 52 to Part 1: Gain = 1 Number of cross edges = 2 +++ No further refinement possible Tribe 1 families get the houses: 0 5 7 8 9 10 11 13 14 15 16 17 18 20 22 23 24 26 28 30 32 34 39 42 52 Total number of houses = 25 Tribe 2 families get the houses: 1 2 3 4 6 12 19 21 25 27 29 31 33 35 36 37 38 40 41 43 44 45 46 47 48 49 50 51 53 54 55 56 57 58 59 Total number of houses = 35## Submission Site