Java Graph darstellen mit über 5000 Nodes

[Yogi666]

Hallo Leute,
Für mein Arbeit muss ich ein GraphFramework finden oder selbst schreiben, dass über 5000 Nodes darstellen kann. Konkret geht es um eine State Machine. Labels auf den Nodes, sowie Transistionen zu anderen nodes sind notwendig. Vorgabe ist Java.

Da sind mir bisher einige Frameworks bei meiner Recherche aufgefallen.

Jung
Grappa
Graphviz
jgraph
jgraphT

einige von denen basieren auf SWT, andere auf SWING. Irre ich mich, oder sind SWT und SWING vor allem für nicht performancelastige GUI Komponenten anstatt performanter Grafik vorgesehen? Ich bräuchte also ein Framework, was das Rendern und Buffern der Knoten meines Graphen auf der Grafikkarte berechnet. Die aktuelle Lösung setzt auf CPU Rendering und flackert stark ab ca 1000 Nodes. Über die Graka dürften 10k Nodes und mehr kein Problem sein.

Ist es richtig, dass SWING und SWT nicht über die Graka berechnet werden?
Hab jetzt bisher kein auf Opengl basierendes Java GraphFramework gefunden.
Das rudimentär selber zu schreiben wäre auch möglich, aber unnötig wenn es sowas schon gibt.

Lange rede kurzer Sinn: Suche Graph Framework für Java das flüssig 5000 und mehr Knoten darstellen kann.

Hat jemand Erfahrungen mit sowas oder kann mir eins empfehlen? Ansonsten geh ich die der Reihe nach durch bis eins meinen Anforderungen gefällt.

Über Tipps freue ich mich!
Beste Grüße
Yogi

 

[Krik]

SWT setzt auf die vom Betriebssystem bereitgestellten UI-Elemente, und die werden ab Vista durch die Grafikkarte berechnet. Man nennt das schwergewichtig, weil an den bereitgestellten Elementen eine ganze Menge Betriebssystem dranhängen kann, das die Sache theoretisch langsamer machen kann.
Swing hingegen ist leichtgewichtig, hier rendert Java selber die Elemente.

Bei 5.000+ Elementen wirst du vermutlich aber generell kaum auf nennenswerte Geschwindigkeiten kommen. 5.000 Sprites (falls du diese verwendest) zwingen auch aktuelle Grafikkarten in die Knie (Füllrate!).
Eventuell kannst du etwas noch einiges rausreißen, wenn du den Graph als Bild erzeugst und dann davon nur einen Ausschnitt anzeigen lässt. Dann muss der Rechner nicht so viele Elemente verwalten und alles läuft schneller. Allerdings musst du dann selbst etwas programmieren, wenn der User mit einzelnen Nodes interagieren soll.

 

[Yogi666]

danke für die antwort!
Das mit SWT ist eine nützliche Information, der bisherige Rechner der Probleme damit hat nutzt XP.
Sprites brauche ich nicht, es soll vor einfarbigem Hintergrund ein Kreis mit einem Label gezeichnet werden.

 

[kuddlmuddl]

Evtl Polygone statt Sprites?
Mit OpenGL wären ein paar tausend Kreis/Quadrate gleichzeitig doch keine Herausforderung.

 

[Yogi666]

Ja darauf wollte ich hinaus. Bisher finde ich jedoch nur Sachen die nicht über OpenGl sondern den CPU gerendert werden und daher deutlich limitiert sind. 5000 Nodes sorgen mit Prefuse (Java SWT) und XP dafür, dass der CPU (Pentium 4 3 ghz) auf ~90% läuft. Ich versuch das gleich mal an meinem Win7 rechner und schaue ob es dort über Graka gerendert wird wie Elaurin angesprochen hat.
Da ich wirklich nur Polygone rendere, müsste eine aktuelle Graka selbst mehrere 100k schaffen. Der CPU ist für derartige Parallelverarbeitung ja schlichtweg nicht gemacht. Daher wäre es recht sinnfrei, das per CPU zu rendern.

Ergänzung (14. Juni 2012)

Tja das erste Framework basiert leider auf Swing, also gibts nur CPU Rendering.
Ich versuchs mal mit ner SWT Komponente.

 

[ice-breaker]

Das Problem bei deiner Anzahl an Knoten ist aber nichtmal das Rendering sondern das Layouting, diese Anzahl an Knoten sinnvoll zu positionieren ist sehr komplex. GraphViz schafft das, aber auch nicht in Echtzeit und rendert dir nur ein Bild.

 

[Yogi666]

danke für die antwort.
Ja das Layouting und zoom etc hält mich davon ab, anzufangen es in Java2D zu basteln. Der nötige Zeitaufwand das einigermaßen ordentlich zu machen ist enorm gegenüber dem Einarbeiten in ein fertiges Framework (sowie das ggf anzupassen).

