Algorythmus zur Zeichnung eines Baumes

anonymus

Hallo,

existieren evtl. irgendwo im Netz fertige Algorythmen,
die beschreiben, wie ein Baum gezeichnet (als Grafik) werden kann?

Leider ist es nicht einfach "nur" ein Binärbaum, sondern ein Gebilde,
das sich theoretisch beliebig oft verzweigen kann,
und ein Knoten auch auf einen darüberligenden "zeigen" kann, wenn sich
dieser in einem anderen Ast befindet oder dass zwei oder mehrere Knoten
einen einzigen Knoten als Nachfolger haben.

(siehe auch: http://www.c-plusplus.net/forum/viewtopic.php?t=87296,
bitte entschuldigt das Cross-Posting, aber die Idee zur Darstellung mit HTML
als Liste etc. hab ich verworfen, war zu unübersichtlich, will jetzt eine Grafik
zeichnen lassen)

Hab zwar schon a bissl was erreicht, aber irgendwie bin ich da noch ned wirklich glücklich darüber

Da der ganze Code zu lange is, hier nur mal ansatzweise:
(PERL)

Baumanfang:
[ ptr ]

ptr ist dann entweder ein 
 - "route-Pointer": ein einziger Nachfolger
 - "case-Pointer" : beliebig viele Nachfolger (case daher, da die Umfrage hier 
                    in Abhängikeit der Auswahl verzweigt, für die 
                    Baumdarstellung eher unwichtig)
 - "if-Pointer:    beliebig viele Nachfolger (meistens wahrscheinlich jedoch 2)

genauer aufbau:
my $routePtr = [fileName,{_continue=>[ ptr ]}]
my $casePtr = [fileName, {_default=>[ ptr ], _cases=>{condition1=>[ ptr ], condition2=>[ ptr ], ...}}]
my $ifPtr = [fileName, {_default=>[ ptr ], condition1=>{_then=>[ ptr ], _else=>[ ptr ]}, condition2=>{_then=>[ ptr ], _else=>[ ptr ]}, ...}]

=> in dem Baum wird jeder Ast der Befragung wiedergegeben.
   Problem: der selbe Knoten kommt öfters in verschiedenen Ästen vor

jetzt wird vereinfacht:
zu jeder Datei werden nur die direkten Nachfolger gespeichert
(sozusagen als Tabelle)

my $table = 
{
   seite1=>[seite2, seite7],
   seite3=>[seite6, seite4],
   seite2=>[seite3],
   seite6=>[seite7],
   seite4=>[seite7]
}

Anmerkung:
die Aufzählung der Seiten ist nicht sortiert.

So und jetzt geht's ans Eingemachte:
Ermittlung der Koordinaten für die einzelnen Knoten...

Vorgehensweise:
(ich hab mich mal auf maximal 3 Verzweigungen pro Knoten beschränkt)

der erste Knoten kriegt vordefinierte Koordinaten.

dann Rekursion:
Parameter für die Funktion: der Name des darzustellenden Knotens
und seine Koordinaten.
Diese ermitteln sich wie folgt:

bei einem einzigen Nachfolger:
KO-mittigerNachfolger = X-Wert vom Aktuellen, Y-Wert vom Aktuellen + deltaY

bei zwei Nachfolgern:
KO-linker Nachfolger = X-Wert vom Aktuellen - deltaX, Y-Wert vom Aktuellen + deltaY
KO-rechter Nachfolter = X-Wert vom Aktuellen + deltaX, Y-Wert vom Aktuellen + deltaY

bei drei Nachfolgern:
linker, mittiger und rechter Nachfolger, ermittlung wie oben

Soweit so schlecht.
Jetzt kann es vorkommen, dass die Knoten von zwei verschiedenen Ästen die selben Koordinaten haben....

Najo, vielleicht gibt's ja schon irgendwas brauchbares.
Bin für Anregungen dankbar

mfg
Martin

case

Vieleicht waere das was für dich :

http://www.research.att.com/sw/tools/graphviz/

anonymus

Hallo,

trifft sich gut, da wir heute die Graphendarstellung wegen der Komplexität auf
unbestimmte Zeit als Nice-To-Have in die Zukunft verschoben haben

Hab jetzt mal so kurz über die Seite drübergeschaut
und mein erster Eindruck ist, dass es brauchbar ist,
vor allem dass es auch klickbare Knoten etc. ermöglicht.

Bloss wenn's schon laufen würde....

najo
Danke

Martin

Korbinian

nur mal eine basisidee: die breite des baumes ist ja immer die breite der unterbäume auf dem nächst tieferen lvl. damit kannst du die gesamtbreite feststellen. dann jeweils die einzelnen ebenen einzuzeichnen sollte nicht so schwer sein jeweils die breite der knoten ausrechnen etc

anonymus

hm,

najo, hab ich auch erst gedacht, so tragisch kann des ned sein...
aber ich hab für Binärbäume schon keine wirklich befriedigende Lösung gefunden
von "allgemeineren" Baumstrukturen mal ganz zu schweigen.

Das obige Programm hab ich jetzt mal ansatzweise durchgetestet und bin mit dem
Ergebnis mehr als zufrieden

=> da mir auch anderweitig noch mehr als genug zum Proggen bleibt,
und meine Gehirnwindungen auch nur noch aus Knoten bestehen,
verzichte ich auf's selber zeichnen von den Bäumen

thx
Martin

Prof84

In soliden OO Hochsprachen kann man Multibäume mit dem
Kompositum (composite) Pattern -
http://home.earthlink.net/~huston2/dp/composite.html
- umsetzen

Für Weicheisprachen wie PHP und Pe(a)rl nutze multidimensionale Arrays:

$Tree['leaf_level_1']['leaf_level_2']['leaf_level_3']....;

cu

P84