# Suche Algorithmus zum Erstellen eines planaren Graphen



## Alan47 (17. Dez 2011)

Hallo zusammen,

nachdem ich jetzt schon eine ganze Weile erfolglos das Web durchsucht habe, dachte ich, ich stelle diese Frage einmal hier, obwohl es jetzt nicht ganz unmittelbar mit Java verbunden ist (auch auf das Risiko hin, dass es eventuell eine blöde Frage sein könnte...).

Und zwar habe ich ein Java-Programm, welches als visuelle Ausgabe einen Graphen auf ein Panel zeichnen soll. Die Knoten und Kanten (also wie viele Knoten es sind und welcher Knoten mit welchem verbunden ist) werden dabei vom Programm berechnet, der Graph dient als Ausgabe. Mein Problem ist, dass ich jetzt einen Algorithmus bräuchte, der mir diese Knoten auf dem Panel anordnet, und zwar nach Möglichkeit so, dass sich keine Kanten überkreuzen. In Ermangelung eines Überbegriffs für einen solchen Algorithmus war es für mich entsprechend schwierig, danach zu suchen.

Nochmal die Ein- und Ausgabe des gesuchten Algorithmus:

Eingabe:
 - Liste von Knoten
 - Liste von (geraden) Kanten, jede Kante kennt Anfangs- und Endknoten

Gewünschte Ausgabe:
 - X/Y Position für jeden Knoten aus der ersten Liste sodass...
 - ... sich die Kanten in der zweiten Liste visuell nicht überkreuzen


Es muss gar nicht in Java geschrieben sein, Pseudocode oder reine Beschreibung eines Algorithmus' wäre völlig ausreichend, auch näherungsweise Algorithmen wären in Ordnung, das Ergebnis muss nicht perfekt sein. Ein Professor an der Uni hat mir erzählt, dass dies u.A. ein aktuelles Forschungsfeld in der Informatik sei, aber wirklich konkret was dazu zu finden, hat sich als schwierig herausgestellt. Wenn mir jemand einen Überbegriff nenen könnte, wie man solche Algorithmen allgemein bezeichnet, wäre mir auch schon sehr geholfen!


Gruß,


Alan


PS: Mir ist bewusst, dass solche Algorithmen existieren und zum Beispiel in "GraphViz" bereits implementiert sind. Ich möchte es aber nach Möglichkeit (aus reinem Interesse) lieber selbst implementieren anstatt auf eine Bibliothek zurückzugreifen.


----------



## Empire Phoenix (17. Dez 2011)

Hm als ganz primitiven Algorithmus würde ich ja ein Backtracking vorschlagen.

Imme einen Weiteren knoten hinzufügen, solange Bedingung mit überschneiden nciht verletzt.
Wenn verletzt, schritt rückgängig und mit anderen Knoten, bzw gleichen Knoten auf andere position weitermachen. Wenn alle möglichkeiten durch und keine gültig, nochmal rückgängig machen und so weiter.

Die Laufzeit hierbei ist zwar nicht all zu toll, jedoch besser als bei reinem Bruteforce, da alle Fälle mit mehrfachen Konflicken wechgelassen werden.

Backtracking ? Wikipedia


----------



## Marco13 (17. Dez 2011)

Ganz allgemein: "Layout-Algorithmen" (für Graphen). Die Überschneidungen zu minimieren ist tatsächlich schwer. Ein konkretes Paper könnte ich auch nicht nennen - da gibt's einfach ZU viele verschiedene Ansätze, Implementierungen, Spezialfälle, Schwerpunkte...  Und auf sowas wie layout planar graph minimize edge crossings - Google Search bist du vielleicht auch schon gekommen 


EDIT: Boah, nicht mal um halb drei kann man hier was schreiben, ohne dass einem einer ein paar Minuten zuvorkommt


----------



## Dow Jones (17. Dez 2011)

Google mal nach Sugiyama, Tagawa und Toda, die haben ein recht bekanntes Verfahren dafür angegeben. Es verarbeitet die Knoten in drei Phasen und kommt dabei leider nicht immer zur optimalen Lösung, aber dafür ist es ganz gut verständlich und implementierbar.


----------



## Gregorrr (17. Dez 2011)

Graphen zu Zeichnen hängt i.d.R. davon ab, in welcher Domäne man sich befindet. Ein Graph steht ja i.d.R. nicht für sich, sondern ist eine Visualisierung eines mathematischen Modells, dass man als Graph modelliert.

Es gibt unendlich viele Repräsentationen eines Graphen => Soll er z.B. hierarchisch angeordnet sein, dürfen sich die Kanten alle nicht schneiden (d.h. planar sein, wobei es Graphen gibt, die nicht planar sind, z.B. der K5), sinds normale Graphen/Digraphen, usw.

Hier hast du eine ganze Vorlesung darüber: Automatisches Zeichnen von Graphen

Du kannst ja mal in die Bib gehen und dir eins der Bücher ausleihen: GD books
In denen werden ganze Frameworks beschrieben, wie man Graphen zeichnen kann.

Hier ist eine Open-Source Implementierung eines Frameworks: OGDF - Open Graph Drawing Framework: tech:layouter

Anfangen könnte man, z.B. bei der Untersuchung ob ein Graph überhaupt planar ist, wenn ja, dann kann man diesen z.B. durch direkte Linien Layouts miteinander verbinden. Ist dieser nicht planar, dann teilt man diesen in planare Untergraphen auf und führt das Linien-Layout auf den Untergraphen aus.

Eventuell ist es auch einfach mit einer guten Verteilung der Knoten im Raum geschehen. Das dürfte fürs erste doch reichen.

Graphen zu Zeichnen ist ein Stoff für Bachelor, Master, Dr.-Arbeiten, usw. Problemstellung skaliert gut^^

[Edit:] Sugiyama, Tagawa und Toda ist in den Vorlesungsunterlagen der Uni Dortmund gut erkärt - mit Pseudocode


----------



## Alan47 (18. Dez 2011)

Hallo Leute,

danke für eure Antworten & Anregungen! Ich werde versuchen, mich in den nächsten Tagen ein wenig in die Materie einzulesen, falls dabei Fragen auftauchen sollten werde ich sie hier posten - einstweilen vielen Dank an alle für die raschen Antworten!


Gruß,


Alan


----------

