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

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 autres choses que les gens ont essayé de l'utiliser.
• Prefuse est un non non car il faut réécrire la plupart de celui-ci.
• Google Goyava si vous avez besoin de bonnes structures de données seulement.
• Graphe Apache Commons . Actuellement en sommeil, mais fournit des implémentations pour de nombreux algorithmes. Voir https://issues.apache.org/jira/browse/SANDBOX-458 pour une liste d'algorithmes implémentés, également comparée à Jung, GraphT, Prefuse, jBPT

Consultez JGraphT pour une bibliothèque de graphiques Java très simple et puissante qui est assez bien faite et, pour dissiper toute confusion, est différent de JGraph . Certains exemple 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 graphes disponibles, y compris plusieurs mécanismes différents pour la création aléatoire de graphes, le recâblage, etc. J'ai également trouvé qu'il était généralement assez facile de l'étendre et de l'adapter si nécessaire.

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

Google Goyava si vous avez seulement besoin de bonnes structures de données.

JGraphT est une bibliothèque de graphes avec Algorithmes implémentés et ayant (à mon avis) un bon modèle de graphique. Exemple 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 layouting, qui sont actuellement manquants dans JGraphT. Le commit le plus récent date de 2010 et les paquets 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 la parapluie d'ASF et du FSE. Peut-être que l'on devrait utiliser le fork github et supprimer cette dépendance. Commit f4ca0cd met en miroir le dernier commit CVS. Les commits actuels semblent supprimer la fonctionnalité de visualisation. Commettre d0fb491c ajoute un .gitignore.

Prefuse stocke les graphiques en utilisant 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 mise en page de graphes, qui peuvent être utilisés indépendamment de SWT. Voir org.Eclipse.zeste.disposition.algorithmes . La structure de graphe utilisée est celle de 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 graphes qui contient de nombreux algorithmes de graphes et évolue mieux que la plupart des bibliothèques en mémoire.

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

Découvrez Plans:

Blueprints est une collection d'interfaces, d'implémentations, d'ouplementations et de suites de tests pour le modèle de données de graphe de propriétés. Blueprints est analogue au JDBC, mais pour les bases de données de graphes. Au sein de la pile de logiciels open source TinkerPop, Blueprints sert de technologie de base 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 paquet d'algorithmes de graphe

Rexster: Un graphe serveur

Http://incubator.apache.org/hama / est un paquet scientifique distribué sur Hadoop pour les données matricielles et graphiques massives.

JDSL (Bibliothèque de structures de données en Java) devrait être assez bon si vous aimez les algorithmes de graphe - 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 planchers architecturaux et les diagrammes de bulles, et cela ne s'est pas trop plaint. Ils ont aussi 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/travailler autour des limitations de prefuse. Je ne peux pas dire que partir de zéro aurait été mieux que nous avons pu démontrer les progrès du jour 1 en utilisant prefuse. D'un autre côté, si nous faisions une deuxième implémentation de la même chose, je pourrais ignorer prefuse car nous comprendrions beaucoup mieux les exigences.

Essayez Annas c'est un package graphique open source qui est facile à gérer

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 la plupart des algorithmes que vous trouvez intéressants par vous-même. 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 oeil à Grph. La bibliothèque est développée au sein de l'Université française et du CNRS/Inria.

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

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

Les implémentations d'algorithmes de graphe d'instruction en java peuvent être trouvées ici (par prof. Sedgewick et al.): http://algs4.cs.princeton.edu/code/

Je leur ai été présenté en assistant à ces cours d'algorithme exceptionnels sur coursera (également enseigné par le prof. Sedgewick):

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

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

Si vous recherchez réellement des bibliothèques de graphiques et non des bibliothèques de graphes Node/Edge, je suggérerais de faire des folies sur une grande bibliothèque de graphes sans visage ( BFG). Il est beaucoup plus facile à utiliser que JFreeChart, semble plus agréable, fonctionne plus vite, a plus d'options de sortie, vraiment pas de comparaison.

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

Fournit un logiciel puissant pour travailler avec des graphiques (directs ou non). 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: backtracking code. Le paquet fournit quelques algorithmes: Dijkstra, retour en arrière minimun chemin coût, ect..