Gemeinsames Model für Baum- und Graphdarstellung-wie gehts?

[_Andreas_]

Hallo zusammen.


Ich will Netzwerkinformationen (also praktisch Kanten und Knoten), die in einer Datenbank abgelegt sind visualisieren.

Die Info soll gleichzeitig in einem Baum (JTree oder ein SWT-Tree Objekt z.b.) und in einer Graphdarstellung (über irgendein Graphzeichenframework) dargestellt werden.

Jetzt ist es natürlich so, dass das Graphzeichenframework ein anderes Input Modell beötigt wie der Baum. Aber laut Model View Controller Paradigma, sollen ja die gleichen Modells für die verschiedenen Views benutzt werden.

Wie gehe ich nun vor?
Welche Klassen brauche ich denn jetzt noch um MVC umzusetzen?

Sorry für diese recht grundsätzliche Frage, aber ich bin mir im Moment echt nicht im Klaren wie man sowas am besten anpackt.

Grüße
andreas

 

[mic_checker]

willst du komplett alles selber programmieren oder suchst du bestehende lib's ?

Falls du lib's suchst:
www.javalinkbase.de

 

[_Andreas_]

für die Graphvisualisierung benutze ich Touchgraph (www.touchgraph.com) bzw. Prefuse (sourceforge projekt).

Die haben beide verschiedene Datenmodelle, welche sie als Input für ihre Visualisierung benötigen, also ich muss sie mit ihren entsprechenden "Inputobjekten" füttern.

Ich möchte dann zusätzlich zu den beiden Graphvisualisierungen auch noch eine Baumkomponente anbieten (eben eine aus Swing bzw. SWT, da gibt es ja welche dafür), diese wollen natürlich auch ihre eignen ContenProvider (also InputObjekte).

Also benutze ich hier nur die bestehenden libs.

Was ich mich frage ist jetzt nur:

Wie kann ich diese ganzen Libs und ihre verschiedenen Datenmodelle miteinander kombinieren?

Mir fehlt ja irgendwie im Moment noch eine "Schicht" wenn man so will, weil es im moment ja so ausschaut:


Views (Graphview, Baumview)
^
|
???????????????????
(Welche Klasen brauche ich hier, wie stell ich das an, dass ein gemeinsames "basisdatenmodell" genutzt wird?)
^
|
Infos in Datenbank



Vesteht ihr was ich meine?

 

[Roar]

bau einen wrapper, der deine daten aufnimmt und ein model interface von beiden libraries implementiert. dann gibst du deinen wrapper sowohl dem tree als auch dem graphen als model. soltle klappen.

also in etwa sowas:

class UniversalDataModel implements TreeModel, AnyGraphModel {

   private Collection daten = ...;

   public Object getTreeValueBlabla() { .. }

   public Object getGraphValueBblabla() { ... }
}

 

[AlArenal]

Zunächst schreibst du dir eine Klasse, z.B. "NetObject", die auf der Datenebene deinen Nodes entspricht. Sind deine Kanten einfach nur Beziehungen und enthalten neben einem evtl. Kantengewicht keine weiteren Infos oder Funktionalitäten, wirst du für sie vermutlich keine eigene Klasse benötigen.

NetObject versiehst du mit Methoden wie "NetObject getParent()", " int getChildCount()", "NetObject getChild(int index)", ... Für die spätere Implementierung eines TreeModels musst du dann nicht mehr viel machen und kannst dessen Methoden einfach auf die jeweiligen Instanzen umleiten.

Beim Einlesen erzeugst du nun Instanzen von NetObject und packst diese in eine Collection (z.B. ArrayList). Ein einfaches TreeModel auf dieser Basis ist recht einfach zu entwickeln (s.o.).

Für die Anbindung einer Graphlib müsste man nun deren Aufbau kennen. prefuse beispielsweise ist ganz anders aufgebaut als JGo oder JGraph. Ich selbst arbeite mit JGo (kommerziell) und versuche mich nebenher ein wenig mit prefuse zuu beschäftigen.

