Библиотека SimpleGraph4J для работы с графами в Java

Android Статьи Браузерные игры Программы О сайте

Для одной исследовательской задачи потребовалось находить кратчайший путь в большом ориентированном графе, состоящим из нескольких миллионов рёбер. Основная программа была написана на Java, по этому начал искать библиотеки для этой платформы. Просмотрев несколько из них, в начале 2020 года не нашёл подходящих: требовалась простая, быстрая и чтобы весь граф помещался на одном компьюетре без лишнего потребления памяти. Так я сделал простую, быструю и компактную реализацию графа на Java.

Сейчас решил поделиться с Вами этой программой, оформив её ввиде библиотеки: https://github.com/playerO1/simplegraph4j. Когда выкладывал в июне 2021 года первую версию на github, ещё не придумал название. Сначало назвал Simplegraph, но оказалось с таким названием сотни проектов на github. Потом переименова в simplegraph4j, такого названия не было на github, оно показывает, что это библиотека для Java™. Составил подробное описание проекта в README.MD.

Если вы используете Java, вам нужно просто найти путь в большом (до миллиарда рёбер) ориентированном графе, расстояние у рёбер в формате double и у вас есть только один персональный компьютер (не суперкомпьютерный кластер) - тогда можете использовать мою библиотеку. Если вам нужны дополнительные вычислительные алгоритмы для графа, большая универсальность, распределённые вычисления — тогда сперва изучите другие библиотеки.

История создания библиотеки.

Сначала попробовал Hipster4j - достаточно простой, но тормозил абстрактный конструктор графа и граф потреблял много оперативной памяти.

Потом понял — надо использовать самые простые PoJo объекты, чтобы экономить память. Чем проще — тем мнеьше памяти. Взял с сайта stackowerflow.com пример реализованного на Java алгоритма Дейкстры (англ. Djkstra) поиска в графе. В своей библитеке назвал это SimpleGraph. Тогда это была не библиотека а java-пакет (папка) с несколькими классами.

Но немного не хватало оперативной памяти — тогда переписал хранение связей (рёбер) на примитивные типы (в языке Java есть объекты и "низкоуровенвые" примитивы), используя trove4j. Это позволило использовать от 12 байт на каждое ребро. Скорость работы графа была хорошая, а расход памяти сократился в разы. В библитеки назвал это PrimitiveGraph (от особенности языка программирования java: primitive type). Возможно эта реализация самая близкая к C++ по характеристикам. Этим моя библиотека выгодно отличается от других высокоуровневых библиотек работы с графами в Java.

В некоторых экспериментах всё равно нехватало оперативной памяти для графа. Тогда решил сделать следующую реализацию — на жёстком диске (на файлах). Так, удалось за час найти путь в графе из ста тысяч вершин и миллиарда рёбер. В библитеке назвал это FileGraph.

Итог

Существует очень много маленьких библиотек, написанных на разных языках программирования для работы компьютерных программ с графами. Только для Java я нашёл уже больше 10. Можете написать свою, но лучше сначало поискать готовую.


Android Статьи Браузерные игры Программы О сайте
	Для одной исследовательской задачи потребовалось находить кратчайший путь в большом ориентированном графе, состоящим из нескольких миллионов рёбер. Основная программа была написана на Java, по этому начал искать библиотеки для этой платформы. Просмотрев несколько из них, в начале 2020 года не нашёл подходящих: требовалась простая, быстрая и чтобы весь граф помещался на одном компьюетре без лишнего потребления памяти. Так я сделал простую, быструю и компактную реализацию графа на Java. Сейчас решил поделиться с Вами этой программой, оформив её ввиде библиотеки: https://github.com/playerO1/simplegraph4j. Когда выкладывал в июне 2021 года первую версию на github, ещё не придумал название. Сначало назвал Simplegraph, но оказалось с таким названием сотни проектов на github. Потом переименова в simplegraph4j, такого названия не было на github, оно показывает, что это библиотека для Java™. Составил подробное описание проекта в README.MD. Если вы используете Java, вам нужно просто найти путь в большом (до миллиарда рёбер) ориентированном графе, расстояние у рёбер в формате double и у вас есть только один персональный компьютер (не суперкомпьютерный кластер) - тогда можете использовать мою библиотеку. Если вам нужны дополнительные вычислительные алгоритмы для графа, большая универсальность, распределённые вычисления — тогда сперва изучите другие библиотеки. История создания библиотеки. Сначала попробовал Hipster4j - достаточно простой, но тормозил абстрактный конструктор графа и граф потреблял много оперативной памяти. Потом понял — надо использовать самые простые PoJo объекты, чтобы экономить память. Чем проще — тем мнеьше памяти. Взял с сайта stackowerflow.com пример реализованного на Java алгоритма Дейкстры (англ. Djkstra) поиска в графе. В своей библитеке назвал это SimpleGraph. Тогда это была не библиотека а java-пакет (папка) с несколькими классами. Но немного не хватало оперативной памяти — тогда переписал хранение связей (рёбер) на примитивные типы (в языке Java есть объекты и "низкоуровенвые" примитивы), используя trove4j. Это позволило использовать от 12 байт на каждое ребро. Скорость работы графа была хорошая, а расход памяти сократился в разы. В библитеки назвал это PrimitiveGraph (от особенности языка программирования java: primitive type). Возможно эта реализация самая близкая к C++ по характеристикам. Этим моя библиотека выгодно отличается от других высокоуровневых библиотек работы с графами в Java. В некоторых экспериментах всё равно нехватало оперативной памяти для графа. Тогда решил сделать следующую реализацию — на жёстком диске (на файлах). Так, удалось за час найти путь в графе из ста тысяч вершин и миллиарда рёбер. В библитеке назвал это FileGraph. Итог Существует очень много маленьких библиотек, написанных на разных языках программирования для работы компьютерных программ с графами. Только для Java я нашёл уже больше 10. Можете написать свою, но лучше сначало поискать готовую.
	© www.AlexeyK.com, 2021