Hi, Dirk,
ich denke, aus der Lösung deines Problems könnte man eine
Dissertation machen.
B Forderung, dass senkrechte Linien keine Winkelverläufe
besitzen dürfen
das verstehe ich nicht. Über Knoten hinweg? Ich dachte an ein
„Kirschenmodell“, wo an einem Knoten n Knoten hängen und die n
Kinder haben können. zusammen mit meinen restlichen Annahmen
sollte es damit eine eindeutige Lösung geben.
Die Hoffnung auf eine eindeutige Lösung kommt zu früh!
Ich habe mal ein Beispiel aus dem Leben gegriffen:
http://home.arcor.de/mucu/org1.jpg
Die Hauptabteilung hat zwei (Stabs-) Gruppen direkt zugeordnet.
Die Abteilung 7 hat die Gruppe 9 zugeordnet. Die Konstellation
macht, um Breite zu sparen, Winkelverläufe der Linien nötig.
Dies ist jedoch keineswegs daran gebunden, dass es Verbindungen
über Hierarchieebenen hinweg gibt wie bei einer Stabsgruppe,
dies zeigt z.B. die Verbindung von Gruppe 9 zu Untergruppe 16,
die, um Breite zu sparen, auch einen Winkelverlauf braucht.
Dies kann also auch in deinem Kirschenmodell vorkommen.
zu 1 und 2: Ich glaube nicht, dass die reichste Ebene (auch
wenn die Blätter nicht senkrecht angeordnet werden) immer die
„Breiteste“ oder wichtigste ist.
Hm. Gegen Glauben kann ich nicht argumentieren. Aber einig werden
sollten wir uns über folgenden Satz 1:
Wenn nur Voraussetzung A gilt, also alle Knoten einer Hierarchie-
stufe auch in einer Ebene dargestellt werden sollen, dann bestimmt
die reichste Hierarchiestufe die Minimalbreite der Darstellung.
Beweis: Alle Org-Einheiten einer Ebene müssen nebeneinander
dargestellt werden. Also ist die Darstellung mindestens so breit
wie die Anzahl der Org-Einheiten in der reichsten Ebene.
Eine Verbreiterung über die Breite der reichsten Ebene hinaus
lässt sich i.a. nur vermeiden, wenn man Winkelverläufe zwischen
den Ebenen zulässt.
Ob die reichste Ebene die wichtigste ist, weiß ich nicht. Das
ist eine Frage der Bewertung, und die mag jeder selbst so treffen
wie er mag. Ob sie die breiteste ist, weiß ich auch nicht. Aber
jedenfalls ist die Darstellung insgesamt nie schmaler als die
der reichsten Ebene.
Weil die reichste Ebene aber nach Satz 1 (ohne weitere Bedingungen)
diejenige ist, die die Mindestbreite der Darstellung bestimmt, beginnt
meine Strategie hier und bewegt sich von hier aus nach oben zur Wurzel
und nach unten zu den feinsten Verästelungen (wo wegen der geringeren
Knotenanzahl weniger Gedränge herrscht).
Was mir gefällt, ist der
Ansatz von unten nach oben zu arbeiten und ggfs. „Platz zu
schaffen“.
Erste Idee:
Initilaisierung: Linke untere Kirsche ist der Anfang. Knoten
dürber, Geschwister dran, Knoten in die Mitte.
Elter des Knoten ermitteln. Dessen Kinder ermitteln und
dranhängen, Knoten „zentrieren“ (nach rechts schieben).
dann rekursiv Kinder und Kindeskinder etc abarbeiten.nach
jedem Geschwistersatz alle Eltern bis zur aktuellen Wurzel
korrigieren.
immer höher, bis Root erreicht ist.
Es kann durchaus sein, dass dein Algorithmus in vielen praktischen
Fällen ein gutes Ergebnis liefert. Ob es ein optimales Ergebnis
ist, wissen wir noch nicht. Mein Optimierungsansatz, in jedem
Schritt kürzere Äste zwischen 2 längere zu setzen, um Lücken
füllen zu können, ist nicht erkennbar, aber ich habe auch keine
Beweise dafür, dass meine Strategie Vorteile bringt.
Ich weiß nur, dass ein Baum durch alle bestehenden Beziehungen
eindeutig bestimmt ist. Die optimale Darstellung kann daher nur
eine (möglichst geschickte Permutation der Äste) mit Ausnutzung
des freien Raumes zwischen den großen Ästen sein. Und da hilft
es nicht, links unten anzufangen und systematisch vorzugehen,
sondern eine Strategie zur möglichst geschickten Raumnutzung
ist angesagt. Ich glaube allerdings, dass es dafür auch keinen
deterministischen sondern nur einen schrittweise optimierenden
Weg geben wird, ähnlich wie bei anderen Optimierungsproblemen.
Mögliche Bewertungen von Ästen könnten die
Eigenschaften „schlank“, „Speckringe“, „bauchlastig“,
naja, dachte schin du meinst mich … 
„kegelförmig“, „kopflastig“ usw. sein. Die Auswahl von
optimalen Nachbarn würde dann etwa lauten: Kopflastig neben
kegelförmig, schlank neben bauchlastig, etc.
Nein, mit diesen Attributen habe ich nicht dich gemeint, nicht
einmal mich selbst, obwohl das eine oder andere zutrifft.
Gruß, multze
