"""
Cis 435 - Algorithms
Implementation of MST-Prim in Python
Scott Hurring - http://hurring.com/code/python/mst_prim/

Changelog:
	v0.1a - Dec 09, 2004
	Initial release
"""

import sys, Numeric

# Ajacency matrix from p.571
A = [ [0, 4, 0, 0, 0, 0, 0, 8, 0], \
      [4, 0, 8, 0, 0, 0, 0, 11,0], \
      [0, 8, 0, 7, 0, 4, 0, 0, 2], \
      [0, 0, 7, 0, 9, 14,0, 0, 0], \
      [0, 0, 0, 9, 0, 10,0, 0, 0], \
      [0, 0, 4, 14,10,0, 2, 0, 0], \
      [0, 0, 0, 0, 0, 2, 0, 1, 6], \
      [8, 11,0, 0, 0, 0, 1, 0, 7], \
      [0, 0, 2, 0, 0, 0, 6, 7, 0], \
];

class MST_Prim:
	INFINITY = pow(2, 32)
	vertices = 0
	
	def __init__(self, A, r):
		"""
		Prepare the inputs for mst_prime
		"""
		self.vertices = A[0].__len__();
		self.init_adjacency(A)
		self.remove_route(A, r)
	
	def mst_prim(self, A, w, path=[]):
		"""
		'A' is the adjacency matrix
		'w' is the list of all connected vertices (in order of discovery)
		'path' is a list of tuples showing (from, to)
		"""
		# Stop when we've added all nodes to the path
		if (w.__len__() == self.vertices):
			return (A, w, path)
		# Find minimum path coming OUT of the known vertexes			
		(vfrom, vto, vcost) = self.find_min(A, w)
		
		# Mark down this vertex as being a part of the MST path
		w.append(vto)
		path.append((vfrom,vto))
		
		self.remove_route(A, vto)
		
		return self.mst_prim(A, w, path)
	
	
	def init_adjacency(self, A):
		"""
		Initialize adjacency list - set 0 = INFINITY
		"""
		for i in range(0, self.vertices):
			for j in range(0, self.vertices):
				if A[i][j] == 0:
					A[i][j] = pow(2,32)
		
	def remove_route(self, A, v):
		"""
		Once we've added a node to our path, set all routes
		to this node equal to INFINITY - to prevent loops
		"""
		for i in range(0, self.vertices):
			A[i][v] = self.INFINITY
	
	def find_min(self, A, w):
		"""
		Find the cheapest connection we can possibly make,
		given the partially-built MST 'w'
		'vfrom' vertex to connect from
		'vto' vertex to connect to
		'vcost' cost of connection
		"""
		vcost = self.INFINITY
		vto = vfrom = -1
		for v in w:
			# Get array offset of minimum  of this vertex
			i = Numeric.argmin(A[v])
			if A[v][i] < vcost:
				vcost = A[v][i]
				vto = i
				vfrom = v
		return (vfrom, vto, vcost)

# Execute the MST Prim algorithm on 'A', starting at node 0
r = 0
m = MST_Prim(A, r)
(A, w, path) = m.mst_prim(A, [r])
print "Vertices:"
for pair in path:
	print chr(pair[0]+97) ,"->", chr(pair[1]+97)