You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
305 lines
8.3 KiB
305 lines
8.3 KiB
#!/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)
|