Gute Java Graph Algorithmus Bibliothek? [geschlossen]

237

Hat jemand gute Erfahrungen mit Java-Bibliotheken für Graph-Algorithmen gemacht. Ich habe JGraph ausprobiert und fand es in Ordnung , und es gibt viele verschiedene in Google. Gibt es welche, die Leute tatsächlich erfolgreich im Produktionscode verwenden oder empfehlen würden?

Zur Verdeutlichung suche ich keine Bibliothek, die Diagramme / Diagramme erstellt, sondern eine, die bei Diagrammalgorithmen hilft, z. B. Minimum Spanning Tree, Kruskals Algorithmusknoten, Kanten usw. Idealerweise eine mit einigen guten Algorithmen / Daten Strukturen in einer schönen Java OO API.

Nick Fortescue
quelle

Antworten:

108

Wenn Sie JGraph verwendet haben , sollten Sie einen Versuch geben JGraphT die für Algorithmen ausgelegt ist. Eine seiner Funktionen ist die Visualisierung mit der JGraph-Bibliothek. Es ist noch entwickelt, aber ziemlich stabil. Ich habe vor einiger Zeit die Komplexität von JGraphT-Algorithmen analysiert. Einige davon sind nicht die schnellsten, aber wenn Sie sie selbst implementieren und Ihr Diagramm anzeigen müssen, ist dies möglicherweise die beste Wahl. Die Verwendung der API hat mir sehr gut gefallen, als ich schnell eine App schreiben musste, die an Grafiken arbeitete und diese später anzeigte.

Bibix
quelle
JGraph verfügt jetzt über ein Analysepaket, das eine Reihe von Analysefunktionen enthält: jgraph.github.com/mxgraph/java/docs/index.html .
David
63

Zusammenfassung:

Mansu
quelle
Viele davon sind extrem kompliziert ... Mit Fabrikmethoden und so weiter. Ich brauche nur etwas Einfaches, um mich auf ein Interview vorzubereiten. Irgendwelche Ideen?
SoftwareSavant
4
Wenn diese kompliziert sind, als welche Art von Job Sie suchen
Maytham-ɯɐɥʇʎɐɯ
1
Graph-Algorithmen werden hier erklärt geeksforgeeks.org/graph-data-structure-and-algorithms mit einfachem Code
mosh
40

In JGraphT finden Sie eine sehr einfache und leistungsstarke Java- Grafikbibliothek , die ziemlich gut gemacht ist und sich, um Verwirrung zu vermeiden, von JGraph unterscheidet . Einige Beispielcodes :

UndirectedGraph<String, DefaultEdge> g =
        new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

    String v1 = "v1";
    String v2 = "v2";
    String v3 = "v3";
    String v4 = "v4";

    // add the vertices
    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);

    // add edges to create a circuit
    g.addEdge(v1, v2);
    g.addEdge(v2, v3);
    g.addEdge(v3, v4);
    g.addEdge(v4, v1);
Joe Liversedge
quelle
Dies ist eine großartige Demo hier github.com/jgrapht/jgrapht/wiki/DirectedGraphDemo
Jemand irgendwo
37

JUNG ist eine gute Option für die Visualisierung und verfügt auch über einen ziemlich guten Satz verfügbarer Diagrammalgorithmen, einschließlich verschiedener Mechanismen für die zufällige Erstellung, Neuverdrahtung von Diagrammen usw. Ich habe auch festgestellt, dass es im Allgemeinen ziemlich einfach ist, es zu erweitern und bei Bedarf anzupassen .

Kai
quelle
Pakete hep.aida. * Sind LGPL ( acs.lbl.gov/software/colt/license.html ). Dies wird über Colt ( jung.sourceforge.net/download.html) importiert ) . Dies verhindert, dass JUNG in Projekten unter dem Dach von ASF und ESF eingesetzt wird. Vielleicht sollte man die Github-Gabel github.com/rortian/jung2 verwenden und diese Abhängigkeit entfernen. github.com/rortian/jung2/commit/… spiegelt das letzte CVS-Commit wider. Die aktuellen Commits scheinen die Visualisierungsfunktionen zu entfernen.
Koppor
Es gibt keine Veröffentlichung seit 2010, ich denke, dass dieses Projekt aufgegeben wird
Yacino
14

