import tkinter
import random
import math
import random

size = 8
height = 550
width = 600

class Point:
    X = 0
    Y = 0

Pos = []
Network = []

def distance(a, b):
    return math.sqrt((a.X - b.X) ** 2 + (a.Y - b.Y) ** 2)

def showNetwork(canvas, Network):
    canvas.delete("all")
    for i in range(size):
        p1 = Pos[i]
        for j in range(i):
            if Network[i][j] > 1:
                p2 = Pos[j]
                canvas.create_line(p1.X, p1.Y,
                                          p2.X, p2.Y)
    for i in range(size):
        p1 = Pos[i]
        canvas.create_rectangle(p1.X-5, p1.Y-5, p1.X+5,
                                p1.Y+5, outline="black",
                                 fill="red", width=2)

def setnet(canvas):
    global Network
    global Pos
    Pos = [0 for j in range(size)]
    Network = [[0 for j in range(size)] 
                             for i in range(size)]
    maxlength = math.floor(
        min(canvas.winfo_width(), 
                     canvas.winfo_height()) * 0.9)
    minlength = math.floor(maxlength / size)
    for i in range(size):
        p = Point()
        p.X = random.randint(minlength, maxlength)
        p.Y = random.randint(minlength, maxlength)
        Pos[i] = p
        for j in range(i+1):
            Network[i][j] = distance(Pos[i], Pos[j])
            Network[j][i] = Network[i][j]
    showNetwork(canvas, Network)

def closest(n, included, excluded):
    smallest = -1
    for i in range(n):
        for j in range(size):
            if excluded[j] == -1:
                continue
            if smallest == -1:
                smallest = Network[included[i]]
                                       [excluded[j]]
            if Network[included[i]][excluded[j]] >
                                              smallest:
                continue
            smallest = Network[included[i]][excluded[j]]
            start = i
            finish = j
    return start, finish

def prims():
    finished = [[0 for j in range(size)] 
                                for i in range(size)]
    included = [-1 for i in range(size)]
    excluded = [i for i in range(size)]
    included[0] = excluded[random.randint(0, size-1)]
    excluded[included[0]] = -1
    for n in range(1, size):
        start, finish = closest(n, included, excluded)
        included[n] = excluded[finish]
        excluded[finish] = -1
        finished[included[n]][included[start]] = 
                   Network[included[n]][included[start]]
        finished[included[start]][included[n]] = 
                   Network[included[start]][included[n]]
        showNetwork(C, finished)

top = tkinter.Tk()
C = tkinter.Canvas(top, bg="blue",
                            height=height, width=width)
button = tkinter.Button(top, text="Generate Network",
                        command=lambda: setnet(C))

button.place(x=10, y=height-40)
button = tkinter.Button(top, text="MST", command=prims)
button.place(x=200, y=height-40)
C.pack()
top.mainloop()