#!/usr/bin/env python
#Author: Shriphani Palakodety
#Mail: spalakod@purdue.edu

# An implementation of Kruskal's algorithm
# We define a simple graph here

import heapq
#from disjoint_set1 import *  #choose implementation at will
from disjoint_set2 import *

class Vertex:
	def __init__(self, value):
		self.value = value

	def __str__(self):
		return self.value

class Edge:
	def __init__(self, vertex1, vertex2, weight):
		self.vertex1 = vertex1
		self.vertex2 = vertex2
		self.weight = weight
	
	def __str__(self):
		s = "Connects: " + str(self.vertex1) + " and " + str(self.vertex2) + "\tWeight: " + str(self.weight)
		return s
		
class Graph:
	def __init__(self, V, E):
		self.V = V
		self.E = E


# -------------------------------------------------------------------- #
#                   Next, there is Kruskal's Algorithm.  	       #
# -------------------------------------------------------------------- #

# heapq is a module that allows a priority queue to be represented using
# an array

def kruskal(G):
	heap = []
	
	for edge in G.E:
		heapq.heappush(heap, (edge.weight, edge))
	
	T = []  #this contains all the edges in the tree
	
	# run makeset on all the vertices
	
	for vertex in G.V:
		MakeSet(vertex)
	
	while heap:
		min_edge = heapq.heappop(heap)[1]
		if FindSet(min_edge.vertex1) is not FindSet(min_edge.vertex2):
			# perform a union and add this edge to the Tree
			T.append(min_edge)
			Union(min_edge.vertex1, min_edge.vertex2)
	return T

if __name__ == "__main__":
	# -------------------------------------------------------------------- #
	# I plan to use this graph with vertices [a, b, c, d, e, f] and some   #
	#                    edges I randomly thought of		       #
	# -------------------------------------------------------------------- #
	
	characters = ['a', 'b', 'c', 'd', 'e']
	
	vertices = []
	edges = []
	
	for char in characters:
		vertices.append(Vertex(char))
	
	i = 0
	
	for vertex1 in vertices:
		for vertex2 in vertices:
			edges.append(Edge(vertex1, vertex2, i))
			i += 1
	
	G = Graph(vertices, edges)
	
	T = kruskal(G)
	
	for edge in T:
		print edge