Готовые инструменты, да ещё open-source, — это, конечно, здорово. Но реальность обычно такова, что ни один из них не подходит на 100%. Так было и у меня на недавнем проекте. Поэтому пришлось собирать Франкенштейна:
1️⃣ Основная часть — на Guava Graphs
2️⃣ Отдельные
3️⃣ Часто востребованные алгоритмы — (полу)самописные
Поясню такой выбор.
1️⃣ Guava Graphs оказалась хороша по трём причинам:
— максимально человеческий API: интуитивно понятный, почти без неожиданностей, хорошо документирован;
— гибкость построения графов: можно указать что надо, а что нет, и не "переплачивать" за ненужные фичи;
— стандартный набор прелестей: большое сообщество, много примеров, регулярные обновления.
2️⃣ Без JGraphT не удалось обойтись из-за того, что:
— нужно уметь экспортировать граф в другие форматы (GraphVizDot, GEXF) для отладки и верификации (см. приложенный скринкаст);
— нужно исполнять нетривиальные алгоритмы, которых нет в Guava, например, выявлять путь образования циклов.
В принципе, JGraphT покрывает и функционал Guava, поэтому можно было обойтись только им. Но помимо всяких полусубъективных факторов (типа удобства API и полноты документации) я не стал так делать потому, что JGraphT расценивает ребра графа как полноценные его сущности и потому создаёт в памяти объект под каждое ребро. А в Guava есть возможность этого не делать и выражать ребра атрибутами вершин 🔖
В нашем случае рёбра отражают однотипные отношения между ячейками таблиц, поэтому не нуждаются ни в лейблах, ни в других свойствах, а значит, не обязаны быть объектами, и это здорово экономит память. Судите сами — сейчас на одном из серверов заказчика расклад по графу такой:
• 516К вершин (ячеек)
• 1,1М рёбер (связей между ячейками)
• 500 Мб занимает граф в памяти 🪙
Согласитесь, это уже не мало. А если бы мы взяли JGraphT, и на каждое ребро создавали бы по объекту в куче, цифры были бы куда более жуткими... 🙈
3️⃣ Собственные алгоритмы потребовались в тех местах, где Guava ничего не предлагает, а конвертировать граф в формат JGraphT неоправданно дорого. Пример такого места — топологическая сортировка, которая нужна при каждом вычислении зависимых ячеек или при полном пересчёте всей таблицы 🔗
Изначально я взял для этого готовый алгоритм с GitHub. Он работал чётко, но выдаваемый им результат можно было исполнять только в один поток, а в наших масштабах этого оказалось недостаточно: таблица на 16,5К ячеек с формулами обсчитывалась 51 секунду. Тогда пришлось менять его на самописный алгоритм, пригодный для исполнения на множестве ядер 🪵
Конечно, слово самописный тут требует кавычек, ибо в 2026 году вряд ли имеет смысл писать такие вещи с нуля. Вместо этого основа реализации создавалась в обнимку с ИИ, а потом дорабатывалась напильником под (порой суровые) реалии целевого проекта 🪚
Заодно с этой доработкой открылись
—
Не скажу, что строение этого Франкенштейна меня полностью устраивает и не подлежит пересмотру. Вопросики к нему есть. В частности, одна строчка в
build.gradle.kts, добавившая зависимость от JGraphT, увеличила размер финального артефакта приложения на 5+ Мб. Стоило ли оно того — вопрос ещё открытый... 🤔P.S. Приложенный видосик — скринкаст из программы Gephi, о которой я рассказывал в Полке около года назад. На нём запечатлён "игрушечный" граф на 11К ячеек, полученный экспортом (через JGraphT) из нашего приложения не под нагрузкой. Он вам что-нибудь напоминает? 😉
P.P.S. Если вам интересно подробнее почитать про реализацию топологической сортировки, поставьте под этим постом "🤓".