Apache Commons bietet Commons-Graph . Unter http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/ kann die Quelle überprüft werden. Die Verwendung der Beispiel-API erfolgt auch im SVN . Unter https://issues.apache.org/jira/browse/SANDBOX-458 finden Sie eine Liste der implementierten Algorithmen, die auch mit Jung, GraphT, Prefuse und jBPT verglichen werden

Google Guava, wenn Sie nur gute Datenstrukturen benötigen.

JGraphT ist eine Graphbibliothek mit vielen implementierten Algorithmen und (meiner Meinung nach) einem guten Graphmodell. Helloworld Beispiel . Lizenz: LGPL + EPL.

JUNG2 ist auch eine BSD-lizenzierte Bibliothek mit einer ähnlichen Datenstruktur wie JGraphT. Es bietet Layouting-Algorithmen, die derzeit in JGraphT fehlen. Das letzte Commit stammt aus dem Jahr 2010 und aus Paketenhep.aida.* sind LGPL (über die Colt-Bibliothek , die von JUNG importiert wird ). Dies verhindert, dass JUNG in Projekten unter dem Dach von ASF und ESF eingesetzt wird. Vielleicht sollte man die Github-Gabel verwenden und diese Abhängigkeit entfernen. Commit f4ca0cd spiegelt das letzte CVS-Commit. Die aktuellen Commits scheinen die Visualisierungsfunktionen zu entfernen. Commit d0fb491c fügt a hinzu .gitignore.

Prefuse speichert die Diagramme unter Verwendung einer Matrixstruktur, die für spärliche Diagramme nicht speichereffizient ist. Lizenz: BSD

Eclipse Zest verfügt über integrierte Algorithmen für das Diagrammlayout, die unabhängig von SWT verwendet werden können. Sehen org.eclipse.zest.layouts.algorithms . Die verwendete Diagrammstruktur ist die von Eclipse Draw2d , bei der Knoten explizite Objekte sind und nicht über Generics injiziert werden (wie dies in Apache Commons Graph, JGraphT und JUNG2 der Fall ist).

koppor
quelle
12

http://neo4j.org/ ist eine Diagrammdatenbank, die viele Diagrammalgorithmen enthält und besser skaliert als die meisten In-Memory-Bibliotheken.

Jonathan Hendler
quelle
1
Gibt es einen Neo4J-Client (Java-Client), auf dem Sie ihn visualisieren können?
Vishrant
10

In einem Universitätsprojekt habe ich mit yFiles von yWorks herumgespielt und festgestellt, dass es eine ziemlich gute API hat.

Turismo
quelle
Ich habe yFiles zur Visualisierung von Abhängigkeiten zwischen Datenelementen verwendet (als Teil einer kommerziellen Softwareplattform). Ich habe eigentlich keine Graph-Analyse-Algorithmen verwendet, aber überprüfe, ob das y.algo-Paket das enthält, was du brauchst: yworks.com/products/yfiles/doc/api
Jonik
2
yFiles ist keine Open Source, bietet aber kommerzielle Lizenzen an
koppor
9

Schauen Sie sich Blueprints an :

Blueprints ist eine Sammlung von Schnittstellen, Implementierungen, Erweiterungen und Testsuiten für das Datenmodell des Eigenschaftsgraphen. Blaupausen sind analog zu JDBC, jedoch für Diagrammdatenbanken. Innerhalb des Open-Source-Software-Stacks TinkerPop dient Blueprints als grundlegende Technologie für:

Pipes : Ein fauler Datenfluss-Framework

Gremlin : Eine Graph-Traversal-Sprache

Frames : Ein Object-to-Graph-Mapper

Ofen : Ein Paket mit Graphalgorithmen

Rexster : Ein Grafikserver

Alex
quelle
7

JDSL (Data Structures Library in Java) sollte gut genug sein, wenn Sie sich mit Graph-Algorithmen beschäftigen - http://www.cs.brown.edu/cgc/jdsl/

