print ("Homework 16 (2) 10.2 #2 : Use Kruskal's algorithm to find a minimal spanning tree for the capital cities of New England...")
print("")
print("ME: Augusta, Maine") # vertex 1
print("MA: Boston, Massachusetts") # vertex 2
print("NH: Concord, New Hampshire") # vertex 3
print("CT: Hartford, Connecticut") # vertex 4
print("VT: Montpelier, Vermont") # vertex 5
print("RI: Providence, Rhode Island") # vertex 6
print("")

print ("While not geographically true, the graph below does accurately depict the distances between each city...")

edges = [
    (1, 2, 165),
    (1, 3, 148),
    (1, 4, 266),
    (1, 5, 190),
    (1, 6, 208),
    (2, 3, 75),
    (2, 4, 103),
    (2, 5, 192),
    (2, 6, 43),
    (3, 4, 142),
    (3, 5, 117),
    (3, 6, 109),
    (4, 5, 204),
    (4, 6, 70),
    (5, 6, 223)]

G=Graph(edges)
G.weighted(True)
G.relabel({
1:'ME' , 2:'MA', 3:'NH', 4:'CT', 5:'VT', 6:'RI'})
G.graphplot(edge_labels=True,save_pos=True).show()

print ("Kruskal's algorithm determines the following spanning tree of minimal distances:")

G.relabel({'ME':'Augusta' , 'MA':'Boston', 'NH':'Concord', 'CT':'Hartford', 'VT':'Montpelier', 'RI':'Providence'})
from sage.graphs.spanning_tree import kruskal
E = kruskal(G, check=True);E

T=Graph(E)
T.set_pos(G.get_pos())
T.graphplot(edge_labels=True).show()