Hi, I\'m trying to program kruskal\'s algorithm in python but I don\'t understan

Question

Hi,

I'm trying to program kruskal's algorithm in python but I don't understand how to continue from where I am. Here is what I have so far:

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

#load city coordinates
A = np.loadtxt("Cities.data.txt")
#finding "weight" function
def distance(x, y):
return sqrt((x[0] - y[0])**2 + (x[1] - y[1])**2)

#appending edges
edges = []
for i in range(len(A)):
for j in range(len(A)):
if i < j:
edges.append((i, j))

I need help with creating my def MST(edges, nodes) but I don't know where I should start. A contains a list of city coordinates and here is what I have for calculating each weight of the 128 cities in A:

for x in range(len(A)-1):
distance(A[x], A[x+1])

How can I code the MST in python to take these edges and weights (distances)?

Explanation / Answer

#======================================================================= # Kruskal MST #======================================================================= def kruskal_mst(G): """Return a minimum spanning tree using kruskal's algorithm""" # sort the list of edges in G by their length Edges = [(u, v, G[u][v]['length']) for u,v in G.edges()] Edges.sort(cmp=lambda x,y: cmp(x[2],y[2])) UF = make_union_find(G.nodes()) # union-find data structure # for edges in increasing weight mst = [] # list of edges in the mst for u,v,d in Edges: setu = find(UF, u) setv = find(UF, v) # if u,v are in different components if setu != setv: mst.append((u,v)) union(UF, setu, setv) snapshot_kruskal(G, mst) return mst #======================================================================= # MST Testing and Visualization Code #======================================================================= def dist(xy1, xy2): """Euclidean distance""" return math.sqrt((xy1[0] - xy2[0])**2 + (xy1[1] - xy2[1])**2) def random_mst_graph(n, k=4): """Make a random graph by choosing n nodes in the [0,1.0] by [0,1] square. The 'length' of each edge is the euclidean distance between them. Edges connect to the k nearest neighbors of each node.""" # build random nodes G = nx.Graph() for i in xrange(n): G.add_node(i, pos=(0.9*random.random()+0.05,0.9*random.random()+0.05)) # add edges for i in G.nodes(): near = [(u, dist(G.node[i]['pos'],G.node[u]['pos'])) for u in G.nodes() if u != i] near.sort(cmp=lambda x,y: cmp(x[1],y[1])) for u,d in near[0:k]: G.add_edge(i, u, length=d) # ensure it's connected CC = nx.connected_components(G) for i in xrange(len(CC)-1): u = random.choice(CC[i]) v = random.choice(CC[i+1]) G.add_edge(u,v, length=dist(G.node[u]['pos'], G.node[v]['pos'])) return G def draw_mst_graph(G, T={}, outfile=None): """Draw the MST graph, highlight edges given by the MST parent dictionary T. T should be in the same format as returned by prim_mst().""" import matplotlib.pyplot as plt # construct the attributes for the edges pos = dict((u,G.node[u]['pos']) for u in G.nodes()) labels = dict((u,str(u)) for u in G.nodes()) colors = [] width = [] for u,v in G.edges(): if isinstance(T, dict): inmst = (u in T and v == T[u]) or (v in T and u == T[v]) elif isinstance(T, nx.Graph): inmst = T.has_edge(u,v) colors.append(1 if inmst else 255) width.append(5 if inmst else 1) # draw it plt.figure(facecolor="w", dpi=80) plt.margins(0,0) plt.xticks([]) plt.yticks([]) plt.ylim(0.0,1.0) plt.xlim(0.0,1.0) plt.box(False) nx.draw_networkx(G, labels=labels, node_size = 500, node_color = "white", edge_color = colors, width=width, pos=pos) if outfile is not None: plt.savefig(outfile, format="pdf", dpi=150, bbox_inches='tight', pad_inches=0.0) plt.close() else: plt.show() def snapshot_kruskal(G, edges, pdf=True): T = nx.Graph() for u,v in edges: T.add_edge(u,v) draw_mst_graph(G, T, pdffile if pdf else None) def snapshot_mst(G, parent): tree = dict((u,parent[u]) for u in G.nodes() if G.node[u]['distto'] == float("-inf") and u in parent) draw_mst_graph(G, tree, pdffile) def test_mst(): """Draw the MST for a random graph.""" global pdffile pdffile = start_pdf("mst.pdf") N = random_mst_graph(20) draw_mst_graph(N, prim_mst(N)) close_pdf(pdffile) def test_kruskal(): """Draw the MST for a random graph.""" global pdffile pdffile = start_pdf("kruskal.pdf") N = random_mst_graph(20) snapshot_kruskal(N, kruskal_mst(N), False) close_pdf(pdffile) def start_pdf(outfile): from matplotlib.backends.backend_pdf import PdfPages pp = PdfPages(outfile) return pp def close_pdf(pp): pp.close() def main(): import sys if len(sys.argv) >= 2: if sys.argv[1] == "heap": test_heap() if sys.argv[1] == "mst": test_mst() if sys.argv[1] == "kruskal": test_kruskal() else: print "Usage: mstprim.py [heap|mst|kruskal]" if __name__ == "__main__": main()

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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