cp2.5

# -*- coding: utf-8 -*-
"""
Created on Tue Apr 15 12:18:41 2014

@author: Administrator
"""
import numpy as np

def bigraph(G):
    head, edge = G
    color = np.zeros_like(head)
    def dfs(knot):
        nedge = head[knot]
        while nedge != -1:
            nknot = edge[nedge]['to']
            if color[nknot] == 0:
                color[nknot] = - color[knot]
                return dfs(nknot)
            elif color[nknot] == color[knot]:
                return False
            nedge = edge[nedge]['next']
        return True
    color[0] = 1
    return dfs(0)
    
def bellman(G, s):
    head, edge = G
    p = np.empty_like(head)
    dist = np.empty(len(head))
    dist.fill(np.inf)
    dist[s] = 0
    for _ in xrange(len(head) - 1):
        for knot, nedge in enumerate(head):
            while nedge != -1:
                nknot = edge[nedge]['to']
                if dist[nknot] > dist[knot] + edge[nedge]['w']:
                    dist[nknot] = dist[knot] + edge[nedge]['w']
                    p[nknot] = knot
                nedge = edge[nedge]['next']
    return dist, p
    
import heapq
def dijkstra(G, s):
    head, edge = G
    p = np.empty_like(head)
    dist = np.empty(len(head))
    dist.fill(np.inf)
    dist[s] = 0
    deque = [(0, s)]
    while len(deque):
        d, knot = heapq.heappop(deque)
        if d != dist[knot]: continue
        nedge = head[knot]
        while nedge != -1:
            nknot = edge[nedge]['to']
            if dist[nknot] > dist[knot] + edge[nedge]['w']:
                dist[nknot] = dist[knot] + edge[nedge]['w']
                p[nknot] = knot
                heapq.heappush(deque, (dist[nknot], nknot))
            nedge = edge[nedge]['next']
    return dist, p
    
def floyd(G):
    n = len(G)
    p = np.empty((n, n), dtype=int)
    for k in xrange(n):
        for i in xrange(n):
            for j in xrange(n):
                if G[i,j] > G[i,k] + G[k,j]:
                    G[i,j] = G[i,k] + G[k,j]
                    p[i,j] = k
    return G, p
    
def prim(G):
    head, edge = G
    n = len(head)
    p = np.zeros_like(head)
    used = np.empty(n, dtype=bool)
    used.fill(False)
    crtmin = np.empty(n, dtype=float)
    crtmin.fill(np.inf)
    im = 0
    used[im] = True
    for _ in xrange(n-1):
        nedge = head[im]
        while nedge != -1:
            nknot = edge[nedge]['to']
            if not used[nknot] and crtmin[nknot] > edge[nedge]['w']:
                crtmin[nknot] = edge[nedge]['w']
                p[nknot] = im
            nedge = edge[nedge]['next']
        m = np.inf
        for i, ud in enumerate(used):
            if not ud and crtmin[i] < m:
                m, im = crtmin[i], i
        used[im] = True
    return p
        
        
                
    
if __name__ == '__main__':
#    def init():
#        n, m = input('n=?, m=?  ')
#        head = np.empty(n, dtype=int)
#        head.fill(-1)
#        EdgeNode = np.dtype({'names':['to','w','next'], 
#                             'formats':[int,float,int]}, align=True)
#        edge = np.empty(2*m, EdgeNode)
#        for k in xrange(m):
#            i, j, w = input('i=?, j=?, w=?  ')
#            edge[k]['to'] = j
#            edge[k]['w'] = w
#            edge[k]['next'] = head[i]
#            head[i] = k
#            
#            edge[m+k]['to'] = i
#            edge[m+k]['w'] = w
#            edge[m+k]['next'] = head[j]
#            head[j] = m+k
#        return head, edge
##    
#    G = init()
#    G = (np.array([ 1,  5,  4,  6,  8,  9, 19]),
#         np.array([(1, 2.0, -1), (2, 5.0, 0), (2, 4.0, 10), (3, 6.0, 2), (3, 2.0, 12),
#                   (4, 10.0, 3), (5, 1.0, 14), (5, 3.0, 15), (6, 5.0, 7), (6, 9.0, 17),
#                   (0, 2.0, -1), (0, 5.0, -1), (1, 4.0, 11), (1, 6.0, -1),
#                   (2, 2.0, 13), (1, 10.0, -1), (3, 1.0, -1), (4, 3.0, 16),
#                   (4, 5.0, -1), (5, 9.0, 18)], 
#                  dtype={'names':['to','w','next'], 'formats':['<i4','<f8','<i4'], 'offsets':[0,8,16], 'itemsize':24, 'aligned':True}))
#
#    print bellman(G, 0)

#    print bigraph(G)

#    print dijkstra(G, 0)
    G = (np.array([ 0,  3,  4,  8,  7, 17, 15]),
         np.array([(2, 1.0, -1), (2, 2.0, -1), (3, 3.0, 10), (4, 10.0, 1), (5, 7.0, 2),
                   (6, 5.0, 11), (6, 8.0, 13), (5, 5.0, 12), (5, 2.0, 5), (0, 1.0, -1),
                   (1, 2.0, 9), (2, 3.0, -1), (1, 10.0, -1), (2, 7.0, -1),
                   (3, 5.0, -1), (5, 8.0, 14), (4, 5.0, 6), (3, 2.0, 16)], 
                  dtype={'names':['to','w','next'], 'formats':['<i4','<f8','<i4'], 'offsets':[0,8,16], 'itemsize':24, 'aligned':True}))

    print prim(G)