In this project, you will create a Python program that implements Prim's algorithm to find a Minimal Weight Spanning tree for a weighted graph G. Attached to this assignment, you will find 3 files

1. Weighted_Graph.py : A class to create a weighted graph object. 2. test.txt : A text file defining a weighted graph 3. Prim_Template.py: A template of the python program to implement Prim's algorithm.

Update Prim_Template.py with the python code to create a weighted graph object from test.txt , impletment Prim's algorithm to find a minimal spanning tree for weighted graph, and display the spanning tree.

WEIGHTED_GRAPH-----------------------------------------------------------------------------------------------

#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ Discrete Mathematical Structures

In this python script we define a simple and weighted graph class object. This object should be used to write Prim's and Kruskal's algorithms. """

import numpy as np import networkx as nx import matplotlib.pyplot as plt

class Weighted_Graph(object): def __init__(self, edge_list_file): """ Set the edge list directory address """ self.edge_list_file = edge_list_file def edge_dict(self): """ Reads in the edge list from the provided directory address and creates a edge dictionary where the keys are the edges and values are the corresponding edge weights. In particular, to access the value of edge (a,b), simply type edge_dict[(a,b)]""" edge_dict = dict() # dict()=empty dictionary edge_list = np.loadtxt(self.edge_list_file, int) # numpy 2-d array for row in edge_list: edge_dict[(row[0], row[1])] = row[2] # Assign keys and values return edge_dict def edge_set(self): """ Returns the set of edges """ return set(self.edge_dict().keys()) def vertex_set(self): """ Returns the set of vertices """ vertex_set = set() # set()= the empty set for e in self.edge_set(): for v in e: vertex_set.add(v) return vertex_set def draw_graph(self): """ This function is used to visualize your weighted graph. The functions used inside are from the networkx library. """ G = nx.read_edgelist(self.edge_list_file, nodetype=int, data=(('weight',float),)) e=[(u,v) for (u,v,d) in G.edges(data=True)] pos=nx.spring_layout(G) # positions for all nodes nx.draw_networkx_nodes(G,pos,node_size=250) # nodes nx.draw_networkx_edges(G,pos,edgelist=e,width=1) # edges # labels labels = nx.get_edge_attributes(G,'weight') nx.draw_networkx_labels(G,pos,font_size=10,font_family='sans-serif') nx.draw_networkx_edge_labels(G,pos,edge_labels=labels) plt.axis('off') plt.show() def draw_subgraph(self, H): """ This function is used to visualize your weighted graph. The functions used inside are from the networkx library. """ G = nx.read_edgelist(self.edge_list_file, nodetype=int, data=(('weight',float),)) e1=[(u,v) for (u,v,d) in G.edges(data=True)] e2= [e for e in e1 if e in H[1]] v1 =[v for v in H[0]] pos=nx.spring_layout(G) # positions for all nodes nx.draw_networkx_nodes(G,pos,node_size=250) # nodes nx.draw_networkx_nodes(G,pos, nodelist = v1,node_size=400) nx.draw_networkx_edges(G,pos,edgelist=e1,width=1) # edges nx.draw_networkx_edges(G,pos,edgelist=e2, color = 'red' ,width=5) # labels labels = nx.get_edge_attributes(G,'weight') nx.draw_networkx_labels(G,pos,font_size=10,font_family='sans-serif') nx.draw_networkx_edge_labels(G,pos,edge_labels=labels) plt.axis('off') plt.show()

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

PRIM TEMPLATE

''' import Weighted_Graph '''

''' Use Prim's algorithm to find a MST for the graph G ''' def prim(G): ''' Initialize tree T with a single vertex and no edges '''

''' while the vertex set of T is smaller than the vertex set of G, find the edge e with minimum weight so that T+e is a tree. Then update T = T+e '''

''' return T '''

''' return the edge e from graph G with minimum weight where T+e is a tree ''' def minValidEdge(G,T): ''' get a set all edges e in G where T+e is a tree'''

''' initialize minEdge to be a random edge in valid '''

''' check all edges e in valid. if the weight of e is less than the weight of minEdge, update minEdge = e '''

''' return minEdge'''

''' return the weight of an edge in a weighted graph G ''' def weight(e,G):

''' return the set of all edges e from G where T+e is a tree and e is not already an edge of T''' def validEdges(G,T): ''' get a set incident of all edges in G incident with T''' ''' initialize an empty set valid ''' ''' check all edges e in incident. if T+e is a tree, add e to valid'''

''' return validEdges '''

''' return the set of all edges from graph G that are incident with tree T''' def incidentEdges(G,T): ''' initialize an empty set incident ''' ''' for every vertex v in T check all edges e in G. if v is an endpoint of e, add e to incident'''

''' return indicent'''

''' initialize the weighted graph G from the file test.txt. Find a MST for G using prim(). display T (the MST) '''

if __name__ == "__main__":

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Test.txt : (the Text file should just a .txt containing these numbers below)

0 1 2 0 2 3 1 3 2 1 4 4 2 3 11 2 5 2 3 4 10 4 5 3 4 6 4 5 6 2