Хорошая библиотека алгоритмов графа Java?

У кого-нибудь был хороший опыт работы с любыми библиотеками Java для алгоритмов Graph. Я пробовал JGraph и нашел это в порядке, и в google есть много разных. Есть ли люди, которые действительно успешно используют производственный код или рекомендуют?

Чтобы уточнить, я не ищу библиотеку, которая создает графики/диаграммы, я ищу тот, который помогает с алгоритмами Графа, например, минимальное связующее дерево, алгоритм Крускала Узлы, Края и т.д. В идеале один с некоторым хорошим алгоритмы/структуры данных в хорошем Java OO API.

Ответы

Ответ 1

Если вы использовали JGraph, вы должны попробовать JGraphT, который предназначен для алгоритмов. Одна из его особенностей - визуализация с использованием библиотеки JGraph. Он по-прежнему развивается, но довольно стабилен. Некоторое время назад я проанализировал сложность алгоритмов JGraphT. Некоторые из них не самые быстрые, но если вы собираетесь реализовать их самостоятельно и должны отображать свой график, тогда это может быть лучший выбор. Мне очень понравилось использовать его API, когда мне быстро пришлось написать приложение, которое работало над графиком и отображало его позже.

Ответ 2

Резюме:

JGraphT, если вас больше интересуют структуры данных и алгоритмы.
JGraph, если ваш основной фокус - визуализация.
Jung, yWorks и BFG - это то, что люди пытались использовать.
Prefuse - нет, так как нужно переписать большую часть его.
Google Guava, если вам нужны только хорошие структуры данных.
График Apache Commons. В настоящее время бездействует, но обеспечивает реализацию для многих алгоритмов. См. https://issues.apache.org/jira/browse/SANDBOX-458 для списка реализованных алгоритмов, также сравниваемых с Jung, GraphT, Prefuse, jBPT

Ответ 3

Откажитесь от JGraphT для очень простой и мощной библиотеки графиков Java, которая довольно хорошо выполнена и, чтобы устранить любую путаницу, отличается чем JGraph. Пример пример кода:

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

Ответ 4

JUNG - хороший вариант для визуализации, а также имеет довольно хороший набор доступных алгоритмов графа, включая несколько разных механизмов случайного построение графа, переделка и т.д. Я также обнаружил, что его довольно легко расширить и адаптировать там, где это необходимо.

Ответ 5

http://neo4j.org/ - это база данных графов, которая содержит множество алгоритмов и масштабов графа лучше, чем большинство библиотек в памяти.

Ответ 6

Apache Commons предлагает commons-graph. В разделе http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/ можно проверить источник. Пример использования API-интерфейса - в SVN. См. https://issues.apache.org/jira/browse/SANDBOX-458 для списка реализованных алгоритмов, также сравниваемых с Jung, GraphT, Prefuse, jBPT

Google Guava, если вам нужны только хорошие структуры данных.

JGraphT - это библиотека графов с множеством реализованных алгоритмов и имеющая (по моему оппину) хорошую графическую модель. Пример Helloworld. Лицензия: LGPL + EPL.

JUNG2 также является лицензированной BSD библиотекой со структурой данных, подобной JGraphT. Он предлагает алгоритмы компоновки, которые в настоящее время отсутствуют в JGraphT. Последняя фиксация - с 2010 года, а пакеты hep.aida.* - это LGPL (через библиотеку colt, которая импортируется JUNG). Это предотвращает использование JUNG в проектах под эгидой ASF и ESF. Возможно, следует использовать виджет github и удалить эту зависимость. Commit f4ca0cd отражает последнее завершение CVS. По-видимому, текущие фиксации устраняют функциональность визуализации. Commit d0fb491c добавляет .gitignore.

Prefuse хранит графики, используя матричную структуру, которая не является эффективной для памяти для разреженных графиков. Лицензия: BSD

Eclipse Zest имеет встроенные алгоритмы компоновки графа, которые могут использоваться независимо от SWT. См. org.eclipse.zest.layouts.algorithms. Используемая структура графа - это Eclipse Draw2d, где Узлы явные объекты и не вводятся через Generics (как это происходит в Apache Commons Graph, JGraphT и JUNG2).

Ответ 7

В университетском проекте я играл с yFiles yWorks и обнаружил, что у него довольно хороший API.

Ответ 8

проверьте Blueprints:

Blueprints представляет собой набор интерфейсов, реализаций, аллюминий и наборов тестов для модели данных графа свойств. Blueprints аналогичен JDBC, но для графических баз данных. В программном стеке с открытым исходным кодом TinkerPop Blueprints служит базовой технологией для:

Pipes: ленивая инфраструктура потока данных

Gremlin: язык обхода графика

Frames: Преобразователь объектов к графам

Furnace: пакет алгоритмов графа

Rexster: сервер графов

Ответ 9

JDSL (библиотека структур данных на Java) должна быть достаточно хорошей, если вы используете алгоритмы графа - http://www.cs.brown.edu/cgc/jdsl/

Ответ 10

http://incubator.apache.org/hama/ - это распределенный научный пакет на Hadoop для массивных матричных и графических данных.

Ответ 11

Для визуализации наша группа имела некоторый успех с prefuse. Мы расширили его, чтобы обрабатывать архитектурные напольные плиты и диаграммы пузырьков, и он не жаловался слишком много. У них есть новый набор инструментов Flex, также называемый Flare, который использует очень похожий API.

UPDATE: Я должен согласиться с комментарием, мы закончили тем, что написали множество пользовательских функций/работали над ограничениями префьюза. Я не могу сказать, что начать с нуля было бы лучше, хотя мы смогли продемонстрировать прогресс с 1-го дня, используя prefuse. С другой стороны, если бы мы выполняли вторую реализацию одного и того же материала, я мог бы пропустить prefuse, так как мы поняли бы требования намного лучше.

Ответ 12

Попробуйте Annas его пакет с открытым исходным кодом, который легко получить с помощью

http://annas.googlecode.com

Ответ 13

Также полезно убедиться, что график можно представить просто так:

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

и реализовать большинство алгоритмов, которые вы найдете интересными сами. Если вы столкнулись с этим вопросом в середине некоторой практики/обучения на графиках, это лучшая библиотека для рассмотрения.;)

Вы также можете предпочесть матрицу смежности для большинства распространенных алгоритмов:

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

или матрицы для некоторых операций:

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

Ответ 14

Я не знаю, буду ли я называть его готовым к производству, но там jGABL.

Ответ 15

Если вам нужна производительность, вы можете взглянуть на Grph. Библиотека разработана во французском университете и CNRS/Inria.

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

Проект активен, и поддерживается реактивная поддержка!

Ответ 16

Здесь можно найти примеры реализации алгоритма алгоритма в java (проф. Sedgewick и др.): http://algs4.cs.princeton.edu/code/

Я познакомился с ними, посещая эти курсы с исключительным алгоритмом на курсах (также преподавал проф. Sedgewick):

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

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

Ответ 17

Если вы на самом деле ищете библиотеки диаграмм, а не для библиотек Node/Edge Graph, я бы предложил splurging в библиотеке Big Faceless Graph (BFG). Это проще в использовании, чем JFreeChart, выглядит лучше, работает быстрее, имеет больше возможностей вывода, на самом деле никакого сравнения.

Ответ 18

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

Обеспечивает мощное программное обеспечение для работы с графиками (прямое или непрямое). Также генерирует код Graphivz, вы можете видеть графические представления. Вы можете поместить свои собственные алгоритмы кода в pakage, например: код возврата. Пакет предоставляет некоторые алгоритмы: Dijkstra, стоимость отслеживания минимального пути, ect..