Bonne bibliothèque d'algorithmes de graphes Java? [fermé]

Quelqu'un at-il eu de bonnes expériences avec les bibliothèques Java pour les algorithmes Graph. J'ai essayé JGraph et je l'ai trouvé correct, et il y en a beaucoup de différents dans google. Y a-t-il des personnes que les gens utilisent réellement avec succès dans le code de production ou recommandent?

Pour clarifier, je ne cherche pas une bibliothèque qui produit des graphiques / diagrammes, je cherche une bibliothèque qui aide avec les algorithmes Graph, par exemple un arbre couvrant minimum, l'algorithme de Kruskal Nodes, Edges, etc. Idéalement une avec de bons algorithmes / données structures dans une belle API Java OO.

Si vous utilisiez JGraph, vous devriez essayer JGraphT qui est conçu pour les algorithmes. L'une de ses fonctionnalités est la visualisation à l'aide de la bibliothèque JGraph. Il est toujours développé, mais assez stable. J'ai analysé la complexité des algorithmes JGraphT il y a quelque temps. Certains d'entre eux ne sont pas les plus rapides, mais si vous allez les implémenter par vous-même et que vous devez afficher votre graphique, cela pourrait être le meilleur choix. J'ai vraiment aimé utiliser son API, quand j'ai rapidement dû écrire une application qui travaillait sur un graphique et l'afficher plus tard.

Résumé:

• JGraphT si vous êtes plus intéressé par les structures de données et les algorithmes.
• JGraph si votre objectif principal est la visualisation.
• Jung , yWorks et BFG sont d'autres choses que les gens ont essayé d'utiliser.
• La préfuse est un non non car il faut en réécrire la majeure partie.
• Google Guava si vous avez besoin uniquement de bonnes infrastructures de données.
• Graphique Apache Commons . Actuellement dormant, mais fournit des implémentations pour de nombreux algorithmes. Voir https://issues.apache.org/jira/browse/SANDBOX-458 pour une liste des algorithmes implémentés, également comparés à Jung, GraphT, Prefuse, jBPT

Consultez JGraphT pour une bibliothèque de graphes Java très simple et puissante qui est assez bien faite et, pour dissiper toute confusion, est différente de JGraph . Quelques exemples de code :

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);

JUNG est une bonne option pour la visualisation, et dispose également d'un assez bon ensemble d'algorithmes de graphiques disponibles, y compris plusieurs mécanismes différents pour la création aléatoire de graphiques, le recâblage, etc. J'ai également trouvé qu'il était généralement assez facile à étendre et à adapter si nécessaire .

Apache Commons propose un graphique commun . Sous http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/ on peut inspecter la source. Un exemple d'utilisation de l'API se trouve également dans le SVN . Voir https://issues.apache.org/jira/browse/SANDBOX-458 pour une liste des algorithmes implémentés, également comparés à Jung, GraphT, Prefuse, jBPT

Google Guava si vous avez besoin uniquement de bonnes infrastructures de données.

JGraphT est une bibliothèque de graphiques avec de nombreux algorithmes implémentés et ayant (à mon avis) un bon modèle de graphique. Exemple de Helloworld . Licence: LGPL + EPL.

JUNG2 est également une bibliothèque sous licence BSD avec une structure de données similaire à JGraphT. Il propose des algorithmes de mise en page, qui manquent actuellement dans JGraphT. Le commit le plus récent date de 2010 et les packages hep.aida.*sont LGPL (via la bibliothèque colt , qui est importée par JUNG ). Cela empêche JUNG d'être utilisé dans des projets sous l'égide de l'ASF et de l'ESF. Peut-être que l'on devrait utiliser la fourchette github et supprimer cette dépendance. La validation f4ca0cd est en miroir de la dernière validation CVS. Les validations actuelles semblent supprimer la fonctionnalité de visualisation. La validation d0fb491c ajoute a .gitignore.

Prefuse stocke les graphiques à l'aide d'une structure matricielle, qui n'est pas efficace en mémoire pour les graphiques clairsemés. Licence: BSD

Eclipse Zest a intégré des algorithmes de présentation graphique, qui peuvent être utilisés indépendamment de SWT. Voir org.eclipse.zest.layouts.algorithms . La structure graphique utilisée est celle d' Eclipse Draw2d , où les nœuds sont des objets explicites et non injectés via des génériques (comme cela se produit dans Apache Commons Graph, JGraphT et JUNG2).

