search

truffle-hog / documentation

Description and specification documents for TruffleHog and spp_profinet.
GNU General Public License v2.0
2 stars 1 forks source link

Graphalgorithmen spezifizieren. #17

Closed mlgiraud closed 8 years ago

mlgiraud commented 8 years ago

Wir müssen mindestens 2 Graphalgorithmen beim Namen nennen.

JanSurft commented 8 years ago

Wer hat das mit den Graphalgorithmen überhaupt eingebaut?

JanSurft commented 8 years ago

Ich wäre gar nich darauf gekommen im Vorfeld, die Graphen Representation mit den Graphenalgorithmen zu verknüpfen.

mlgiraud commented 8 years ago

Kann sein, dass ich das da rein hab. Wie würdest du das denn machen? Ich mein die Knoten müssen nach irgendeinem Schema (Algorithmus) angeordnet werden.

JanSurft commented 8 years ago

Na klar... Aber eigentlich ist mir egal wie eine Graphenbibliothek die Konten sortiert :) bzw. Ich weiß nicht was es da für möglichkeiten gibt... Ich wusste auch gar nicht, dass man da genau spezifizieren kann nach welchem Algorithmus der Graph jetzt die Knoten sortiert usw....

mlgiraud commented 8 years ago

Jo gibt halt verschiedene Verfahren, wie das angeordnet werden soll. Ich denke es wär schon sinnvoll dem Nutzer diese Möglichkeit dann auch zu geben, wenn es sie schon gibt. Müssen uns halt einfach nur 2 Beispiele raussuchen und die da rein packen?

JanSurft commented 8 years ago

Aber hat jede Graphenbibliothek die gleichen Darstellungsalgos?

mlgiraud commented 8 years ago

Müssen wir schauen. Wir müssen uns sowieso bald mal einigen, welche Bibliotheken und Sprachen wir für unser Projekt verwenden wollen. Was mich im Moment am meisten beschäftigt, ist die Interprozesskommunikation. Zwischen Java und C ist das nämlich garn nicht mal so trivial.

JanSurft commented 8 years ago

Eigentlich ist das sehr einfach auf Linux:

http://www.jonathanbeard.io/tutorials/CtoJava.html

JanSurft commented 8 years ago

Aber ich finde im Pflichtenheft muss man sich halt noch nicht auf die verwendete Software festlegen...und daher wäre es finde ich schwierig sich schon auf Graphenalgorithmen festzulegen, weil wir gar nicht wissen welche Alogirhtmen am ende verfügbar sein werden.

mlgiraud commented 8 years ago

Das Problem dabei ist nicht, wie wir die Verbindung aufbauen zwischen zwei Prozessen, sondern wie wir effizient die Daten rüberschieben können. Von c zu c prozess könnte man einfach ein struct rüberschicken und das sofort wieder auslesen. Mit Java geht das glaube ich nicht so einfach. Da muss man die Daten dann halt irgendwie serialisieren.

JanSurft commented 8 years ago

Mit java muss man einfach die Daten auslesen... also mit DataInputStream oder ByteBuffer... Aber zurück zum Graphenalgo problem.. :D

JanSurft commented 8 years ago

JUNG ist eine open source BSD lizensierte java graphen bibliothek... Anscheind laut diesem paper genau das richtige um Netzwerkaktivitäten graphisch darzustellen:

http://jung.sourceforge.net/doc/JUNG_journal.pdf

JanSurft commented 8 years ago

Diese Algorthmen gibt es in Jung für das Layout:

http://jung.sourceforge.net/doc/api/index.html -> edu.uci.ics.jung.algorithms.layout

JanSurft commented 8 years ago

Ich würde daraus z.B. gerne den Kamada-Kawai algorithmus verwenden. Der sieht ganz gut aus, bzw. Graphen sehen damit sehr schön geordnet aus.

jundl77 commented 8 years ago

http://www.cytoscape.org/ !

jundl77 commented 8 years ago

Also ich habe mir das nochmal genauer angeguckt. Ich habe noch diese library gefunden zu leicht zu benutzten ist und auch für Projekte wie unsere vorgesehen ist. (Da ist zum Beispiel erklärt wie man die library in eine andere view gut einbindet, und es sind auch Klassen dafür vorhanden.) Alles ist sehr schön und gut dort, die Graphen werden auch gut dargestellt - aber ich habe bislang noch nicht rausgefunden ob man den Graphendarstellungsalgorithmus ändern kann. Auf jeden Fall ist neuste version der library aus 2014, also relativ modern. Hier ist der link. http://graphstream-project.org/

Der große vorteil dieser library ist das sie dafür gemacht ist Graphen dynamisch zu verändern. Bei jung hatte ich gelesen auf stack overflow das manche meinten das Jung probleme mit dynamischer Graphendarstellung hat was für uns natürlich sehr wichtig ist. Ich habe mal ein kleines testprogramm mit dieser graphenlibrary geschrieben - bzw. von deren webseite genommen - und alles funktioniert sehr schön. Ich kann mal die sources auf github hochladen wenn ihr es auch bauen wollt oder ich zeige es euch so morgen.

Auf jeden Fall würde ich vieleicht nochmal überlegen welche library wir nutzten - und welche Algorithmen wir im Pflichtenheft angeben, weil nur an eine Library gebunden zu sein weil sie bestimmte Algorithmen supportet ist ziemlich scheisse. Vorallem ist die neuste version von JUNG aus 2010 - also nicht gerade das neuste.

mlgiraud commented 8 years ago

Ich schau mir beide mal an und versuch anfang nächster woche mal nen Prototypen oder so zusammenzuhacken. Dann schauen wir mal was die jeweils für Vorteile haben.