In JGo sieht es so aus, dass du ein JGoDocument hast, in welchem dann die JGoNodes, JGoLinks, also alle visuellen Komponenten eines Graphen drin sind, die in einem JGoView dargestellt werden. Ähnlich sieht es, wenn ich mich recht erinnere, auch in JGraph aus.

Wenn alle deine Daten eh in einem einzigen Baum passen, benutzt du ein TreeModel als zentrale Datenstruktur. Für die Anbindung der Graphlib schreibst du dir einen Adapter, der auf das zentrale TreeModel (am besten als Singleton ausführen) einen TreeModelListener registriert. Änderungen im Tree bekommt der Adapter nun automatisch mit (die Implementierung der ganzen Event-Klamotten im Model kann etwas nervtötend sein) und in dem Adapter hängst du dich zeitgleich an das Model deiner Graphlib (JGODocument bei JGo, in JGraph gibts glaub ich was analoges dazu) und aktualisierst diesen entsprechend.

Das Ganze kann man natürlich auch rückwärts machen, so dass Änderungen der Daten im Graph vom Tree übernommen werden.

Hab das alles schonmal durch und es hat sich als nützlich erweisen ein zentrales Singleton zu haben, dass ein TreeModel ist und die Jtrees nicht direkt darauf arbeiten zu lassen, sondern über das zentrale Model noch andere Models zu stülpen, die nochmal Daten und Events filtern. So kann in einem Tree nur einen Ausschnitt aus dem gesamten Baum darstellen und nahezu beliebig filtern.

ZUm FIltern siehe auch diesen noch nicht ganz fertigen Artikel von mir: http://wiki.alexander-langer.de/index.php/JTree:_Gefilterte_Anzeige

 

[_Andreas_]

Vielen Dank euch beiden!

@Roar: Die Interfaces müsste ich bei deinem Vorschlag dann auch selber schreiben, oder?

Obwohl eigentlich nicht. JTree hat ja z.b. Interfaces die für den ContentProvider implementiert sein müssen. Diese könnte ich ja dann in der universellenDatenstruktur implementieren.
Leider weiß ich nicht ob es solche Interfaces für Touchgraph und Prefuse gibt (weißt du das vieleicht AlArenal?), da muss ich mal schauen.


@AlArenal:
Ich brauche auch zu den Links noch eine Klasse, da ich mit diesen noch Metainfos anzeigen lasse, aber das macht ja prinzipiell nichts aus.
Dein Vorschlag hat durchaus seinen Reiz, nur bin ich ein bisschen zögerlich, weil du ja für die Datenstruktur des Baumes ein JTree Interface implementierst. Das gehört ja eigentlich zur Oberflächenbibliothek und nicht zu den Datenstrukturen an sich. Verletzt man damit nicht ein wenig die Prinzipien der Schichtentrennung?
Ich habe auch keinen hierarchischen Graphen sondern einen mit Zyklen also wäre es ja so, dass wenn ich meine Infos in eine Baumstruktur schiebe die Informationen redundant abgelegt werden, oder?
Dann wäre es aber nicht so praktisch die dann in den Graphen zu schieben... oder ist hier mein Gedankengang falsch?

Hmm... ist es dann noch praktikabel für mich ein TreeModel als zentrale Datenstruktur zu nehmen?

Das restliche Vorgehen dass du mir geschildert hast, könnte ich ja auch für eine andere (eigensdefinierte) zentrale Datenstruktur verwenden, oder? Ich meine natürlich gestetz dem Falle, das es möglich für eine eigens kreierte Datenstruktur auch einen Listener für die GraphLibs zu implementieren. Geht das?



Vielen Dank euch beiden nochmal für den Input. Ich hoffe ihr habt nochmal lust mir zu antworten.

 

[AlArenal]

@AlArenal:
Ich brauche auch zu den Links noch eine Klasse, da ich mit diesen noch Metainfos anzeigen lasse, aber das macht ja prinzipiell nichts aus.

Nein, ist im Grunde nur Fleißarbeit.

Dein Vorschlag hat durchaus seinen Reiz, nur bin ich ein bisschen zögerlich, weil du ja für die Datenstruktur des Baumes ein JTree Interface implementierst. Das gehört ja eigentlich zur Oberflächenbibliothek und nicht zu den Datenstrukturen an sich. Verletzt man damit nicht ein wenig die Prinzipien der Schichtentrennung?

