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.
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.
