I need help with the following assignment:

you will use the provided code template to find the Minimum Spanning Tree

of a graph using Kruskal's Algorithm. You will not only implement the algorithm itself, but you

will also implement 3 necessary functions for the union-find abstract data type, which is used to determine whether or not adding a particular edge will make a cycle. There are two python scripts given, "projectUtils.py" and "mst.py". The implementation must be done in "mst.py". We're not supposed to touch "projectUtils.py", and we're not allowed to import any other libraries besides the ones included in the code.

Here's "mst.py" file:

# -*- coding: utf-8 -*- """ mst.py Union find object for kruskal algorithm using adjacency matrix Also known as a Disjoint-set data structure See the text (Dasgupta) """ import argparse import ProjectUtils as util class unionFind: def __init__(self, n): self.pi = [i for i in range(n)] self.rank = [0 for i in range(n)] def areConnected(self, p, q): """ return true if 2 nodes are connected or false if they are not by comparing their roots """ #TODO Your Code Goes Here return None def union(self, u, v): """ build union of 2 components Be sure to maintain self.rank as needed to make sure your algorithm is optimal. """ #TODO Your Code Goes Here (remove pass) pass def find(self, p): """ find the root of the set containing the passed vertex p - Must use path compression! """ #TODO Your Code Goes Here return None def kruskal(G): """ Kruskal algorithm G : graph object """ #Build unionFind Object uf = unionFind(G.numVerts) #Make MST as a set MST = set() #Get list of edges sorted by increasing weight sortedEdges = G.sortedEdges() #Go through edges in sorted order smallest, to largest for e in sortedEdges: #TODO Your Code Goes Here (remove comments if you wish) # use the following line to add an edge to the MST. # You may change it's indentation/scope within the for loop MST.add(util.buildMSTEdge(G,e)) #TODOne - do not modify any other code below this line return MST, uf def main(): """ main """ #DO NOT REMOVE ANY ARGUMENTS FROM THE ARGPARSER BELOW parser = argparse.ArgumentParser(description='Minimum Spanning Tree Coding Quiz') #use this flag, or change the default here to use different graph description files parser.add_argument('-g', '--graphFile', help='File holding graph data in specified format', default='small.txt', dest='graphDataFileName') #use this flag to print the graph and resulting MST parser.add_argument('-p', '--print', help='Print the MSTs?', default=False, dest='printMST') #args for autograder, DO NOT MODIFY ANY OF THESE parser.add_argument('-n', '--sName', help='Student name, used for autograder', default='GT', dest='studentName') parser.add_argument('-a', '--autograde', help='Autograder-called (2) or not (1=default)', type=int, choices=[1, 2], default=1, dest='autograde') args = parser.parse_args() #DO NOT MODIFY ANY OF THE FOLLOWING CODE #Build graph object graph = util.build_MSTBaseGraph(args) #you may print the configuration of the graph -- only effective for graphs with up to 10 vertex #graph.printMe() #Calculate kruskal's alg for MST MST_Kruskal, uf = kruskal(graph) #verify against provided prim's algorithm results util.verify_MSTKruskalResults(args, MST_Kruskal, args.printMST) if __name__ == '__main__': main() 

Here's "projectUtils.py":

