"""
Branch-and-bound-Baeume fuer das Rucksackproblem.
benoetigt das Zeichenprogramm ipe http://ipe7.sourceforge.net/
"""

gg = [6,2,5,4,7]
ww = [10,6,12,7,9]
B = 14 # 14/20/50
#B = 15 # 23/27/53

gg = [7,6,2,5,4]
ww = [9,10,6,12,7]
B = 14 # 14/30/50
#B = 15 # 23/39/52

sortieren = False
#sortieren = True

allslides = False
allslides = True

# Strategie zur Knotenauswahl:
#############################
bestselection = "DFS0" # Tiefensuche x=0 zuerst
#bestselection = "DFS1" # Tiefensuche x=1 zuerst
#bestselection = "BFS" # Breitensuche
#bestselection = min
#bestselection = max

zeilenabstand = 13
hdist = 8
voffset = 80
boxheight = 60
boxwidth = 35

n=len(gg)


if sortieren:
  a = [(-w/float(g),g,w) for g,w in zip(gg,ww)]
  a.sort()
  gg = [g for r,g,w in a]
  ww = [w for r,g,w in a]

def data_table(ratios=False):
    aus.write(r"""<text
pos="20 570" stroke="black" type="minipage" width="500"
halign="left" valign="top" size="smell">\begin{tabular}{r|"""
 + "r"*len(gg)+ r"""|l}
$i$&""" + "&".join(str(i+1) for i in range(len(gg))) + r"""\\
\hline
$g_i$ &"""  + "&".join(str(g) for g in gg) + "&$G="+str(B)+r"""$\\
$w_i$ &"""  + "&".join(str(g) for g in ww) + (r"""\\
$w_i/g_i$ &"""  + "&".join("%4.2f"%(ww[i]/float(gg[i]))
                for i in range(len(gg)))
if ratios else "")
 + r"""\\
\end{tabular}

\medskip
Strategie: %s
</text>
""" % ("max" if bestselection==max else
"min" if bestselection==min else bestselection))


def full_tree():
    subtree(0,0,0,"root")
def subtree(level,g,w,text):
    print " "*level,text,g,w
    if level>=n: return
    text = "x%d="%(level+1)
    subtree(level+1,g,w,text+"0")
    if g+gg[level]<=B:
        subtree(level+1,g+gg[level],w+ww[level],text+"1")
#full_tree()

width = {}
pos = {}
data = {}
bound = {}

def full_tree():
    global totalwidth
    w = subtree1(0,0,0,())
    totalwidth = max(800,w+20)
    print "width",w
    posi = (totalwidth-w)/2.
    subtree2(0,0,0,(),posi,"{}$root${}")
    for nod in pos:
        pos[nod] += width[nod]/2.

def subtree1(level,g,w,name):
    if level>=n:
        w = width[name] = boxwidth
        return w
    w = subtree1(level+1,g,w,name+(0,))
    if g+gg[level]<=B:
        w += subtree1(level+1,g+gg[level],w+ww[level],name+(1,))
        w += hdist
    width[name] = w
    return w

def subtree2(level,g,w,name,posi,text):
    "pos = horizontal position of left corner of subtree"
    pos[name]=posi
    data[name]=(text,g,w)
    if level>=n:
        w = boxwidth
        return w
    text = "x_%d="%(level+1)
    subtree2(level+1,g,w,name+(0,),posi,text+"0")
    if g+gg[level]<=B:
        w += subtree2(level+1,g+gg[level],w+ww[level],name+(1,),
                      posi+width[name+(0,)]+hdist,text+"1")
        w += hdist
    return w


full_tree()

#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

textform = """<text transformations="translations"
pos="%d %d" stroke="%s" type="label"
halign="center" valign="baseline" size="one">%s</text>
"""

def makebox(x,level,name,g,w,s=None,thick=False):
    l = boxwidth /2.
    return ("""<group matrix="1 0 0 1 %4.2f %4.2f">
<path stroke="%s"%s>
%4.2f %4.2f m
%4.2f %4.2f l
%4.2f %4.2f l
%4.2f %4.2f l
h
</path>
""" % (x,540-level*voffset,color,
       (' pen="heavier"' if thick else ' pen="thin"'),
-l,0,l,0,l,-boxheight,-l,-boxheight) +
textform % (0,2-zeilenabstand, color, "$%s$"%name) +
textform % (0,2-2*zeilenabstand, color, "$g=%d$"%g) +
textform % (0,2-3*zeilenabstand, color, "$w=%d$"%w) +
(textform % (0,-4*zeilenabstand, color, "$%4.2f$"%s) if s else "") +
"</group>\n")

