Programming Assignment 9

Thanks to your programming assistance, desert-dwellers and forest-dwellers are living happily in the newly built city. The government of CSA plans to supply cooking gas connections to all the houses in the city. The gas agency plans to minimize the length of pipes while maintaining connectivity to every house. This means that we now need to solve an instance of the Euclidean minimum spanning tree problem.

The brute-force approach is to compute the distances between all pairs of houses, and run any MST algorithm on this fully connected graph. However, there are Θ(n²) edges in the graph (where n is the number of houses). This leads to Ω(n²) running time. If we look at the problem geometrically, we can arrive at O(n log n)-time algorithms. The basic observation is that if two houses are distant from one another, it is likely that the edge connecting these two houses will not be present in the MST. In other words, it suffices to look at only the neighborhood of each house, thereby restricting the connectivity graph to have only O(n) edges. One possibility is to use the Delaunay triangulation of the given points. This is, however, a topic that is outside the scope of this course. In your Algorithms II course, you would study Voronoi diagrams and Delaunay triangulation.

For the time being, you implement Rajasekaran's randomized algorithm which has an expected running time of O(n log n), assuming that the houses are uniformly randomly distributed in a square. This algorithm generates subgraphs with gradually growing neighborhood size. Such a subgraph need not be connected. However, a minimum spanning forest of the subgraph can be computed using any MST algorithm. When there is only one tree in the forest, we have obtained the desired Euclidean MST.

Write a program to do the following.

• Read the number n of houses from the user. Maintain a two-dimensional hash table of n randomly generated points in the unit square (as in Assignment 8). You need this two-dimensional hash table for implementing the EMST algorithm.
• Design a data structure to store a graph in the adjacency-list format.
• Write Kruskal's algorithm with path compression to compute the minimum spanning forest of a graph. Use a min-heap (instead of sorting the edges with respect to their weights, as implemented in the notes).
• Implement Rajasekaran's algorithm EMST. This algorithm should invoke your implementation of Kruskal's algorithm as many times as needed. You may take C₁ = 1.5, C₂ = 1.1, and natural logarithm in the formula for r.

Sample output

   n = 10000000

   +++ First phase of EMST...
       No of edges in G is 35321066
       No of edges in T is 9985319
       Number of trees = 14681

   +++ Second phase of EMST...
       Largest tree is of size = 9969720
       No of edges in G is 49819152
       No of edges in T is 9999997
       Number of trees = 3

   +++ Second phase of EMST...
       Largest tree is of size = 9999998
       No of edges in G is 49819162
       No of edges in T is 9999999
       Number of trees = 1

Submission Site

---

Back | Home