Wer das Problem sehr komisch findet, dann nur kurz der Hinweis, dass ich mit Graph nicht Geraden, Parabeln oder Sinuskurven meine, sondern die Datenstruktur Graph. Man hat da Knoten und Verbindungen zwischen den Knoten, die z.B. für Städte und Flugverbindungen zwischen den Städten stehen können.

Ich suche ein Programm oder einen Algorithmus (den ich dann implementieren müßte), das/der mir einen Graphen nicht in Form einer Adjazenzmatrix oder -liste ausgibt, sondern eben graphisch. Mit Punkten und Linien zwischen den Punkten.

Weiss da jemand was?

Hallo!

Ich habe mal ein Tutorial-Thread über Rekursion geschrieben, da gibt´s einen Link zu einem Programm mit Sourcen, das evtl. für dich interessant ist. Es geht darum, den kürzesten Weg von Punkt A zu Punkt B zu kommen, das ist auch graphisch visualisiert.

Hier der Link zum Thread, hier der zum Download.

Cu,
Udontknow

Hab das mal kurz überflogen, und ich glaube, das ist nicht ganz das, was ich brauche.
Wenn ich das richtig verstehe, generierst du zufällige KnotenKoordinaten, und erzeugst Verbindungen zwischen diesen Knoten, wenn gewisse Anforderungen erfüllt sind. Dadurch baust du den Graphen auf und machst dann darauf deine Routenplanung. Ich suche das umgekehrte:

Ich habe einen Graphen gegeben, z.B. in der Form

evtl kriegen die Kanten auch noch die Information Gerichtet/Ungerichtet/Distanz etc.

Ich möchte dann diesen Knoten Koordinaten zuweisen (2D, 3D, völlig egal), so dass die Zeichung einigermaßen übersichtlich wird...

Wieso ist das nicht das, was du brauchst? Du sollst ja nicht die Zufallsgenerierung verwenden, sondern nur die Klasse TNetz!

Hier mal die Realisierung:


Du musst anschliessend dir nur einen ordentlichen Algorithmus überlegen, der die X und Y-Koordinaten zuweist.

Cu,
Udontknow

Die interne Darstellung des Graphen im Rechner hab ich schon. Sie stimmt zwar nicht mit deiner überein, aber so gehts auch. Bei mir hab ich im wesentlichen eine Basisklasse TElement, die nur einen Vorwärts- und Rückwärtszeiger enthält. Damit baue ich mir für die einzelnen Knoten die Adjazenzliste, in dem ich von TElement Klassen wie z.B TKante und TKnoten ableite, und diese in die Liste packe. Die Datenstrukturen TStack und TQueue für Tiefen- und Breitensuche durch den Graphen hab ich auch fertig. Und die Wegesuche funktioniert bestens.

Zusammengefasst habe ich den Grundstock, um praktisch jeden Graphalgorithmus ohne viel Mehraufwand zu proggen

Udontkow hat folgendes geschrieben:

Du musst anschliessend dir nur einen ordentlichen Algorithmus überlegen, der die X und Y-Koordinaten zuweist.

Jetzt hast du es! Ich suche so einen Algorithmus. Wenn ich den hätte, würde ich hier nicht nachfragen. Aber ich weiss nicht, wo ich da anfangen soll. Bei jedem neuen Ansatz finde ich direkt nen Graphen, mit dem das in die Hose geht...

Hmmm... Das ist natürlich schon ein wenig knifflig. Vielleicht muss man das graphische Aufbereiten selbst auch ebenso rekursiv angehen.

Ich spekuliere einfach mal so wild drauf los:
Du versuchst, immer erst einen Knoten zu setzen und um ihn herum die anderen Knoten, mit denen er eine Verbindung hat. Sobald du einen dieser Knoten setzt, sollte das gleiche Prozedere für diesen Knoten erfolgen, also dessen Partnerknoten nun in Nähe setzen.
Dabei darf natürlich auch nicht beliebig oft die Position eines Knotens geändert werden. Vielleicht müsste da dann so eine Art Abschwächung für das Verschieben implementiert werden.

Hmmm, ich weiss, das ist nicht wirklich eine Hilfe. Da wirst du selbst auch noch ordentlich schwitzen, nehme ich an...

Cu,
Udontknow

Als Regel zum Verschieben:

Ein Knoten sollte nur dann verschoben, wenn er an der neuen Stelle einen besseren Platz hätte (sprich: näher zu seinen Partnerknoten). Das könnte man zum Beispiel so ausdrücken:



Cu,
Udontknow

Hmm..danke, dass du dir da Mühe machst. Aber ich glaube, das geht so nicht. Zwar kann man mit deiner Prozedur rausfinden, wie weit der Knoten von seinen Nachbarn zusammen entfernt ist, aber wie findet man dann einen Platz, der besser ist? Wohin soll man den Knoten verschieben? Und soll man überhaupt? Oder wäre es besser, wenn man den Knoten da so läßt, und lieber ein paar andere Knoten verschiebt? Was ist überhaupt ein besserer Platz? Die Distanz ist ja nicht das einzige Gütesiegel. Sinnvoll wäre ja auch, dass man möglichst wenige Kantenüberschneidungen hat. Und zwei Kanten dürfen ja auch niemals genau übereinanderliegen. Das müßte man auch noch überprüfen.
Guck dir z.b. Das Bild an. Angenommen, der Algo hat bisher das linke Bild gemalt. Der minimale-Distanz-Algorithmus würde den unteren Knoten in die Mitte des Quadrats verschieben, und Essig isset mit der Übersichtlichkeit...


Eine Idee wäre z.B. gewisse Teilstrukturen in dem Graphen zu suchen. Z.B. Cliquen, Kreise, Wege etc. Dann für diese Teilstrukturen (meinetwegen rekursiv) Koordinaten festlegen (das Problem ist dann ja kleiner geworden), und anschliessend den Graph wieder "aufpusten". Aber ganz ausgegoren ist das auch noch nicht...und noch dazu ein riesen Programmieraufwand.

Jaja, das ist schon eine gewaltige Aufgabe, keine Frage. Habe ja auch nicht behauptet, daß das die perfekte Lösung ist, es sind halt theoretische Ansätze, die ich ersponnen habe.

Zur Positionsbewertung: Nimm doch deine Bedingungen einfach noch dazu. Also z.B. den Wert noch einmal durch die Anzahl der Kantenüberschneidungen (evtl vorher modifizieren) teilen.

Zur Positionsbestimmung: Nun, da würde ich vielleicht einfach eine Art Feld (im Sinne von Schachbrett, nicht programmiertechnisch )einführen, sodaß also grundsätzlich ein Mindestabstand besteht. Die Position eines Feldes darf natürlich nicht doppelt vergeben werden.

Das mit den Teilstrukturen klingt übrigens auch sehr gut, allerdings ergibt sich da natürlich auch die Frage, wie du das abgrenzt, denn die Ermittlung der optimalen Teilstruktur ist auch wieder eine Sache, die die Untersuchung aller Knoten miteinbezieht.

Cu,
Udontknow