In this problem you will need to implement Kruskals algorithm to find the minimal spanning tree of a graph. When you finish your implementation you will need to run in on an input graph I am giving to you in file graph_example.py.

I am giving you for this homework two files :

1-graph_example.py has a graph example using networkx. This will get you started using the networkx library. We do not need much beyond knowing how to create a graph, how to add a node and edge to that graph. In this file I am loading a graph example that comes with the package and then list its nodes and edges. I then assigned a weight to the edges of that graph. If you run that file you will see that it prints to you the list of nodes, list of edges and their weights.

2- The second file unionfind.py is a simple implementation for union-find data structure. You will need this file in order to easily implement the Kruskals algorithm

graph_example.py

import networkx as nx from unionfind import * # Load a graph example from networkx

graph=nx.house_x_graph()

print("The nodes of the graph are given by the list : ")

print(graph.nodes())

print("The edges of the graph are given by the list : ")

print(graph.edges())

# here we are giving weights to the edges initweight=1 for edge in graph.edges(): graph.add_edge(edge[0], edge[1], weight=initweight) initweight=initweight+1

# check the weights of the edges: for edge in graph.edges(): a=edge[0] b=edge[1] print("edge "+str(edge)+" has weight " + str(graph[a][b]['weight']) ) # now you will need to calculate the minimal spanning tree for the graph above.

# Implement Kruskal algorothm and run it on the above graph example and record your result.

unionfind.py

class UnionFind: def __init__(self): '''\ Create an empty union find data structure.''' self.num_weights = {} self.parent_pointers = {} self.num_to_objects = {} self.objects_to_num = {} self.__repr__ = self.__str__ def insert_objects(self, objects): '''\ Insert a sequence of objects into the structure. All must be Python hashable.''' for object in objects: self.find(object); def find(self, object): '''\ Find the root of the set that an object is in. If the object was not known, will make it known, and it becomes its own set. Object must be Python hashable.''' if not object in self.objects_to_num: obj_num = len(self.objects_to_num) self.num_weights[obj_num] = 1 self.objects_to_num[object] = obj_num self.num_to_objects[obj_num] = object self.parent_pointers[obj_num] = obj_num return object stk = [self.objects_to_num[object]] par = self.parent_pointers[stk[-1]] while par != stk[-1]: stk.append(par) par = self.parent_pointers[par] for i in stk: self.parent_pointers[i] = par return self.num_to_objects[par] def union(self, object1, object2): '''\ Combine the sets that contain the two objects given. Both objects must be Python hashable. If either or both objects are unknown, will make them known, and combine them.''' o1p = self.find(object1) o2p = self.find(object2) if o1p != o2p: on1 = self.objects_to_num[o1p] on2 = self.objects_to_num[o2p] w1 = self.num_weights[on1] w2 = self.num_weights[on2] if w1 < w2: o1p, o2p, on1, on2, w1, w2 = o2p, o1p, on2, on1, w2, w1 self.num_weights[on1] = w1+w2 del self.num_weights[on2] self.parent_pointers[on2] = on1

kruskalsalgorithm.py

from unionfind import * import networkx as nx

class kruskalsalgorithm(): def __init__(self,inputgraph): self.original_graph=inputgraph self.tree=nx.Graph()

# uncomment the following function and start your implementation as described in lecture 2 def spanningtree(self):