Falsch, ich implementiere ein TreeModel-Interface und das gehört nunmal zum M in MVC

Ich habe auch keinen hierarchischen Graphen sondern einen mit Zyklen also wäre es ja so, dass wenn ich meine Infos in eine Baumstruktur schiebe die Informationen redundant abgelegt werden, oder?

Wenn du Zyklen hast, ist ein TreeModel als zentrale Datenstruktur in der Tat ungeeignet. Du bräuchtest dann was allgemeineres und könntest daran evtl. in Einzelfällen ein TreeModel per Adapter andocken um einen Teil der Daten darzustellen.
Es gibt zwei Standardwege einen Graphen auf der Datenebene zu repräsentieren. Zum einen via Adjazenzliste und zum anderen via Adjazenzmatrix. Ersteres kann man einfach z.B. mittels einer Hashtable abbilden und letzteres über ein zweidimensionales Feld oder ein TableModel. Die Matrix hat den Nachteil dass die Anzahl ihrer Elemente quadratisch zur Anzahl der Knoten ist.

Je nachdem wie deine Daten aufgenaut sind, wirst du mit einer "Standard-Datenstruktur" allein nicht weiterkommen. Ich habe z.B. auch ein Visualisierungstool für Prozesslandschaften entwickelt. Da neben der hierarchischen Struktur der Prozesslandschaft auch noch jeder Prozess eine beliebige Anzahl von Prozessen als Input oder Output haben kann, ist die Visualisierung hier ebenfalls nicht ganz trivial.
Am Ende habe ich mir eine Klasse gestrickt, die die Prozessdaten nach dem Einlesen aufbereitet. Intern beherbergt die Klasse Adjazenzlisten und Maps um wiederkehrende Abfragen bei der Visualisierung zu beschleunigen.

Ich denke etwas ähnliches könntest du auch machen. Beim Einlesen legst du Instanzen deiner Knoten- und Kanten-Klassen an und legst die in Listen ab. Auf Basis dieser Listen erzeugst du deine weiteren benötigten Datenstrukturen. Das Ganze kapselst du in einer Klasse. Wenn du für bestimmte Anwendungsfälle ein TreeModel oder einen Adapter für deine Graphlib brauchst, lässt du dir diese am besten in der Datenklasse erzeugen. Wenn du diese nun noch mit den passenden Interfaces ausstattest hast du eine zentrale Datenklasse, auf die alles zugreift und die Synchronisation aller Ansichten automatisiert.
Ist mitunter ein wenig knifflig, aber macht Spaß

Dann wäre es aber nicht so praktisch die dann in den Graphen zu schieben... oder ist hier mein Gedankengang falsch?

Ich hab mir die Klassen in prefuse noch nicht richtig angesehen, nur mal das Tutorial und andere Sachen in Ruhe durchgelesen und ne kurze Tech-Demo geschrieben, die prefuse an unsere Prozessdaten ankoppelt (damit ich Cheffes was zeigen konnte). Möglicherweise kannst du auch auf Basis der Klassen aus der Model-Schicht von prefuse ein zentrales Model entwerfen. Musst du dir mal anschauen. Jeffrey Heer braucht zwar manchmal nen Tag bis er auf E-Mail antwortet, ist aber ein ganz netter Geselle, der sogar noch ein paar Brocken Deutsch spricht und hier schon rumgetourt ist

Hmm... ist es dann noch praktikabel für mich ein TreeModel als zentrale Datenstruktur zu nehmen?

Eher nicht. Ich war im ersten Post von deiner ursprünglichen Aussage ausgegangen und hatte angenommen, deine Daten wären auch tatsächlich entsprechend strukturiert.

Das restliche Vorgehen dass du mir geschildert hast, könnte ich ja auch für eine andere (eigensdefinierte) zentrale Datenstruktur verwenden, oder? Ich meine natürlich gestetz dem Falle, das es möglich für eine eigens kreierte Datenstruktur auch einen Listener für die GraphLibs zu implementieren. Geht das?

