#!/usr/bin/python #Import required libraries import sys import os from PIL import Image, ImageDraw, ImageShow, ImageFont import math import psutil import time from collections import defaultdict class Node: def __init__(self, rect, colour, index, node_size): self.rect = [rect[0], rect[1], rect[0] + node_size, rect[1] + node_size] self.pos = ((self.rect[0] + self.rect[2])/2, (self.rect[1] + self.rect[3])/2) self.colour = colour self.index = index def colour(index): array = ["red", "blue", "green"] return array[index % len(array)] def sort_edges(edges): return sorted(edges, key = lambda x: (x[0].index, x[1].index)) def sort_tuples_and_edges(edges): sorted_tuples = [] for e in edges: if e[0].index == num_nodes - 1 and e[1].index == 0: sorted_tuples.append(e) elif e[0].index > e[1].index: sorted_tuples.append((e[1], e[0])) else: sorted_tuples.append(e) return sort_edges(sorted_tuples) def to_indices(edge): return (edge[0].index, edge[1].index) def list_to_indices(edges): e = [] for edge in edges: e.append(to_indices(edge)) return e class Sxiv(ImageShow.UnixViewer): def get_command_ex(self, file, **options): return ("bspc rule -a \* -o state=floating focus=off && sxiv",) * 2 node_size = 10 m, n = 600, 600 nodes = [] num_nodes = 6 assert(num_nodes % 3 == 0) ImageShow.register(Sxiv(), -1) font = ImageFont.truetype("Hack-Bold.ttf", node_size*3) im = Image.new('RGB', (m, n)) draw = ImageDraw.Draw(im) draw.rectangle([0, 0, m, n], "white") x_step = math.floor(m / num_nodes) - 10 y_step = math.floor(n / num_nodes) - 10 centerX = math.floor(m/2) centerY = math.floor(n/2) step = -math.floor(360 / num_nodes) radius = math.floor(n/2.5) for i in range(0, num_nodes): angle = (i * step) coordinates = [centerX + radius*math.cos(math.radians(angle)), centerY + radius*math.sin(math.radians(angle))] nodes.append(Node(coordinates, colour(i), i, node_size)) for i,node in enumerate(nodes): draw.rectangle(node.rect, fill=node.colour) draw.text(node.pos, str(node.index),font=font, fill="black") root = [] for i in range(0, num_nodes - 1): root.append((nodes[i], nodes[i+1])) root_tuples = list_to_indices(root) def connect_tuple(d, e): connect(d, e[0], e[1]) def connect(d, v, w): d.line([v.pos, w.pos], fill="black", width=math.floor(node_size/4)) def draw_tree(edges): local = im.copy() d = ImageDraw.Draw(local) for e in edges: connect(d, e[0], e[1]) local.show() def has_crossing(edge, edges): new = to_indices(edge) if(new[0] > new[1]): new = new[::-1] for e in edges: exis = to_indices(e) if(exis[0] > exis[1]): exis = exis[::-1] if(exis[0] < new[0] < exis[1] and new[1] > exis[1]): return True if(exis[0] < new[1] < exis[1] and new[0] < exis[0]): return True return False def dfs(parents, visited, adj, node): visited.add(node) for adj_node in adj[node]: if adj_node not in visited: parents[adj_node] = node dfs(parents, visited, adj, adj_node) elif parents[node] != adj_node: return True def has_cycle(new_edge, edges): adj = defaultdict(set) es = [to_indices(e) for e in edges] es.append(to_indices(new_edge)) for x, y in es: adj[x].add(y) adj[y].add(x) visited = set() parents = [None] * len(adj) if dfs(parents, visited, adj, to_indices(new_edge)[0]): return True return False def construct_neighbourhood(edges, index): neighbourhood = [] i = 0 #print(list_to_indices(edges)) for e in edges: if not is_from_root(to_indices(e)): continue start = e[0].index #print("Testing: " + str(to_indices(e))) for new_target in range(0, num_nodes): new_edge = (e[0], nodes[new_target]) if(e == new_edge): continue cropped_edges = edges[:] cropped_edges.remove(e) #print(list_to_indices(cropped_edges)) #print(to_indices(new_edge)) #input() if(new_target % 3 == e[0].index % 3): #print("isn't bicolored") continue if(has_crossing(new_edge, cropped_edges)): #print("has_crossing") continue if(has_cycle(new_edge, cropped_edges)): #print("has_cycle") continue cropped_edges.append(new_edge) #print("Added: " + str(list_to_indices(cropped_edges))) neighbourhood.append(sort_edges(cropped_edges)) if(i == index): return neighbourhood i = i + 1 return neighbourhood def degree(edges): #print("degree...") l = len(construct_neighbourhood(edges, sys.maxsize)) #print("done...") return l def get_jth_neighbour(edges, index): #print("Getting index: " + str(index)) return construct_neighbourhood(edges, index)[index] def is_from_root(edge): return abs(edge[0] - edge[1]) == 1 def get_largest_non_root_edge(edges): edges.reverse() for e in edges: if not is_from_root(e): return e return edges def get_largest_missing_convex_edge(edges): difference = [e for e in root_tuples if e not in edges] return difference[-1] def get_missing_convex_edge(edges, tup): for i in range(tup[0], tup[1]): if (i,i+1) not in list_to_indices(edges): print("missing edge: " + str((i,i+1))) return (nodes[i], nodes[i+1]) def get_e_bar(edges): for e in sort_tuples_and_edges(edges): if not is_from_root(to_indices(e)): print("e_bar: " + str(to_indices(e))) return e return edges def get_parent(edges): sorted_edges = sort_edges(edges) e = get_e_bar(sorted_edges) if type(e) is list: return list_to_indices(edges) try: sorted_edges.remove(e) except: sorted_edges.remove((e[1], e[0])) #sorted_edges.append(get_largest_missing_convex_edge(sorted_edges)) sorted_edges.append(get_missing_convex_edge(sorted_edges, to_indices(e))) return sorted_edges def get_parent_in_nodes(edges): parent = list_to_indices(get_parent(edges)) p = [] for e in parent: p.append((nodes[e[0]], nodes[e[1]])) return sort_edges(p) # #test = [] #test.append((nodes[1], nodes[2])) #test.append((nodes[2], nodes[3])) #test.append((nodes[2], nodes[4])) #test.append((nodes[4], nodes[0])) #test.append((nodes[0], nodes[5])) #test.append((nodes[5], nodes[6])) #test.append((nodes[0], nodes[7])) #test.append((nodes[8], nodes[8])) #draw_tree(test) #draw_tree(get_parent_in_nodes(test)) v = root j = 0 count = 1 while True: deg = degree(v) #print(" degree = " + str(deg)) while(j != deg): j = j + 1 w = sort_tuples_and_edges(get_jth_neighbour(v, j - 1)) print("\t prob(v): " + str(list_to_indices(v))) print("\t probing: " + str(list_to_indices(w))) print("\t pred(w): " + str(list_to_indices(sort_tuples_and_edges(get_parent_in_nodes(w))))) if(sort_tuples_and_edges(get_parent_in_nodes(w)) == sort_tuples_and_edges(v)): print("!!! Added: " + str(list_to_indices(w))) v = w j = 0 count = count + 1 #print(" Current w:" + str(list_to_indices(v))) #print(" degree = " + str(deg) + " j = " + str(j)) deg = degree(v) #draw_tree(v) #input() #for proc in psutil.process_iter(): # if proc.name() == "sxiv": # proc.kill() input() if(v != root): w = v v = get_parent_in_nodes(w) j = 0 neighbours = construct_neighbourhood(v, sys.maxsize) n = neighbours[j] while(n != w): j = j + 1 n = neighbours[j] input() if(v == root and j == degree(root)): print(list_to_indices(v)) print(j) break #while True: # for tree in construct_neighbourhood(root, sys.maxsize): # im1 = im.copy() # d = ImageDraw.Draw(im1) # draw_tree(d, tree) # im1.show() # # input() # #for proc in psutil.process_iter(): # # if proc.name() == "sxiv": # # proc.kill() # assert(False)