Bounding Boxes - Algorithmus mit GNUProlog

Der in der Vorlesung besprochene Algorithmus zum Ausgeben eines Baums basierend auf Bounding Boxes war einfach nach GNUProlog zu übertragen. Die Methode 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.