Das muss auf jeden Fall gehen. Die Graphlibs arbeiten ja auch alle durchweg auf basis von MVC. Eine View-Komponeten zeigt die Daten aus der Model-Komponenten an. In den Details differenzieren sie sich teils stark, aber grundsätzlich funktionieren deren Views ja auch nur indem sie sich als Listener am Model registrieren, um bei Änderungen die Anzeige zu aktualisieren. Andersrum kann man sich auch an den mir bekannten View-Komponenten als Listener registrieren, um auf View-Events zu lauschen, wie sie bei User-Interaktion mit dem View/dem Graph ausgelöst werden. Musst du im EInzelfall mal nen Blick in die jeweiligen APIs werfen, zur Not kannste die Klassen der Graphlibs ja auch um benötigte Funktionalität erweitern.

 

[_Andreas_]

Vielen Dank für die aufschlußreiche Antwort AlArenal!!

Falsch, ich implementiere ein TreeModel-Interface und das gehört nunmal zum M in MVC

jo, stimmt eigentlich

Es gibt zwei Standardwege einen Graphen auf der Datenebene zu repräsentieren. Zum einen via Adjazenzliste und zum anderen via Adjazenzmatrix. Ersteres kann man einfach z.B. mittels einer Hashtable abbilden und letzteres über ein zweidimensionales Feld oder ein TableModel. Die Matrix hat den Nachteil dass die Anzahl ihrer Elemente quadratisch zur Anzahl der Knoten ist.

Danke für diesen Hinweis.

Ich denke etwas ähnliches könntest du auch machen. Beim Einlesen legst du Instanzen deiner Knoten- und Kanten-Klassen an und legst die in Listen ab. Auf Basis dieser Listen erzeugst du deine weiteren benötigten Datenstrukturen.

Ok, dann habe ich eine Klasse die für das Einlesen zuständig ist. Dort erschaffe ich die Listen für die Knoten und Kanten. Danach übergebe ich diese Listen in meine zentrales Datenobjekt (welches ich mal "GraphModel" nenne).

Das Ganze kapselst du in einer Klasse

Also den Einleseprozess, oder? Ich brauche ja 2 verschiedene Klassen für den Einleseprozess und für mein "GraphModel".
Hinzu kommen dann noch 2 Klassen für meine Kanten und Knoten (und vieleicht noch diverse andere Klassen an die ich im Moment aber nicht denken will).

Wenn du für bestimmte Anwendungsfälle ein TreeModel oder einen Adapter für deine Graphlib brauchst, lässt du dir diese am besten in der Datenklasse erzeugen. Wenn du diese nun noch mit den passenden Interfaces ausstattest hast du eine zentrale Datenklasse, auf die alles zugreift und die Synchronisation aller Ansichten automatisiert.

Hmm, wie meinst du das mit erzeugen? Es gibt doch nur eine zentrale Datenklasse, also das GraphModel (wäre dann also als Singelton implementiert).
Wenn ich in diesem GraphModel die Interface für das TreeModel und die jeweiligen GraphLibs implementiere, dann kann ich doch diese eine Instanz des GraphModels immer direkt als Input an die GraphLibs bzw. den Tree übergeben.
Ich verstehe nicht wie du das mit dem erzeugen meinst.


Glaubst du es empfiehlt sich für jede GraphLib / Tree einen eigenen Adapter zu schreiben?
Oder soll ich alle Interfaces in der zentralen Datenklasse GraphModel implementieren? Ein eigener Adapter wäre vieleicht sauberer, oder?

Vieleicht hast du ja nochmal lust mir zu antworten.
Deine bisherigen Antworten haben mir auf jeden Fall sehr geholfen!

 

[AlArenal]

DatenEinlesen -> GraphModel [Singleton]

Soweit sind wir uns schonmal einig.

Wie du schon selbst überlegt hast, halte auch ich es für sauberer die Schnittstelle zwischen deinem GraphModel und einem TreeModel in eine eigene Adapterklasse auszulagern, gleiches gilt für die Anbindung an GraphLibs. Das macht es etwas übersichtlicher wenn neue Adapter hinzukommen und einfacher wenn welche mal rausfliegen sollten und entspricht eher dem Konzept der Kapselung.

