"""
By : Jad Saklawi
     
To run type : python main.py graphFile

Files included :
graph : Contains graph from page 571
"""

import sys
infinity = pow(2,32)

def mst_prim(G, r):
    for u in G.keys():
        G[u].key = infinity
        G[u].pie = None
        
    G[r].key = 0

    Q = Heap()
    for u in G.keys():
        Q.add(G[u])
    
    while not Q.empty():
        u = Q.extract_min()
        for v in u.adj:
            if Q.contains(v) and u.weight[v] < v.key:
                v.pie = u
                Q.decrease_key(v, u.weight[v])

class Heap:
    "Minimal heap implementation"
    def __init__(self):
        self.data = []
    def min_element(self,data, element):
        for i in range(0,len(data)):
            if element.key < data[i].key:
                return i
        return None
    def add(self, element):
        ret = self.min_element(self.data, element)
        if ret == None:
            self.data.append(element)
        else:
            self.data.insert(ret, element)
    def empty(self):
        if self.data == []:
            return True
        return False
    def extract_min(self):
        ret = self.data[0]
        del self.data[0]
        return ret
    def contains(self,element):
        for i in self.data:
            if element == i:
                return True
        return False
    def decrease_key(self, element, key):
        for i in range(0,len(self.data)):
            if element == self.data[i]:
                break
        del self.data[i]
        element.key = key
        self.add(element)

class Node:
    "Class to encapsulate Graph nodes."
    def __init__(self,label):
        self.label = label
        self.adj = []
        self.weight = dict()
    def add_edge(self,vertex, weight):
        self.adj.append(vertex)
        self.weight[vertex] = int(weight)

def loadGraph(fname):
    "Loads graph from file. No syntax checking... file should be in corrrect format"
    f = open(fname,'r')
    l = f.readlines()
    f.close()
    graph = dict()
    for i in l:
        label = ((i.split())[0]).split(":")[0] 
        graph[label] = Node(label)
    for i in l:
        tmp = i.split()
        label = tmp[0].split(":")[0]
        del tmp[0]
        for j in tmp:
            k = j.split(',')[0]
            edge = k.split('.')
            graph[label].add_edge(graph[edge[0]], int(edge[1]))
    return graph

def help():
    print "Usage python prim.py graphFile"
    print "Make sure file is of correct format. See sample file"

try:
    graphFile = sys.argv[1]
    G = loadGraph(graphFile)
    mst_prim(G, 'a')

    weight = 0
    for i in G.keys():
        if G[i].pie != None:
            print  G[i].pie.label, "->", i
            weight = weight + G[i].weight[G[i].pie]
        
    print "Tree weight is :", weight
except:
    help()