3.2 Clustering (Krukal MST using UFS).py

""" 1.Question 1 In this programming problem and the next you'll code up the clustering algorithm from lecture for computing a max-spacing k-clustering. This file (clustering1.txt) describes a distance function (equivalently, a complete graph with edge costs). It has the following format: [number_of_nodes] [edge 1 node 1] [edge 1 node 2] [edge 1 cost] [edge 2 node 1] [edge 2 node 2] [edge 2 cost] ... There is one edge (i,j)(i,j) for each choice of 1≤i self.rank[ry]: self.p[ry] = rx else: self.p[rx] = ry self.rank[ry] += 1 def dataReader(filePath): with open(filePath) as f: data = f.readlines() numNodes = int(data[0]) nodes = [Node(i) for i in range(numNodes + 1)] edges = [] for index in range(1, len(data)): node1ID, node2ID, cost = list(map(int, data[index].split())) nodes[node1ID].connections.append((node2ID, cost)) nodes[node2ID].connections.append((node1ID, cost)) edges.append(Edge(node1ID, node2ID, cost)) return numNodes, nodes, edges def clustering(numClusters, numNodes, nodes, edges): ufs = UFS(numNodes + 1) findRes = False edges.sort(key=lambda item:item.cost) for edge in edges: node1ID, node2ID = edge.nodes if ufs.find(node1ID) != ufs.find(node2ID): if not findRes: ufs.union(node1ID, node2ID) numNodes -= 1 else: return edge.cost if numNodes == numClusters: findRes = True def main(): filePath = "data/clustering1.txt" numNodes, nodes, edges = dataReader(filePath) minimumSpacing = clustering(4, numNodes, nodes, edges) print("Minimum Spacing of 4 clusters: ", minimumSpacing) if __name__ == "__main__": main()