##MST #this function will load graph information from file and build the graph structure def build_MSTBaseGraph(args): #file format should be #line 0 : # of verts #line 1 : # of edges #line 2... : vert1 vert2 edgeWT MSTGraphData = readFileDat(args.graphDataFileName) numVerts = int(MSTGraphData[0].strip()) numEdges = int(MSTGraphData[1].strip()) edgeDataAra = [] for i in range(numEdges): line = MSTGraphData[i+2] vals = line.split() v1 = int(vals[0].strip()) v2 = int(vals[1].strip()) wt = float(vals[2].strip()) #print("v1 :{} v2 :{} wt : {} ".format(v1,v2,wt)) edgeDataAra.append([wt,v1,v2]) G = Graph(numVerts, edgeDataAra) return G def print_MSTResults(MST): itr = 0 for E in MST: print("({:4d},{:4d}) {:2.6f} ".format(E[1][0], E[1][1], E[0]), end=" | ") itr += 1 if(itr > 2): itr=0 print("") print(" ") """ build a tuple holding edge weight and edge verts to add to mst """ def buildMSTEdge(G, e): wt = G.edgeWts[e] return (wt, e) def save_MSTRes(args, MST): saveName = "soln_"+args.graphDataFileName strList = [] for E in MST: strDat = "{} {} {}".format(E[1][0],E[1][1],E[0]) strList.append(strDat) writeFileDat(saveName, strList) def load_MSTRes(args): solnName = "soln_"+args.graphDataFileName resDataList = readFileDat(solnName) MST = set() for line in resDataList : vals = line.split() v1 = int(vals[0].strip()) v2 = int(vals[1].strip()) wt = float(vals[2].strip()) MST.add((wt, (v1,v2))) return MST #u def findTotalWeightOfMst(MST): totWt = 0 for E in MST: totWt += E[0] return totWt #used locally def _compareTwoMSTs(MST_1, lbl1, MST_2, lbl2, printMST): wt1 = round(findTotalWeightOfMst(MST_1), 12) wt2 = round(findTotalWeightOfMst(MST_2), 12) if(abs(wt1 - wt2) < 1e-12): print("Correct: {} Weight : {} {} Wt : {} ".format(lbl1, wt1, lbl2, wt2)) return True else: diff12 = MST_1 - MST_2 sizeDiff12 = len(diff12) diff21 = MST_2 - MST_1 sizeDiff21 = len(diff21) print("Incorrect: {} Weight : {} {} Wt : {}".format(lbl1, wt1, lbl2, wt2)) return False """ verifies results of kruskal calculation """ def verify_MSTKruskalResults(args, MST_Kruskal, printMST=False): MST_Correct = load_MSTRes(args) if(printMST): if(len(MST_Kruskal) < 1): print("No Kruskal's Algorithm results found (Empty MST)") else : print("Kruskal's Algorithm results (Edge list of MST) : ") print_MSTResults(MST_Kruskal) print(" ") print("Correct results : ") print_MSTResults(MST_Correct) print(" ") return _compareTwoMSTs(MST_Kruskal,"Kruskal's Result", MST_Correct, "Expected Result", printMST) """ this structure will represent an undirected graph as an adjacency matrix """ class Graph: def __init__(self, numVerts, edgeDataAra): self.numVerts = numVerts self.numEdges = len(edgeDataAra) self.edgeDataAra = edgeDataAra self.edges = set() self.edgeWts = dict() # populate the graph for edge in edgeDataAra: #add edge so that lowest vert is always first if(edge[1] > edge[2]): thisEdge = (edge[2],edge[1]) else : thisEdge = (edge[1],edge[2]) self.edges.add(thisEdge) self.edgeWts[thisEdge] = edge[0] """ returns list of edges sorted in increasing weight """ def sortedEdges(self): sortedEdges = sorted(self.edges, key=lambda e:self.edgeWts[e]) return sortedEdges def buildAdjacencyMat(self): numVerts = self.numVerts graphAdjMat = [[0]*numVerts for _ in range(numVerts)] edgeDataAra = self.edgeDataAra for edge in edgeDataAra: graphAdjMat[edge[1]][edge[2]] = edge[0] graphAdjMat[edge[2]][edge[1]] = edge[0] # use adjacent matrix to represent the graph return graphAdjMat """ for debug purposes """ def printMe(self): print("Graph has :{} vertices and {} edges".format(self.numVerts,self.numEdges)) NumVerts = min(10, self.numVerts) AM = [[0.0 for _ in range(NumVerts)] for _ in range(NumVerts)] for edge in self.edges: a,b = edge if a > NumVerts: continue if b > NumVerts: continue weight = self.edgeWts[edge] AM[a][b] = weight AM[b][a] = weight print(' ', end = ' ') for i in range(NumVerts): print('{0:5d}'.format(i), end = ' ') print() for i, row in enumerate(AM): print('{0:2d}'.format(i), end=' ') for j in row: if j == 0: print(' ', end = ' ') else: print('{0:1.3f}'.format(j),end=' ') print() print() 

Here's a sample text file of the graph to test:

8 16 4 5 0.35 4 7 0.37 5 7 0.28 0 7 0.16 1 5 0.32 0 4 0.38 2 3 0.17 1 7 0.19 0 2 0.26 1 2 0.36 1 3 0.29 2 7 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93 

and here's the solution for the above text file:

2 3 0.17 0 7 0.16 5 7 0.28 2 6 0.4 4 5 0.35 0 2 0.26 1 7 0.19 

You can pass the text file name to the code by using command line argument "-g".