Wenn es am Anfang einige Sekunden dauert mit der Positionierung ist das kein Problem. Der Graph soll dann zoombar sein. Mit Mouse Events müssen Knoten aufgerufen werden können und dann ihre Eigenschaften hergeben.
Graphviz macht aus einer Menge von Anfangsdaten ein Bild, da fehlt dann die Flexibilität per Drag and Drop zu verändern. Da müsste das Gesamtbild jedes mal neu gezeichnet werden. Ich bräuchte etwas was nur betroffene Bereiche neu zeichnet.

Java2D kann seit Java SE 5.0 auf eine Opengl Nutzung zurückgreifen. Ein Tool was Java2D nutzt würde daher schon reichen vermutlich. Leider sprießen nur SWT und Swing aus dem Boden.

Ergänzung (14. Juni 2012)

das Layout kann ja auch problemlos vor dem Erzeugen der Anzeige berechnet werden.

 

[Krik]

Mal so nebenbei gefragt: Warum willst du 5.000 Elemente gleichzeitig anzeigen? Dafür muss man sehr weit herauszoomen, dementsprechend klein und nahezu unsichtbar werden die Knoten sein. Durch manche Zoomfunktionen gehen so viele Details unter, dass zB Linien uU. unsichtbar werden können. Dazu kommt, dass das Editieren der Knoten in der Gesamtansicht keinen Sinn ergibt, da man kaum den richtigen Knoten mit der Maus treffen kann und bei der Menge sowieso überfordert ist.


Ich schlage daher vor, mehrere Zoomlevel mit unterschiedlich detailierter Ansicht und unterschiedlichen Interaktionsmöglichkeiten zu implementieren.

ZB so:
Minimaler Zoom - Gesamtübersicht
Knoten als Quadrate mit 3-x Pixel Kantenlänge (was optisch besser aussieht)
1-2 px dicke Kanten/Verbindungen (je nach Ästhetik)
Interaktionsmöglichkeiten: Reinzoomen
Als Bild rendern

Mittlerer Zoom - Teilüberblick
Knoten als Quadrate mit 30 - 50 Pixel Kantenlänge, inklusive reduzierter Textdarstellung einiger Knoteneigenschaften (wie immer je nach Optik anpassen)
2-5 Pixel dicke Kanten mit reduzierter Textdarstellung einiger Kanteneigenschaften
Interaktionsmöglichkeiten: Reinzoomen, Rauszoomen, 1-x Knoten und Kanten durch Markierungsrahmen mit der Maus markier- und löschbar, Undo-Funktion um Löschen rückgängig machen zu können
Rendern als Bild (die Interaktionsmöglichkeiten kann man problemlos selber per Hand implementieren)

Maximaler Zoom - Detailansicht
Knoten als Rechtecke mit voller Darstellung aller Eigenschaften
2-5 Pixel dicke Kanten mit voller Darstellung aller Eigenschaften
Interaktionsmöglichkeiten: Rauszoomen, Einfügen/Editieren/Löschen einzelner Knoten und Kanten, Markierungsrahmen mit der Maus, um mehrere Knoten & Kanten auf einen Schlag markieren und löschen zu können, Undo-Funktion
Rendern mit GUI-Elementen (Framework ist egal, da man wahrscheinlich eh nicht mehr als ~10 Knoten gleichzeitig sieht)

Bei den letzten beiden Zoomleveln musst du dafür sorgen, dass nur der relevante Teil des Graphs berechnet und angezeigt wird. Die unsichtbaren Teile dürfen dem GUI-System nicht bekannt sein, sonst rechnet er sich eventuell an unsichtbaren Elementen tot.

Das ist imo die effizientes Variante und ähnelt sehr stark dem LoD-System in gängigen Spielen (level of detail, vereinfachte Darstellung bei großer Entfernung, maximale Details bei geringer Entfernung plus Abstufungen dazwischen). Für die Gesamt- und mittlere Ansicht reicht das simple Rendern in einen Puffer. Das schaffen auch ältere Systeme ruckzuck (5.000 Quadrate + 5.000*x Linien, bei mittlerem Zoom ein Bruchteil davon, sollte in deutlich unter 1 s möglich sein). Die Detailansicht stellt ebenso für alle Rechner kein Problem dar.
Natürlich ist es aufwändiger bei der Programmierung (wobei die einzelnen Zoomstufen für sich selber recht einfach sind), aber dafür läuft das Programm in jedem Fall flüssig.


Du musst dich entscheiden, ob du ein flüssiges Programm haben willst, dass aber komplexerer Programmierung bedarf, oder ob du dir die Programmierung einfach machst, das Programm aber laufend hängt.