def writebox(name,thick=False):
    if len(name)>0:
        parent = pos[name[:-1]]
        aus.write("""<path stroke="%s" pen="thin">
%4.2f %4.2f m
%4.2f %4.2f l
</path>
""" % ((color if color =="lightgray" else "black"),
 parent,540-(len(name)-1)*voffset-boxheight,
       pos[name],540-len(name)*voffset)) 
    text,g,w = data[name]
    aus.write(makebox(pos[name],len(name),text,g,w,bound.get(name),thick))


def rule1():
 """max ratio among remaining items
 pick the node with smallest upper bound"""
 global color, Bd,nknoten
 Bd = 0 #None
 visited = []
 newopt = False
 frontier = [()]
 nknoten = 1
 computebound(())

 def process(current):
    global Bd,nknoten
    nknoten += 1
    if data[current][2]>Bd:
        Bd = data[current][2] # new optimum.
        newopt = True
    else:
        newopt = False
    if len(current)==n: # a leaf
        visited.append(current)
    else:
        computebound(current)
        frontier.append(current)
    return newopt

 if allslides:
     color = "black"
     aus.write(pagestart)
     for nod in pos: writebox(nod)
     print_bound(0,len(pos))
 while frontier:
     color = "black"
     if allslides:
         aus.write(pagestart)
         for nod in visited: writebox(nod)
         for nod in frontier: writebox(nod,True)
         print_bound(Bd,nknoten,newopt)

     if bestselection == "BFS":
         nextn = frontier[0]
     elif bestselection in ("DFS0", "DFS1"):
         nextn = frontier[-1]
     else: # max or min
         _,nextn = bestselection((bound[nod],nod) for nod in frontier)
     frontier.remove(nextn)
     if allslides:
         color = "black"
         aus.write(pagestart)
         for nod in visited: writebox(nod)
         for nod in frontier: writebox(nod,True)
         color = "blue"
         writebox(nextn,True)
         color = "black"
         print_bound(Bd,nknoten)

     visited.append(nextn)
     if Bd==0 or bound[nextn]>Bd:
         # go to children
         newopt = False
         if bestselection != "DFS0":
           newopt = process(nextn+(0,)) or newopt
         if nextn+(1,) in pos:
           newopt = process(nextn+(1,)) or newopt
         if bestselection == "DFS0": # Kinder in umgekehrter Reihenfolge
           newopt = process(nextn+(0,)) or newopt

 color = "black"
 aus.write(pagestart)
 for nod in visited: writebox(nod)
 print_bound(Bd,nknoten)


def computebound(current):
    l = len(current)
    text,g,w = data[current]
    maxratio = max(ww[i]/float(gg[i]) for i in range(l,n))
    bound[current] = w + (B-g)*maxratio

def print_bound(Bd,nknoten, newopt=False):
    aus.write(r"""<text pos="550 560" stroke="black" type="minipage"
width="300"
size="normal">\# Knoten = """+str(nknoten)+" / "+str(len(pos))+
"\n\n$W^* = """ + str(Bd) +
(r"\textcolor{red}+" if newopt else "") +
 """$</text>
</page>
""")
         
     


from b_and_b_ipe import ipestart,pagestart
aus = open("b_and_b_tree.ipe","w")
aus.write(ipestart%(totalwidth,totalwidth))
color = "lightgray"
aus.write(r"""<ipestyle name="backgr">
<symbol name="Background">
<group>
""")
data_table(True)
#aus.write('<group opacity="half">\n') #matrix="1 0 0 1 400 270">\n')
for nod in pos:
    writebox(nod)
aus.write(r"""</group>
</symbol>
</ipestyle>
""")

rule1()

aus.write("</ipe>\n")
aus.close()

import subprocess

subprocess.check_call("ipetoipe -pdf -export b_and_b_tree.ipe", shell=True)
subprocess.check_call("evince b_and_b_tree.pdf", shell=True)
#subprocess.check_call("acroread b_and_b_tree.pdf", shell=True)