MaryJane hat geschrieben:
Mausi hat geschrieben:
Diesen Graphen stellt man am besten als Liste dar, wobei jeder Knoten [1..n] Nachfolger (und wenn man den doppelt verkettet) auch [1..n] Vorgänger hat.
Was genau wäre jetzt der unterschied zwischen den Nachfolgern und den Vorgängern?
ähem. räusper. Das war unklar formuliert: Man unterscheidet zwischen:
gerichteter Graph
ungerichteter Graph
(und einigen anderen)
Bei einem
gerichteten Graphen gibt es zwar einen Weg n1-->n2 aber nicht unbedingt auch umgekehrt n1<--n2. Jetzt kann man in den einzelen "Nodes" einfach speichern
wohin der Pfeil zeigt (
Nachfolger), aber später wird man auch feststellen wollen (für einige Algorithem notwendig), welche "Nodes" alle auf diese hier
zeigen (
Vorgänger). Damit man dann nicht den gesamten Graphen wieder absuchen muss (vollständige Suche), speichert man das gleich "doppel-gemoppelt" in den Knoten rein. Man muss nur bei den Einfüge- und Löschoperationen entsprechend vorsichtig sein, dass man die anderen Knoten gleich mitändert. Am einfachen Beispiel:
Code:
definition class node
{
nachfolger = {node}
vorgänger = {node}
inhalt (z.B. Größe des Sterns)
}
nodeA
{
nachfolger = { nodeB, nodeC }
vorgänger = { }
}
nodeB
{
nachfolger = { nodeD, ... }
vorgänger = { nodeA } // siehe nodeA.nachfolger
}
nodeC
{
nachfolger = {...}
vorgänger = { nodeA }
}
Das sieht nun vereinfacht so aus:
Code:
nodeA -----------> nodeB ---------> nodeD
\---------> nodeC
Wenn nun die Verbindung nodeA <--- nodeB (also auch die umgekehrte) erstellt werden soll, so sind beide Knoten nodeA und nodeB zu ändern:
Code:
function insertConnection (sourceNode, destinationNode)
{
sourceNode.addNachfolger (destinationNode);
destinationNode.addVorgänger (sourceNode);
}
Bei dem
ungerichteten Graphen kann man dann auf die Vorgänger/Nachfolger verzichten, nennt das noch vielleicht um in "adjacent Nodes"
Code:
definition Node
{
adjacent = {Node}
inhalt
}
MaryJane hat geschrieben:
Mausi hat geschrieben:
Der Ausgabe-Algorithmus muss sicherlich den Graphen mehrfach traversieren, um "Überschneidungen" bei der Darstellung zu verhindern
Was meinst du mit "mehrfach traversieren"?
... man "besucht" eine Reihe (gewisse Anzahl) von Knoten, d.h. man läuft durch den Graphen, klappert einzelne Nodes ab. Wenn man das für den gesamten Graphen anstellt, so traversiert man vollständig. Das muss mindestens einmal passieren, damit man den zeichnen kann.
MaryJane hat geschrieben:
Mausi hat geschrieben:
Die Knoten bekommen dann ein zusätzliches Attribut [x, y], welches die Lage im Raum beschreibt.
Genau das ist doch das eigentliche Problem: Wie willst du den Welten x und y so zuweisen, dass sie sinnvoll dargestellt werden?
Hehe, ich erwähnte doch jede Library, die man nur finden braucht, wo das schon programmiert ist
Also in groben Stichpunkte könnte das (in's Blaue gesagt) so aussehen:
1. Man läßt die
Ausgabegröße (z.B. 750x550 Pixel) erstmal völlig außer Acht. Umherschieben, Zoomen u.s.w. kann man später ja immer noch. Auch muß der Graph erstmal nicht "in der Mitte, zentriert" sein, sondern man fängt halt irgendwo an.
2. Man greife sich die erste Node (welche, ist egal) und weise den
Wert [0,0] zu. Jetzt haben wir die Mitte definiert.
3. Wir zählen ab, wieviele Nachfolger der Knoten hat, z.B. 3 und
verteilen jetzt gerecht im Uhrzeigersinn: [0,1] (rechts davon), [0,-1] oberhalb, [-1,0] links davon.
4. Wenn man die maximale Anzahl möglicher "Nachfolger" kennt, ist das natürlich einfacher, sonst muss man den
Radius halt vergrößern, bis es passt.
5. So, jetzt wird
rekursiv (ist erstmal das naheliegendste) das gleich wiederholt, und zwar für alle Nachfolger, d.h. jetzt fängt man mit NodeB an (bei [0,1]) und weist die nächsten Punkte zu, wobei man den Vorgänger (nämlich [0,0] so läßt wie er war).
6. Bis jetzt kein Problem, außer wir wollen einen Nachfolger auf das Zeichenbrett bringen, der schon vorher da war (genau da beginnt das
"Kreisproblem"). Man muss jetzt nacharbeiten. Zum Beispiel müssen wir feststellen, ob der "weiter oben", "rechts" oder sonstwo liegt. Das kriegen wir ja durch die Koordination heraus: NodeT[tX,tY]; NodeU[uX,uY] Dann x = tX-uX und y = tY - uY. Ist x>0 dann rechts von uns, x=0 oberhalb oder unterhalb (abhängig von Wert y) und x<0 links von uns. Bei y>0 unterhalb, y=0 auf gleicher Linie und y<0 oberhalb. Wenn x=0 und y=0 ist, dann haben wir was falsch gemacht, weil es derselbe Punkt ist.
7. Achso nebenbei: Die
belegten Punkte sollte man sich noch in einer Matrix merken, damit man "besetzte" leichter erkennen kann, um dann mit dem überhaus einfachen "Verschiebe-Algrothmus" starten kann (lol). Oder man definiert einfach, dass für x, y auch reele Zahlen erlaubt sind, dann kann man immer noch einen "dazwischenquetschen".
8. Jetzt wissen wir aber schonmal, dass irgenwo vorher sich ein "Fehler" eingeschlichen hat, nämlich ursächlich durch unser
"gerechtes Verteilen" am Anfang, wo wir natürlich noch nicht wissen konnten, ob es nun besser war, die NodeU (an NodeX) besser links oder rechts davon zu plazieren. Wir müssen und nur erstmal für eins entscheiden, um später festzustellen, ob das geglückt ist. D.h. wir gehen jetzt die Schritte aus Punkt 5. alle wieder zurück, bis wir bis wieder da waren, wo wir just die NodeT gezeichnet habe. Und wissen nun, dass das der falsche Platz war. nun haben wir uns sinnvollerweise gemerkt, welche Himmelsrichtung denn besser wäre, und quetschen das Dingen jetzt da rein. Gleichzeitig setzen wir auf die NodeT ein "Fähnchen". Wir wissen, dass wir damit ein Problem "hatten".
9. Jetzt malen wir wieder fleißig an dem Graphen, solange, bis wir wieder bei der NodeU angelangt sind, und stellen
erstaunlicher und überraschter Weise fest, dass die schon gezeichnet wurde, und die nicht richtig passt. Wir ... gehen also wieder zurück, bis wir bei der NodeT sind, und sehen da unser "Fähnchen" vom letzten mal. Wie bei Hänsel und Gretel. Wenn wir dieses tolle Fähnchen nicht hätten, würden wir wieder von vorne Anfang, ohne es zu merken. Das Fähnchen heißt jetzt, dass also die NodeT eigentlich
nicht mehr das Problem sein kann, sondern irgendwas vorher. Also gehen wir jetzt 1 Schritt zurück an die Node, die vor der NodeT gesetzt wurde. Nun zu dessen Vorgänger, verschieben den, und setzen da wieder unser Fähnchen drauf.
10. Wenn wir irgendwann auf die Node[0,0] ein Fähnchen setzen sollten, haben wir falsch programmiert.
Das nun in aller gröbster Form, wie gesagt, ins Blaue hinein gedacht. Es gibt da mit Sicherheit Literatur, die das löst.
Ähh... ja, da habe ich noch ein Buch grade gefunden:
Also es gibt schonmal einen Algorithmus, der einen Zyklus in einem Graphen erkennt (also einen Kreis hat, um bei SC zu bleiben).
Es gibt auch einen, der einen "Spannbaum" findet, d.h. einen Pfad, entlang der ganzen Knoten, der jeden nur einmal besucht.
Kann man sicherlich gut gebrauchen.
AHA. Also hier stehts:
Algorithmen und Datenstrukturen in C++, Addison Wesley, Robert Sedgewick, Seite 494 hat geschrieben:
Zum Beispiel ist es möglich, auf effiziente Weise zu bestimmen, ob ein Graph in der Ebene gezeichnet werden kann, ohne dass ich irgendwelche Linien schneiden, oder ob dies nicht möglich ist. Dieses Problem wird das Problem der Planarität (Ebenheit) genannt, und es war kein effizienter Algorithmus für seine Lösung bekannt, bis R. E. Tarjan 1974 einen genialen (jedoch sehr schwierigen) Algorithmus des Problems in linearer Zeit entwickelte, bei dem Tiefensuche verwendet wird.
Für so ein paar Handvoll Knoten von so 500 kann man vielleicht ja einen einfacheren nehmen, den man nur finden muss...
So, und nun darfst Du gerne weitertüfteln.
Grüße,
Mausi
Anmelden
Registrieren
FAQ
Suche
... jetzt kann ich auch den Programmierer von dem Java-Tool besser verstehen, dass er an den Kreisen gescheitert ist.
