import networkx as nx
from random import choice
import itertools

def complete_graph_from_list(L, create_using=None):
    G = nx.empty_graph(len(L),create_using)
    if len(L)>1:
        if G.is_directed():
            edges = itertools.permutations(L,2)
        else:
            edges = itertools.combinations(L,2)
        G.add_edges_from(edges)
    return G


''' We Begin '''
numberNodes = 64
maxDegree = 8

I = nx.Graph()

''' Initialize numberNodes nodes '''
for n in range(1,(maxDegree+1)+1):
    print(n)
    I.add_node(n)

''' Create a Graph where each node is connected to every other node '''
I = complete_graph_from_list(list(I.nodes()))
print(I.edges())
print("Degree List: {}".format(I.degree(I.nodes())))

# exit()

''' Incrementally expand '''
# increment n
for n in range((maxDegree+1)+1,numberNodes+1):
    # create node for n
    I.add_node(n)

    # while the degree of n is less than 8
    while I.degree(n) < maxDegree-1:

        # find an existing random edge
        random_edge = choice(list(I.edges()))


        print("before {}".format(random_edge))
        while n == random_edge[0] or n == random_edge[1] or I.degree(random_edge[0]) > maxDegree or I.degree(random_edge[1]) > maxDegree:
            print("inside {}".format(random_edge))
            random_edge = choice(list(I.edges()))
        print("after {}".format(random_edge))
        # exit()
        I.remove_edge(random_edge[0], random_edge[1])
        I.add_edges_from([(random_edge[0], n),(n, random_edge[1])])

# print(list(I.edges())[randint(1,len(list(I.edges()))-1)])
print("Length of list: {}".format(len(list(I.edges()))))
print("Degree List: {}".format(I.degree(I.nodes())))

plt.figure()
nx.draw_networkx(P, with_labels=True)
plt.show()