import networkx as nx
import random
import sys
import time

def genedges (G):
    n = len(G.nodes())

    # Randomly add edges
    for i in range(0,n-1):
        for j in range(i+1,n):
            if random.random() < 0.25:
                w = random.randint(1,4)
                G.add_edge(i, j, weight=w)

    # If the graph is still unconnected, add edges to make it connected
    nc = nx.number_connected_components(G)
    if nc > 1:
        C = nx.connected_components(G)
        j = None
        for c in C:
            i = c.pop()
            if j is not None:
                print([i, j])
                w = random.randint(1,4)
                G.add_edge(i, j, weight=w)
            j = i

def saveinfo (G):
    n = len(G.nodes())
    L = sorted(G.edges(data=True))
    m = len(L)
    print(n)
    print(m)
    for e in L:
        i, j, w = e
        w = w['weight']
        print(str(i) + " " + str(j) + " " + str(w))

def printMST (T):
    E = sorted(T.edges(data=True))
    totalwt = 0;
    for e in E:
        i, j, w = e
        w = w['weight']
        totalwt += w
        print("(" + str(i) + "," + str(j) + "):" + str(w), end=" ")
    print("[" + str(totalwt) + "]")

def treeweight (T):
    E = sorted(T.edges(data=True))
    totalwt = 0;
    for e in E:
        i, j, w = e
        w = w['weight']
        totalwt += w
    return totalwt

def addedge (T,L,n,m,l,k,minwt,currwt):
    # Early abort strategies
    if currwt > minwt: return               # The current weight is already large
    if len(nx.cycle_basis(T)) > 0: return   # T already contains a cycle
    if l == n-1:                            # All edges added
        printMST(T)
        return
    for e in range(k,m-n+l+2):              # Recurse with another edge added
        i, j, w = L[e]
        w = w['weight']
        T.add_edge(i, j, weight=w)
        addedge(T,L,n,m,l+1,e+1,minwt,currwt+w)
        T.remove_edge(i, j)

def genallMSTs (G,minwt):
    T = nx.Graph()
    n = len(G.nodes())
    T.add_nodes_from(range(n))
    L = sorted(G.edges(data=True))
    addedge(T,L,n,len(L),0,0,minwt,0)

# Initialize parameters
random.seed(time.time())
# random.seed(0.7)
n = eval(sys.argv[1]) if (len(sys.argv) >= 2) else 10

# Create initial graph
G = nx.Graph()
G.add_nodes_from(range(n))
genedges(G)
saveinfo(G)

# Check for connectedness
if not nx.is_connected(G):
    print("Sorry! Graph is not connected. Exiting...")
else:
    # Generate one MST
    T = nx.minimum_spanning_tree(G)
    print("\n+++ MST found")
    printMST(T)
    minwt = treeweight(T)

    # Generate all MSTs
    print("\n+++ Generating all MSTs")
    genallMSTs(G,minwt)