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₁ families of desert-dwellers and n₂ families of forest-dwellers, chosen by the government for relocation in the city. Here, n = n₁ + n₂ 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 that i is allocated to a desert-dweller family, and j to 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₁ houses to desert-dwellers, and the remaining n₂ houses to forest-dwellers. Then, run the following loop for refining this allocation gradually.
• Locate a house u from Part 1 such that moving u to the other part maximizes the reduction in the conflicting (i,j) pairs of houses. Let this switching decrease the number of conflicting pairs by r. We denote this as r = Gain(u).
• Then, choose a house v from Part 2, such that moving this house to Part 1 maximizes the reduction of conflicting (i,j) pairs of houses. Let s denote the reduction in the conflicting pairs for this choice of v. Denote s = Gain(v).
• The houses u and v chosen above should not themselves be within the distance δ.
• Each of r and s may be positive, negative, or zero. However, if their sum r + s is positive, then switch House u to Part 2 and House v to 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 most n₁n₂) 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₁, n₂ 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 in G are the houses. For two vertices i and j, 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 n nodes, such that Part 1 contains n₁ vertices and Part 2 contains the remaining n₂ vertices.
• Run the refinement loop on this partition. Stop when no further refinement is possible by vertex switches. Notice that if u is a vertex in Part 1, then the gain obtained by moving u to Part 2 is the number of neighbors of u in Part 2 minus the number of its neighbors in Part 1. Likewise, the gain in moving a vertex v from Part 2 to Part 1 is the number of neighbors of v in Part 1 minus the number of its neighbors in Part 2. Vertices u and v are 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 u and v in 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

---

Back | Home