Хорошая библиотека алгоритмов графов Java?
Кто-нибудь имел хороший опыт работы с любыми библиотеками Java для алгоритмов Graph. Я попробовал JGraph и нашел, что все в порядке, и в Google есть много разных. Есть ли что-то, что люди на самом деле успешно используют в производственном коде или рекомендуют?
Чтобы уточнить, я не ищу библиотеку, которая производит графики / диаграммы, я ищу библиотеку, которая помогает с алгоритмами Графа, например, минимальное остовное дерево, узлы алгоритма Крускала, края и т. Д. В идеале одна с хорошими алгоритмами / данными структуры в хорошем Java OO API.
18 ответов
Если вы использовали 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 служит основной технологией для:
Трубы: ленивый, структура потока данных
Гремлин: язык обхода графов
Кадры: отображение объекта на граф
Печь: пакет алгоритмов графа
Рексстер: сервер графов
JDSL (библиотека структур данных в Java) должна быть достаточно хороша, если вы знакомы с алгоритмами графов - http://www.cs.brown.edu/cgc/jdsl/
http://incubator.apache.org/hama/ - это распределенный научный пакет по Hadoop для массивных данных матриц и графиков.
Для визуализации наша группа имела некоторый успех с prefuse. Мы расширили его для работы с архитектурными плитами и пузырьковыми диаграммами, и он не слишком жаловался. У них также есть новый инструментарий Flex, называемый Flare, который использует очень похожий API.
ОБНОВЛЕНИЕ: Я должен был бы согласиться с комментарием, мы закончили тем, что написали много пользовательских функций / обходили ограничения префузии. Я не могу сказать, что начинать с нуля было бы лучше, хотя мы смогли продемонстрировать прогресс с первого дня, используя prefuse. С другой стороны, если бы мы делали вторую реализацию того же самого материала, я мог бы пропустить префузу, так как мы поняли бы требования намного лучше.
Также хорошо убедиться, что график может быть представлен так же просто, как:
class Node {
int value;
List<Node> adj;
}
и реализовать большинство алгоритмов, которые вы находите интересными для себя. Если вы попадаете на этот вопрос в середине какой-то учебной / учебной сессии на графиках, это лучшее, что стоит рассмотреть.;)
Вы также можете предпочесть матрицу смежности для большинства распространенных алгоритмов:
class SparseGraph {
int[] nodeValues;
List<Integer>[] edges;
}
или матрица для некоторых операций:
class DenseGraph {
int[] nodeValues;
int[][] edges;
}
Попробуйте Annas - это графический пакет с открытым исходным кодом, с которым легко разобраться
Я не знаю, назову ли я его готовым к производству, но есть jGABL.
Если вам нужна производительность, вы можете взглянуть на Grph. Библиотека разработана во французском университете и CNRS / Inria.
http://www.i3s.unice.fr/~hogie/grph/
Проект активен и реактивная поддержка обеспечена!
Реализации алгоритма учебного графа в Java можно найти здесь (проф. Седжвик и др.): http://algs4.cs.princeton.edu/code/
Я познакомился с ними во время посещения этих исключительных курсов по алгоритму на Coursera (также преподаемых профессором Седжвиком):
Если вы на самом деле ищете библиотеки для диаграмм, а не для библиотек Node/Edge Graph, я бы предложил потратить деньги на библиотеку Big Faceless Graph ( BFG). Это намного проще в использовании, чем JFreeChart, выглядит лучше, работает быстрее, имеет больше параметров вывода, на самом деле нет сравнения.
JGraph от http://mmengineer.blogspot.com/2009/10/java-graph-floyd-class.html
Предоставляет мощное программное обеспечение для работы с графиками (прямым или косвенным). Также генерирует код Graphivz, вы можете увидеть графические представления. Вы можете поместить свои собственные алгоритмы кода в пакет, например: код возврата. Пакет предоставляет несколько алгоритмов: Dijkstra, минимальный путь возврата и т. Д.