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

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

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

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

Резюме:

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

Проверьте 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);

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

Apache Commons предлагает общий граф . Под 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 fork и удалить эту зависимость. Commit f4ca0cd отражает последний коммит CVS. Текущие коммиты, кажется, удаляют функциональность визуализации. Commit d0fb491c добавляет .gitignore.

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

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

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

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

проверить чертежи :

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

Трубы : ленивый, структура потока данных

Гремлин : язык обхода графов

Кадры : отображение объекта на граф

Печь : пакет алгоритмов графа

Рексстер : граф-сервер

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

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

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

ОБНОВЛЕНИЕ: я должен был бы согласиться с комментарием, мы закончили тем, что написали много пользовательской функциональности / обойти ограничения префузии. Я не могу сказать, что начинать с нуля было бы лучше, хотя мы смогли продемонстрировать прогресс с первого дня, используя prefuse. С другой стороны, если бы мы делали вторую реализацию того же самого материала, я мог бы пропустить префузу, так как мы бы лучше поняли требования.

Попробуйте Annas - это графический пакет с открытым исходным кодом, с которым легко разобраться

http://annas.googlecode.com

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

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

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

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

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

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

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

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

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

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

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

Реализации алгоритма учебного графа в Java могут быть найдены здесь (проф. Седжвик и др.): Http://algs4.cs.princeton.edu/code/

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

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

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

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

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

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