Graceful-Tree/grace.py at main · pixelated-rain/Graceful-Tree · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import networkx as nx
import matplotlib.pyplot as plt
from itertools import permutations


def buildGraph():
    print("Let's construct a Graceful Labelling:")

    decision = input("Input graph from file? (y/n) ")

    if decision == 'y':
        data = open("input.txt", 'r')

        G = nx.Graph()
        length = data.readline()
        for n in range(int(length)):
            G.add_node(str(n))

        while True:
            edge = data.readline()
            if edge == "":
                print(G.nodes())
                print(G.edges())
                return G
            else:
                first, second = edge.split(',')
                G.add_edge(first,second)

    vCount = input("How many vertices? ")

    G = nx.Graph()
    for n in range(int(vCount)):
        G.add_node(str(n))

    finished = False
    while ~finished:
        edge = input("Enter an edge 'm,n' or type 'stop': ")
        if edge == "stop":
            print("Graph finished c:")

            #print(G.number_of_nodes())

            #nx.draw_planar(G, with_labels = True, node_color = 'white', node_size = 500)
            #plt.savefig("graph.png")
            #plt.clf()

            #G.clear()
            #nx.draw(G)
            #input("Finished?")

            return G
        else:
            first, second = edge.split(',')
            G.add_edge(first,second)
    return

def findGrace():
    n = 0
    graph = buildGraph()

    vertices = [0]*graph.number_of_nodes()
    for i in range(graph.number_of_nodes()):
        vertices[i] = i

    labelings = list(permutations(vertices))

    for labeling in labelings:
        map = {}
        inv_map = {}
        edgeLabeling = {}

        for i in range(len(labeling)):
            map[str(i)] = labeling[i]
            inv_map[labeling[i]] = str(i)

        graph = nx.relabel_nodes(graph, map)

        for edge in graph.edges():
            edgeLabeling[edge] = str(abs(int(edge[0])-int(edge[1])))

        if len(edgeLabeling.values()) == len(set(edgeLabeling.values())):
            print("Found one!")

            #print(str(n) + ':')
            #print(labeling)

            nx.draw_planar(graph, with_labels = True, node_color = 'white', node_size = 500)
            nx.draw_networkx_edge_labels(graph,nx.planar_layout(graph),edgeLabeling,font_color='red')
            plt.savefig("graph"+str(n)+".png")
            plt.clf()

            graph.clear()
            #nx.draw(graph)

            return

        graph = nx.relabel_nodes(graph, inv_map)
        #print(graph.edges())

    print("And that's all the labelings... phew!")
    return


findGrace()