using program below. In this python script we define a simple and weighted graph

Question

using program below.

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()

# primsfunctions.py from Weighted_Graph import # kruskals functions.py from Weighted Graph import n This file should store all functions that This file should store all functions that you write which will be needed in the steps of Kruskal's algorithm" you write which will be needed in the steps of Prim's algorithm def c(G, e): def c(G, e): .. # Prims.py import prims functions.py # Kruskalspy import kruskals functions.py This file should implement Prim's This file should implement Kruskal's algorithmm algorithm def Kruskals(textfile):.. Grading Rubric: # MST.py from Prims import Prims from Kruskals import Kruskals Solve correctly the MST for a given graph: 90 its n This file should be your main program Prims or Kruskals (bonus for both) 1. Correct Optimal Cost 60 pts 2. Correct File Structure 20 pts 3. Creative user input and program design/ error checks: 10 pts (textfile, algorithm 'Prims'): if algorithm-'Prims' Write a detailed argument, or proof, for the fact that Prims (or Kruskals) always terminates with a optimal spanning tree: 10 pts return Prims(textfile) else: return Kruskals(textfile)

Explanation / Answer

import heapq

#N = number of vertices
#M = number of edges
N = 14
M = 21
MAX = 1e18

#adjancy matrix
adj = [[MAX if i!=j else 0 for j in range(N)] for i in range(N)]
root = [i for i in range(N)] #for disjoint set
edges = [] #edges
dist = [MAX for i in range(N)] #for prim
visited = [False for i in range(N)]
ans_prim = 0
ans_kruskal = 0
mst_edges = []

#DISJOINT SET DATASTRUCTURE for cycle checking in kruskal
def find_root(i):
    while i!=root[i]:
        root[i] = find_root(root[i])
        i = root[i]
    return i

def union(i,j):
    root_i = find_root(i)
    root_j = find_root(j)
    if root_i == root_j:
        return False
  
    if root_i < root_j:
        root[root_j] = root_i
    else:
        root[root_i] = root_j
    return True

#reading from text file , file contains edges in format u v w
with open('spanning.txt') as f:
    for row in f:
        u,v,w = map(int,row.strip().split())
        adj[u][v] = w
        adj[v][u] = w
        edges.append([w,u,v])
      

#PRIMS ALGO

dist[0] = 0
l = [[0,0]]
parent = [-1 for i in range(N)]

heapq.heapify(l) #maintaing heap for lowering complexity
while len(l)>0:
    current = heapq.heappop(l)
    u = current[1]
    if visited[u]: #if already visited continue
        continue
    visited[u] = True
    ans_prim += current[0]
  
    #check for adjacent vertices if they are reachable in smaller values than before
    for v in range(N):
        if not visited[v] and dist[v] > adj[u][v]:
            parent[v] = u
            dist[v] = adj[u][v]
            heapq.heappush(l,[dist[v],v])

print('minimum spanning tree using prims algo:')
print(ans_prim)

#KRUSKAL ALGO

heapq.heapify(edges)
while len(edges)>0:
    current = heapq.heappop(edges)
    u = current[1]
    v = current[2]
    w = current[0]
    #if not forming cycle then add the edge
    if union(u,v):
        mst_edges.append([u,v,w])
        ans_kruskal += w

print('minimum spanning tree using kruskal algo:')
print(ans_kruskal)

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.