mr.sverrir
quelle
Danke dafür, ich würde nie darauf stoßen. Benutzt du es?
Nick Fortescue
1
Ja, ich benutze es. Ich habe vor vielleicht 4 Jahren angefangen, es zu benutzen. So weit so gut, ich wünschte nur, es gäbe auch einen Port für .NET.
mr.sverrir
Leider scheint die Seite jdsl.org jetzt eine Spam-Seite zu sein.
Ross Judson
1
Ich habe den Link im ursprünglichen Beitrag aktualisiert. Vielen Dank.
mr.sverrir
5

Zur Visualisierung hatte unsere Gruppe einige Erfolge mit Prefuse . Wir haben es erweitert, um architektonische Bodenplatten und Blasendiagramme zu handhaben, und es hat sich nicht allzu sehr beschwert. Sie haben auch ein neues Flex-Toolkit namens Flare herausgebracht, das eine sehr ähnliche API verwendet.

UPDATE: Ich muss dem Kommentar zustimmen, am Ende haben wir viele benutzerdefinierte Funktionen geschrieben / um die Einschränkungen der Präfuse herum gearbeitet. Ich kann nicht sagen, dass es besser gewesen wäre, von vorne anzufangen, da wir den Fortschritt vom ersten Tag an mit Prefuse demonstrieren konnten. Auf der anderen Seite, wenn wir eine zweite Implementierung des gleichen Materials durchführen würden, könnte ich Prefuse überspringen, da wir die Anforderungen viel besser verstehen würden.

Jacob Rigby
quelle
Was waren Ihre persönlichen Gedanken mit Prefuse? Bei meinem letzten Job begann ein Projekt, es zu verwenden, endete jedoch mit einer über 90% überarbeiteten (und optimierten, mit neuen Funktionen hinzugefügten) Version von Prefuse.
Thomas Owens
5

Probieren Sie Annas aus, ein Open-Source-Grafikpaket, mit dem Sie sich leicht vertraut machen können

http://annas.googlecode.com

Sam Wilson
quelle
5

Es ist auch gut, davon überzeugt zu sein, dass ein Graph so einfach dargestellt werden kann wie:

class Node {
   int value;
   List<Node> adj;
}

und implementieren Sie die meisten Algorithmen, die Sie selbst interessant finden. Wenn Sie mitten in einer Übungs- / Lernsitzung auf Grafiken auf diese Frage stoßen, ist dies die beste Bibliothek, die Sie in Betracht ziehen sollten. ;)

Sie können auch die Adjazenzmatrix für die meisten gängigen Algorithmen bevorzugen:

class SparseGraph {
  int[] nodeValues;
  List<Integer>[] edges;     
}

oder eine Matrix für einige Operationen:

class DenseGraph {
  int[] nodeValues;
  int[][] edges;     
}
Snicolas
quelle
4

Ich weiß nicht, ob ich es produktionsbereit nennen würde, aber es gibt jGABL .

Hank Gay
quelle
4

Wenn Sie Leistung benötigen, können Sie sich Grph ansehen. Die Bibliothek wird an der französischen Universität und am CNRS / Inria entwickelt.

http://www.i3s.unice.fr/~hogie/grph/

Das Projekt ist aktiv und wird reaktiv unterstützt!

Luc
quelle
0

Wenn Sie tatsächlich nach Diagrammbibliotheken suchen und nicht nach Node / Edge Graph-Bibliotheken, würde ich empfehlen, die Big Faceless Graph Library ( BFG ) zu verwenden. Es ist viel einfacher zu bedienen als JFreeChart, sieht besser aus, läuft schneller, hat mehr Ausgabeoptionen, wirklich keinen Vergleich.

Jacob Rigby
quelle
Sie haben die Frage falsch verstanden: Es geht um die Art von Graphen mit Knoten und Kanten, nicht um die Art mit Torten und Balken.
Amarillion
-1

JGraph von http://mmengineer.blogspot.com/2009/10/java-graph-floyd-class.html

Bietet eine leistungsstarke Software für die Arbeit mit Grafiken (direkt oder ungerichtet). Generiert auch Graphivz-Code, können Sie Grafikdarstellungen sehen. Sie können Ihre eigenen Codealgorithmen in Pakage einfügen, zum Beispiel: Backtracking-Code. Das Paket enthält einige Algorithmen: Dijkstra, Backtracking Minimun Path Cost, ect ..

Bob
quelle