ReverseSearchBicoloredSpanningTrees/st.py

#!/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)