treelayout
bekommt einen Baum übergeben
und füllt dann eine Liste mit Strukturen der Form bb((Name, WRX), LUX, LUY, ROX, ROY)
, wobei
WRX
für die relative X-Koordinate der Wurzel steht, und LUX, LUY, ROX, ROY
für die x-
und y-Koordinaten der Bounding Box des Knotens. Die Länge des Namens des Knotens beeinflußt die
Position der Wurzel. Da die Liste der Bounding Box-Angaben beim rekursiven Durchlaufen erstellt wird,
werden die Variablen in den verschiedenen Fällen auf ihre Domänen festgelegt, wobei wir die
Koordinaten von 0 bis Max, einer ,,symbolischen Konstante'' haben laufen lassen.
Die Vorgehensweise ist einfach: wenn der Knoten ein Blatt ist, ist die rechte obere Ecke gleich der linken unteren, die x-Koordinaten der Bounding Box sind um die Länge des Knotennamens entfernt, und die Wurzelposition ist in der Mitte dazwischen. Wenn ein Knoten einen Nachfolger hat,entsprechen die Bounding Box-Koordinaten bis auf die rechte obere y-Koordinate den Bounding Box-Koordinaten seines Kindes. Die rechte obere x-Koordinate ergibt sich durch die des Nachfolgers plus einen festgelegten Abstand der Baum-Ebenen voneinander, hier 10 Einheiten. Die Wurzel-Position wird wieder durch die Länge des Namens ermittelt.
Wenn ein Knoten 2 Nachfolger hat, ist die Sache schon komplizierter. Zum einen muß man die Bounding Box-Angaben der Kinder in die Liste einbauen. Die beiden Nachfolger-Bäume sind 10 Einheiten voneinander entfernt, und der Knoten ist 10 Einheiten höher als seine Kinder. Die linke untere y-Koordinate der Bounding Box ist die kleinere der y-Koordinaten der Nachfolger-Bounding Boxen (wenn man von einem Koordinatensystem mit (0, 0) links unten ausgeht). Die Wurzel des Knotens liegt genau in der Mitte zwischen der Wurzeln der Kinder (wobei zu beachten ist, das die Wurzelpositionen alle relativ angegeben werden).
treelayout(node(null, N, null), [bb((N, WRX), LUX, LUY, ROX, LUY)]) :- max(Max), fd_domain([LUX, LUY, ROX, WRX], 0, Max), atom_length(N, L), ROX #= LUX + L, WRX #= L // 2. treelayout(node(null, N, TR), [bb((N, WRX), LUX, LUY, ROX, ROY)| BL]) :- max(Max), fd_domain([LUX, LUY, ROX, ROY, WRX, ROY1], 0, Max), treelayout(TR, [bb((K, WRX), LUX, LUY, ROX, ROY1) | NBL]), append([bb((K, WRX), LUX, LUY, ROX, ROY1)], NBL, BL), ROY #= ROY1 + 10. treelayout(node(TL, N, null), [bb((N, WRX), LUX, LUY, ROX, ROY)| BL]) :- max(Max), fd_domain([LUX, LUY, ROX, ROY, WRX, ROY1], 0, Max), treelayout(TL, [bb((K, WRX), LUX, LUY, ROX, ROY1) | NBL]), append([bb((K, WRX), LUX, LUY, ROX, ROY1)], NBL, BL), ROY #= ROY1 + 10. treelayout(node(TL, N, TR), [bb((N, WRX), LUX, LUY, ROX, ROY) | BL]) :- max(Max), fd_domain([LUX, LUY, ROX, ROY, WRX, LUY1, ROX1, ROY1, WRX1, WRX2], 0, Max), treelayout(TL, [bb((N1, WRX1), LUX, LUY1, ROX1, ROY1) | BL1]), treelayout(TR, [bb((N2, WRX2), LUX2, LUY2, ROX, ROY1) | BL2]), append([bb((N1, WRX1), LUX, LUY1, ROX1, ROY1) | BL1], [bb((N2, WRX2), LUX2, LUY2, ROX, ROY1) | BL2], BL), LUX2 #= ROX1 + 10, ROY #= ROY1 + 10, LUY #=< LUY1, LUY #=< LUY2, WRX #= (WRX1 + (WRX2 + LUX2 - LUX)) // 2.
Außer dieser treelayout
-Methode braucht man dann noch andere Methoden, weil man so bisher nur
den Wertebereich der Variablen kennt. Die Variablen müssen also noch ,,gelabelt'' werden, was wir
mit dem ,,first-fail''-Verfahren gemacht haben - es geht die Variablen der Größe ihres Wertebereichs
nach durch und fängt bei der mit dem kleinsten Wertebereich an. Allerdings will fd_labelingff
eine Liste der Variablen, nicht von Bounding Box-Strukturen - deshalb also die Methode
flatten
, die die Struktur rekursiv in eine flache Liste umbaut. Die Methode make_assoc
baut die Struktur in eine den Assoziationslisten des besprochenen Beispiels um, um die ASCII-Ausgabe
zu erleichtern.
tree_layout(T, AL) :- treelayout(T, BBL), flatten(BBL, L), fd_labelingff(L), make_assoc(BBL, AL). tree_layout(T, BBL, AL) :- treelayout(T, BBL), flatten(BBL, L), fd_labelingff(L), make_assoc(BBL, AL). make_assoc([], []). make_assoc([bb((Node, RelX), X, _, _, Y) | R], [p(Node, c(NewX, Y)) | L]) :- NewX is RelX + X, make_assoc(R, L). flatten([], []). flatten([bb((_, WRX), LUX, LUY, ROX, ROY) | R], [WRX, LUX, LUY, ROX, ROY | L]) :- flatten(R, L).
An Verbesserungen für den Algorithmus hatte ich nur die Idee, die Methoden flatten
und
make_assoc
wegzulassen - also mußte ich diese Strukturen direkt erstellen. Die neue Methode
tree_layout
bekommt also einen Baum, und belegt rekursiv einen zweiten Baum, in dem statt nur
des Knotennamens eine Struktur der Form p(Name, c(X, Y))
enthalten ist. Außerdem belegt sie
eine Liste mit den Constraintvariablen, die später ohne Umformung an fd_labeling
weitergegeben
werden kann. Die Assoziationsliste wird nicht mehr gebraucht, weil das Perl-Programm, das auch die
Verbindungen zwischen den Knoten zeichnen soll, ein anderes Ausgabeformat bekommt. Jetzt stellt sich
nur die Frage, ob die Vermeidung von mehrfachem Baum- bzw. Listenabarbeiten das Programm wirklich
effizienter gemacht hat?
treelayout(node(null, N, null), node(null, p(N, c(NewX, LUY)), null), [WRX, LUX, LUY, ROX, LUY]) :- max(Max), fd_domain([LUX, LUY, ROX, WRX, NewX], 0, Max), atom_length(N, L), ROX #= LUX + L, WRX #= L // 2, NewX #= WRX + LUX. treelayout(node(null, N, TR), node(null, p(N, c(NewX, ROY)), TR2), [WRX, LUX, LUY, ROX, ROY| BL]) :- max(Max), fd_domain([LUX, LUY, ROX, ROY, WRX, ROY1, NewX], 0, Max), treelayout(TR, TR2, [WRX, LUX, LUY, ROX, ROY1 | NBL]), append([WRX, LUX, LUY, ROX, ROY1], NBL, BL), ROY #= ROY1 + 10, NewX #= WRX + LUX. treelayout(node(TL, N, null), node(TL2, p(N, c(NewX, ROY)), null), [WRX, LUX, LUY, ROX, ROY| BL]) :- max(Max), fd_domain([LUX, LUY, ROX, ROY, WRX, ROY1, NewX], 0, Max), treelayout(TL, TL2, [WRX, LUX, LUY, ROX, ROY1 | NBL]), append([WRX, LUX, LUY, ROX, ROY1], NBL, BL), ROY #= ROY1 + 10, NewX #= WRX + LUX. treelayout(node(TL, N, TR), node(TL2, p(N, c(NewX, ROY)), TR2), [WRX, LUX, LUY, ROX, ROY | BL]) :- max(Max), fd_domain([LUX, LUY, ROX, ROY, WRX, LUY1, ROX1, ROY1, WRX1, WRX2, NewX], 0, Max), treelayout(TL, TL2, [WRX1, LUX, LUY1, ROX1, ROY1 | BL1]), treelayout(TR, TR2, [WRX2, LUX2, LUY2, ROX, ROY1 | BL2]), append([WRX1, LUX, LUY1, ROX1, ROY1 | BL1], [WRX2, LUX2, LUY2, ROX, ROY1 | BL2], BL), LUX2 #= ROX1 + 10, ROY #= ROY1 + 10, LUY #=< LUY1, LUY #=< LUY2, WRX #= (WRX1 + (WRX2 + LUX2 - LUX)) // 2, NewX #= WRX + LUX.