Minimal network | Euler 107

This problem involves a graph algorithm which is known as Kruskal's algorithm which tries to minimize the sum of values associated with vertices in a graph.

Edges are sorted and then added to a list if it does not violate the rule of minimal graph, which has no closed loops. For this the item is checked whether the vertices are already there in the completed vertices.

This is a simple algorithm and is implemented below with python language. This is a link for the input text file.

	import time
	f = open("p107_network.txt","r")
	str = f.read();
	f.close()
	#kruskals algorithm
	lines = str.strip().split("\n")
	discovered = []
	edges = {}
	i = 0
	for x in lines:
	temp = x.split(",")
	for j in range(i):
	if temp[j] != "-" and not((i,j) in edges or (j,i) in edges):
	tempE = sorted([i,j])
	edges[(tempE[0],tempE[1])] = int(temp[j].strip())
	i += 1
	t = time.time()
	mst = 0
	c = 0
	visited = []
	tree = []
	while(len(edges)>0):
	c+=1
	if c==40:
	break
	e = min(edges,key = edges.get)
	tempE = sorted([e[1],e[0]])
	e = (tempE[0],tempE[1])
	if e not in visited:
	visited.append(e)
	#tree.append(e)
	mst += edges[e]
	for e0 in visited:
	for e1 in visited:
	if e0==e1:
	continue
	else:
	if(e0[1] in e1 or e0[0] in e1):
	temp = list(set(e1+e0))
	temp.sort()
	if len(temp) < 3: continue
	e1=(temp[0],temp[1])
	e2=(temp[1],temp[2])
	e3=(temp[0],temp[2])
	if e1 not in visited and e1 in edges:
	visited.append(e1)
	del edges[e1]
	if e2 not in visited and e2 in edges:
	visited.append(e2)
	del edges[e2]
	if e3 not in visited and e3 in edges:
	visited.append(e3)
	del edges[e3]
	del edges[e]
	print mst
	print time.time()-t

view raw euler107.py hosted with ❤ by GitHub