Соединил две библиотеки для отрисовки графов https://github.com/cosmosgl и https://github.com/gravity-ui/graph. cosmos позволяет реализовать силовой алгоритм с помощью GPU, а gravity соединяет на одном холсте canvas и html в зависимости от уровня зума и добавляет виртуализацию.


Библиотеку gravity делают ребята из инфры Яндекса (соседняя служба с моей), мы её используем во всех сервисах инфраструктуры, чтобы отрисовать сложные графы (от CI пайплайнов до схемы балансировки трафика). Это пожалуй лучшая библиотека в своём классе, и кажется единственная, где canvas и html так нативно объединены. В общем, рекомендую (в том числе на замену reactflow).


Силовой алгоритм легко представить, если все ноды графа заменить шариками, а все ребра заменить на пружинки. Тогда силы натяжения и сжатия пружин приведут систему в состояние с минимальной энергией (точнее будут стремится к этому на бесконечном количестве итераций и при отсутствии осциляторов, для этого предусмотрено затухание сил). Если задать изначально узлам графа случайное положение, то за несколько итераций силовой алгоритм его "распутает" на плоскости, и количество пересечений ребер будет меньше.


Несмотря на то, что у меня есть опыт оптимизации силового алгоритма на CPU (мутабельность, нормализация, массивы для попадания в L кэши и тд), не хотелось писать его снова, тем более что есть cosmos.gl. Так что я сделал "золотой костыль", а именно невидимый div элемент, куда срендерил граф космоса и считал оттуда координаты для нод, после чего передал координаты в гравити.


До 1000 нод всё вообще летает. Да и до 10 тысяч. Потом начинаются проблемы с отрисовкой длинных ребер, поэтому их можно скрывать по умолчанию. Но у меня пока таких больших графов нет.


Всё это я делаю в рамках своего пет проекта по преобразованию графов. Самый близкий аналог это физический проект Стивена Вольфрама с его системой перезаписи гиперграфов. Прошлые посты про сервер, который целиком разворачивается из proto файлов, тоже про этот проект.

Вся наша жизнь — граф...