http://neo4j.org/ est une base de données de graphiques qui contient de nombreux algorithmes et échelles de graphiques mieux que la plupart des bibliothèques en mémoire.

Dans un projet universitaire, j'ai joué avec yFiles by yWorks et j'ai trouvé qu'il avait une assez bonne API.

consultez Blueprints :

Blueprints est une collection d'interfaces, d'implémentations, d'ouplementations et de suites de tests pour le modèle de données du graphique de propriétés. Blueprints est analogue au JDBC, mais pour les bases de données graphiques. Au sein de la pile logicielle open source TinkerPop, Blueprints sert de technologie fondamentale pour:

Pipes : un cadre de flux de données paresseux

Gremlin : un langage de traversée de graphe

Cadres : un mappeur objet-graphique

Furnace : Un package d'algorithmes graphiques

Rexster : un serveur graphique

http://incubator.apache.org/hama/ est un package scientifique distribué sur Hadoop pour des données massives de matrice et de graphique.

JDSL (Data Structures Library en Java) devrait être assez bon si vous êtes dans les algorithmes de graphes - http://www.cs.brown.edu/cgc/jdsl/

Pour la visualisation, notre groupe a eu un certain succès avec prefuse . Nous l'avons étendu pour gérer les plaques de sol architecturales et les diagrammes à bulles, et il ne s'est pas trop plaint. Ils ont également une nouvelle boîte à outils Flex appelée Flare qui utilise une API très similaire.

MISE À JOUR: Je devrais être d'accord avec le commentaire, nous avons fini par écrire beaucoup de fonctionnalités personnalisées / contourner les limitations de préfusage. Je ne peux pas dire que partir de zéro aurait été mieux, car nous avons pu démontrer les progrès réalisés dès le premier jour en utilisant prefuse. D'un autre côté, si nous faisions une deuxième implémentation de la même chose, je pourrais sauter le préfusage car nous comprendrions beaucoup mieux les exigences.

Essayez Annas, c'est un ensemble de graphiques open source facile à maîtriser

http://annas.googlecode.com

Il est également bon d'être convaincu qu'un graphique peut être représenté aussi simplement que:

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

et implémentez vous-même la plupart des algorithmes que vous trouvez intéressants. Si vous tombez sur cette question au milieu d'une session de pratique / apprentissage sur les graphiques, c'est la meilleure bibliothèque à considérer. ;)

Vous pouvez également préférer la matrice d'adjacence pour les algorithmes les plus courants:

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

ou une matrice pour certaines opérations:

class DenseGraph {
  int[] nodeValues;
  int[][] edges;     
}

Je ne sais pas si je l'appellerais prêt pour la production, mais il y a jGABL .

Si vous avez besoin de performances, vous pouvez jeter un œil à Grph. La bibliothèque est développée à l'Université de France et au CNRS / Inria.

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

Le projet est actif et un support réactif est fourni!

Des implémentations d'algorithmes de graphes pédagogiques en java peuvent être trouvées ici (par le prof. Sedgewick et al.): Http://algs4.cs.princeton.edu/code/

Je leur ai été présenté lors de ces cours exceptionnels d'algorithme sur coursera (également enseignés par le professeur Sedgewick):

https://www.coursera.org/course/algs4partI

https://www.coursera.org/course/algs4partII

Si vous recherchez en fait des bibliothèques de graphiques et non des bibliothèques de graphiques de nœuds / bords, je suggérerais de faire des folies sur la bibliothèque de graphiques Big Faceless ( BFG ). Il est beaucoup plus facile à utiliser que JFreeChart, est plus joli, fonctionne plus rapidement, a plus d'options de sortie, vraiment aucune comparaison.

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

Fournit un logiciel puissant pour travailler avec des graphiques (directs ou indirects). Génère également du code Graphivz, vous pouvez voir des représentations graphiques. Vous pouvez mettre vos propres algorithmes de code dans pakage, par exemple: le code de retour arrière. Le paquet fournit quelques algorithmes: Dijkstra, coût de chemin minimun de retour en arrière, etc.