Implementation of the BUILD algorithm (Aho et al., 1981)

build.py

#Implementation of BUILD algorithm

from pptree import *
from blessings import Terminal
term = Terminal()

colFunctions = ["red","green","yellow","blue","magenta","cyan"]

def printTab(*args, **kwargs):
	try:
		tab = kwargs.pop('tab')
	except:
		tab = 0
	args = [str(x) for x in args]
	args = " ".join(args)
	print("	"*tab+args)
	
def contraintToStr(c):
	return "("+c[0][0] +","+ c[0][1] + ") < (" +c[1][0] +","+ c[1][1] + ")"

def partitionToStr(pi):
	for i in range(len(pi)):
		pi[i].sort()	
	part = ["{"+",".join(s)+"}" for s in pi]
	return ",".join(part)

def partition(S,C,tab=0):

	printTab("PARTITION:",tab=tab)
	#Apply first rule
	
	#Add all S to pi as individual blocks
	pi = [[n] for n in S]

	#Apply first rule
	for c in C:

		#Find symbol in ith pos
		for i in range(len(pi)):
			if c[0][0] in pi[i]:
				iIndex = i
				break

		#Find symbol in jth pos
		for i in range(len(pi)):
			if c[0][1] in pi[i]:
				jIndex = i
				break

		#if not in same block -> merge
		if iIndex != jIndex:
			pi[min(iIndex,jIndex)] += pi.pop(max(iIndex,jIndex))

	printTab("pi after Rule1:",partitionToStr(pi),tab=tab)

	#Rule 2
	performedMerge = True
	while performedMerge:
		performedMerge = False
		for k,c in enumerate(C):
			for idx,s in enumerate(pi):
				if c[1][0] in s and c[1][1] in s: #if k,l are both in this block
					for j in range(0,len(pi)):
						if idx!=j:
							if c[0][0] in pi[j] or c[0][1] in pi[j]: #if i or j are in the block
								#Merge blocks
								printTab("	USE C",k+1,tab=tab)
								pi[min(idx,j)] += pi[max(idx,j)]
								pi[max(idx,j)] = []
								performedMerge = True

		pi = [x for x in pi if x != []]
	printTab("pi after Rule2:",partitionToStr(pi),"\n",tab=tab)
	return pi



def build(S,C,tab=0):
	cString = ",".join([contraintToStr(c) for c in C])
	header = "BUILD({"+",".join(S)+"} , {"+cString+"})"
	printTab(eval('term.'+colFunctions[tab+1%len(colFunctions)]+'("--"+header+"-"*(38-len(header)))'),tab=tab)
	tab += 1


	if len(S) == 1:
		printTab("Leaf",S[0],tab=tab)
		root = Node("")
		Node(S[0],parent=root)
		print_tree(root,indent='	'*(tab))
		printTab(eval('term.'+colFunctions[tab%len(colFunctions)]+'("--END"+"-"*35)'),tab=tab-1)
		return Node(S[0])
	else:
		pi = partition(S,C,tab=tab)
		r = len(pi)
		if r == 1:
			return None
		else:
			t = []
			for m in range(0,r):

				#C_m:= {(i, j) < (k, l) in C]i,f,k,1 are in S.};
				cm = []
				constraintsString = ""
				for c in C:
					if c[0][0] in pi[m] and c[0][1] in pi[m] and c[1][0] in pi[m] and c[1][1] in pi[m]:
						constraintsString += "	"*(tab+1) + contraintToStr(c)+"\n"
						cm.append(c)
				if constraintsString != "":
					printTab("The contraints germane to S_"+str(m+1)+":"+"{"+",".join(pi[m])+"}, are:",tab=tab)
					print(constraintsString)
				else:
					printTab("There are no contraints germane to S_"+str(m+1)+":"+"{"+",".join(pi[m])+"}",tab=tab)


				#Tm := BUILD(S_m, C_m);
				t.append(build(pi[m],cm,tab=tab))
				if t[-1] == None:
					return None


		#/* if we reach here a tree exists */
		root = Node("")
		root.children = t

		print_tree(root,indent='	'*(tab))
		printTab(eval('term.'+colFunctions[tab%len(colFunctions)]+'("--END"+"-"*35)'),tab=tab-1)

		return root 

#Q1d
C = [
(("e", "f"),("k", "d")),
(("c", "h"),("a", "n")),
(("j", "n"),("j", "l")),
(("c", "a"),("f", "h")),
(("j", "l"),("e", "n")),
(("n", "l"),("a", "f")),
(("d", "i"),("k", "n")),
(("d", "i"),("g", "i")),
(("c", "l"),("g", "k")),
(("g", "b"),("g", "i")),
(("g", "i"),("d", "m")),
(("c", "h"),("c", "a")),
(("e", "f"),("h", "l")),
(("j", "l"),("j", "a")),
(("k", "m"),("e", "i")),
(("j", "n"),("j", "f"))
]
tree = build(["a","b","c","d","e","f","g","h","i","j","k","l","m","n"],C,tab=0)

#Example 1
'''
C = [
(("1","2"),("1","3")),
(("3", "4"),("1", "5")),
(("3", "5"),("2", "4")),
#(("4", "5"),("1", "2"))
]
tree = build([str(d) for d in range(1,6)],C,tab=0)
'''

#Example 3
'''
C = [
(("1","3"),("2","5")),
(("1", "4"),("3", "7")),
(("2", "6"),("4", "8")),
(("3", "4"),("2", "6")),
(("4", "5"),("1", "9")),
(("7", "8"),("2", "10")),
(("7", "8"),("7", "10")),
(("8","10"),("5", "9")),
]
tree = build([str(d) for d in range(1,11)],C,tab=0)
'''


'''C = [
#Orphan Leaves
(("4", "4"),("1", "3")),
(("5", "5"),("1", "2")),
(("6", "6"),("1", "2")),

#INTERNALS
#e
(("1", "2"),("1","7")),
(("7", "10"),("1", "7")),
(("7", "8"),("1", "7")),
#d
(("7", "8"),("7", "10")),

#c
(("1", "3"),("1", "2"))
]
tree = build([str(d) for d in range(1,11)],C,tab=0)'''