Wofür diu im einzelnen alles Adapter benötigst, weißt du selbst am besten. Ich weiß ja nicht was du später alles in einem JTree darstellen möchtest. Wenn du mehrere unterschiedliche Ansichten über JTree realisierst musst du slebst mal sehen ob du jeweils nen Adapter schreibst oder vielleicht einen Adapter so parametrisieren kannst, dass er für alles herhalten kann. Das Gefühl dafür bekommst du mit der Zeit von selbst, wenn dein erster Adapter läuft. Evtl. würde es sich auch anbieten einen generischen TreeModelAdapter zu basteln und auf den noch weitere Adapter für die unterschiedlichen JTree-Ansichten aufzusetzen. Möglichkeiten gibts da viele, aber das hängt eben immer alles von deinen Anforderungen ab.

Was die Dapter zu den Graphlibs angehst sind die alle so speziell, dass du für jede nen Adapter brauchen wirst. Ich weiß ja nicht wieviele verschiedene Libs du da verwenden willst. Bei JGo und ich glaube auch bei JGraph hast du im Model bereits die Instanzen der visuellen Nodes und Links drin, wogegen prefuse zwischen seinen eigenen Datenobjekten und ihren grafischen Repräsentationen unterschiedet, also noch eine Abstraktionseben mehr hat.

Was du in dein GraphModel so alles treibst, wird sich mit der Zeit ergeben. Ich habe z.B. folgende Situation in meinem Bereich:

Ein Objekt kann andere Objekte als Input und Output definiert haben. Nun kann es vorkommen dass Node A einen Node B als Output definiert hat, Node B hat aber Node A nicht als Input definiert. Das sind so Sachen die über die Farbe der Kanten (dient bei mir also als Kantengewicht) visualisiert werden. Jeder Node kann dabei beliebig viele Inputs und Outputs haben und damit fallen die klassischen Adjazenzlisten und -matrizen schonmal weg als Möglichkeit die Kanten darzustellen.

So habe ich bei mir in der Datenklasse Hashtables, wo die Knoten als Key benutzt werden und als Value eine Map beinhaltet, die die verbundenen Knoten als Key und das Kantengewicht (in meinem Fall über einen Integer, bei dir dann über dein Kantenobjekt) als Value enthalten.

Knoten -> Map( (Knoten -> Kante), (Knoten -> Kante), ... )
Knoten -> Map( (Knoten -> Kante), (Knoten -> Kante), ... )
...

Man muss da ein wenig kreativ sein. Im ersten Schritt setzt man sowas gerne als Brute-Force-Algorithmus um, bis dann die Performance so in die Knie geht, weil man alle Nase lang über alle Objekte iteriert. Dann ist es an der Zeit sich ein paar etwas intelligentere Datenstrukturen zu basteln, die gewisse immer wieder benötigte Infos schon bereit halten, so dass ich sie nur einmal erzeugen muss.

Ich muss aber gestehen auch kein Mathe-Ass zu sein. Für einige Sachen mag es spezielle Algos geben, die ich nicht kenne, die das ganze nochmal beschleunigen könnten. Naja.. nobody's perfect

 

[AlArenal]

P.S.:
Wenn ich sehe bei welchen Datenmengen prefuse noch klasse Perfoamcne bringt (weil intern ja auch gecached wird) würde ich auch in Betracht ziehen die Datenschicht von prefude als Fundament zu benutzen. Müsste mir auch mal anschauen wie das mit dem Caching funzt, ich stoße hier nämlich auch ab und an an meine Grenzen, wobei es auch sein kann dass die hier bei uns eingesetzte Graphlib der Pferdefuß ist.. muss ich mal profilen...

Gerade das Renderer-Konzept in prefuse ist absolut genial, weil man beispielsweise in Abhängigkeit von der Zoomstufe die Nodes ganz anders darstellen und mit Infos füttern kann, was die vom User gefühlte Geschwindigkeit beim Scrollen und bei Interaktion deutlich erhöht.

In der Lib die ich hier sonst nutze enthält jeder Node ne paint()-Methode die man überschreiben muss.. Ist eher ne Lib um visuell was zu basteln als um viele Daten zu visualisieren...