Open Source Java Graph Visualisation Overview

Manageability - Open Source Graph or Network Visualization Written in Java

Graph Visualisierung Gephi

 

http://gephi.org/

Lizenz GPL v3

Datasets unter https://wiki.gephi.org/index.php?title=Datasets

Quickstart / HowTos unter http://gephi.org/users/

Graph Editor yEd und Graph - Visualierungstools

 

http://www.yworks.com/de/products_yfileshtml_about.html

http://www.yworks.com/de/products_yed_about.html

(s. http://www.yworks.com/de/products_yfiles_practicalinfo_gallery.html)

Java Graph Toolkit Lib

Java Graph Bibliothek jGrapht

Aktuelle Version 0.8.2 unter http://www.jgrapht.org/





mit einigen Basisalgorithmen

Blog zum Thema Graph Theorie

The Chinese Postman Problem | Graph Theory

GOBLIN: A Graph Object Library for Network Programming Problems

GOBLIN Download Page

Löst die viele Graph-Probleme, windows und Linux - Version, leider nur unter cygwin in windows zu kompilieren.

Graph Visualisierung .net

http://www.graphviz.org/Download_windows.php

Graph Visualisation Libs

- Canviz, Graphviz rendered on a HTML canvas with JavaScript Online demonstration

- Cytoscape Bioinformatics analysis and visualization tool

- Gephi

- iGraph

- JUNG visualization in Java, can be used with a mapping layer over Gremlin

- Ondex

- Prefuse in Java

- Ubigraph

- Thread on large scale visualization tools for RDF

- NodeXL Excel based visualization for graphs

neo4j Graph-NoSQL-DB

• Film über neo4j (lang 1h, langsam, informativ) http://nosql.mypopescu.com/post/342947902/presentation-graphs-neo4j-teh-awesome

• components.neo4j.org
• http://wiki.neo4j.org/content/Spatial_algos_and_GIS

http://blog.notdot.net/

Google Treffer: dima java distanzmatrix

Witzige Sache: bei der Googlesuche nach "dima java distanzmatrix" gibt es keine Treffer... auch "dima distanzmatrix" gibt nur 10 Treffer. Dabei ist dima doch die einfachste Abkürzung für Distanzmatrix.

Java Graph - Framework JUNG

Framework for the modeling, analysis, and visualization of graphs in Java

unterstützt Graphen

• gerichtet unf ungerichtet
• BFS
• Dijkstra
• Visualisierung

Basiert auf

• Commons-Collections API
  http://jakarta.apache.org/commons/collections/
• CERN Colt API (1.2.0)
  http://dsd.lbl.gov/~hoschek/colt/
  matrix operations, statistics

Doku:
http://jung.sourceforge.net JUNG Home
http://jung.sourceforge.net/presentations/JUNG_M2K.pdf
http://jung.sourceforge.net/doc/api/index.html?overview-summary.html JUNG 2.2 API

Wartezeiten bei zyklischen Bedienungen an Kanten

Bei der Betrachtung von periodischen Kantenproblemen gibt es einen Planungshorizont H. In H sollen Kanten / Jobs erledigt werden. Bis zur nächsten Bedienung der Kante gibt es dann ein Zeitfenster als Abstand zu der letzten Bedienung: einen Minimalen Abstand minspan (u) und einen maximalen Abstand maxspan(u) einer Kante u. Daraus ergibt sich eine Kombination comb(u) der möglichen Bedientage.
Bei einem Planungshorizont H von einer Woche gibt es np = 7  Perioden : { 1,2,3,4,5,6,7=np}, um täglich Bedienung durch zuführen, oder bei einer 2xwöchentlichen Bedienung einer Kante kann z.B. comb(u)  = {1,4} oder {2,5} sein. Da aber an Samstagen und Sonntagen keine Bedientage sind reduzieren sich die Möglichkeiten:

• 1 mal pro Woche: {1},{2},{3},{4},{5} // Mo, ... Fr
• 2 Mal pro Woche: {1,4}, {2,5}
• 5 mal pro Woche: {1,2,3,4,5} // täglich

Periodizität an den Kanten

Periodische Kantenprobleme

An m Kanten (Straßenabschnitten) in einem gerichteten Graph G  gibt es einen bestimmten Planungshorizont H mit einer Anzahl von np Perioden.
Jeder Job oder Kante hat einen bestimmte Frquenz. Dabei ist bei den ungerichteten Kanten darauf zu achten, dass nicht nur die Kosten einmalig für beide Kanten u und v anfallen, sondern auch die Frequenz f(u) gleich ist (f(u)  = f(inv(u)). So muss eine Kante u 1<= f(u) <= np mal im Planungshorizont H bedient werden.
Die Summe aller Frequenzen ns im Planungshorituont H zerteilt das Problem in bestimmte Tagesrhytmen. Unglücklicherweise können die Bedientage nicht willkurlich gewählt werden, sondern sie sollen auch Abstandsregeln einhalten; somit sollen 2 Bedientage in der Persiode wöchentlich nicht z.B. Montag-Dienstag stattfinden, sondern dazwischen mindestens ein Bedienpausentag liegen (z.B. Montag- Donnerstag).

Strafen für schlechte Abbiegemanöver

Strafen für schlechte Abbiegemanöver

Ein Weg, um in routingfähigen Graphen unvorteilhafte Abbiegemanöver darzustellen, ist besteht darin zwischen zwei Kanten Abbiegestrafen zu hinterlegen.
Das Betrifft Linksabbiegungen bei Ampeln oder sog. U-Turns, die sich mit größeren Fahrzeugen schwer durchführen lassen.



Bei dem o.a. Beispiel sind von der eingehenden Kante u vier verschiedene, zulässige Abbiegungen zu den Kanten v1,...v4 (turn (u,v1), turn (u,v2), ...) möglich .
Abbiegestrafen würden hier wegen des U-Turns zwischen u und v1 mit der Straf-Funktion pen (u,v1) abgebildet.
Um von einer Kante u zu einer Kante v einen zulässigen Pfad µ zu bekommen, werden nur zulässige Abbigemöglichkeiten (turns) in Betracht gezogen.
In der Liste der zu bedienenden Kanten µ werden bei der Berechnung der Kosten die Kosten der Quellkante u und die Kosten der Senke v nicht mit berücksichtigt.

Verbotene Abbiegemönover wenden in einer m x m Distanzmatrix D zwischen den m Kanten berücksichtigt, so dass sich die Distanzfunktion d(u,v) die kürzeste, zulässige Entfernung zwischen den Kanten u und v berechnet. Die Distanzmatrix pro Pfad kann via Dijkstra in O( m log m) berechnet werden.

	v1	v2	v3	v4
u	U-Turn	L-Turn	0	0

Zusätzlich sind noch die Regiefahrten ins Revier und zum Depot zu berücksichtigen.

Bedienenung einer Straße

 Bedienung einer Straße

Graph zur Bedienenung einer Straße

Die Modellierung eines Gaphen der wirklichen Welt:
Nodes N und Arcs A bilden einen gerichteten Graph G = (N,A). Jede gerichtete Kante u aller m Kanten aus A kann durchfahren werden von der Quelle b(u) zur Senke e(u).
Jede Kante hat einn Bei einer Leerfahrt über die Kante u entstehen Kosten c(u). Jede Kante kann ein Andorderung (Job) haben.
Die Teilmenge der Kanten mit Anforderungen im Graphen G heissen R, die einzelne Anforderung einer Kante u aus R somit r(u).

Die gerichteten Kanten u2 (b->a)  und u3 (a->b) können oBdA wie Einbahnstraßen zusammengefasst werden. Bei jeder Duchfahrt werden die Anforderungen r1 und r2 auf beiden Seiten bedient.
Die ungerichtete Kante u1 ( a->b, b->a) bedient beide Seiten in beiden Richtungen. Der Job an dieser Straßen kann also in beiden Richtungen erledingt werden.
Deshalb gibt es zwei Kanten v1 und v2 im Graphen G mit Verweisen v1 = inv(v2) und v2 = inv(v1) zueinander. Wenn die Kante nicht "Windy" ist, so sind die Bedienkosten in beiden Richtungen gleich r(v1) = r(v2). Im Weiteren ist darauf zu achten, dass es sich bei den Kanten v1 und v2 aber nur um eine Anforderung r(u1) an der ungerichteten Kante u1 handelt, wenn inv(v1) existiert.

 (C) 2010 Volker Engels, www.softwareengel.de

Blog mit Grafik aus Google Draw

Eine Grafik einzubinden war bisher immer mit mehreren Schritten verbunden. Der Grapg-Editor von Google lässt einfache Abbildungen einfach erstellen und auch für die öffentlichkeit Referenzieren :
<img src="http://docs.google.com/drawings/pub?id=1geiSMs5zP6ZJsWLRsCCunO8mXvfWnQj6Rxa0RutXC4U&amp;w=960&amp;h=720">
Und so sieht das dann aus:

Java Graph - Framework JUNG

Framework for the modeling, analysis, and visualization of graphs in Java

unterstützt Graphen

• gerichtet unf ungerichtet
• BFS
• Dijkstra
• Visualisierung

Basiert auf

• Commons-Collections API
  http://jakarta.apache.org/commons/collections/
• CERN Colt API (1.2.0)
  http://dsd.lbl.gov/~hoschek/colt/
  matrix operations, statistics

Doku:
http://jung.sourceforge.net JUNG Home
http://jung.sourceforge.net/presentations/JUNG_M2K.pdf
http://jung.sourceforge.net/doc/api/index.html?overview-summary.html JUNG 2.2 API

Beispiele der Angewandten Graphtheorien

http://www.ics.uci.edu/~eppstein/geom.html

http://www.ics.uci.edu/~eppstein/junkyard/all.html