Я пытаюсь нарисовать ориентированный ациклический граф, используя d3.js. При поиске макета я наткнулся на Dagre, но, похоже, он менее полезен, так как я не хочу использовать DOT-код в любом месте, Если кто-нибудь знает о чистом решении Javascript для этого или плагина/пользовательского макета для DAG, пожалуйста, дайте мне знать. Спасибо заранее.
Направленный ациклический граф с использованием d3.js без DOT
Ответ 1
Дагр автор здесь. Dagre не содержит никакого кода graphviz - это чистый JavaScript. Однако он основан на аналогичных методах компоновки; оба они основаны на методах из бумаги Сугиямы.
Здесь вы можете найти несколько примеров дагера:
http://cpettitt.github.io/project/dagre-d3/latest/demo/interactive-demo.html http://cpettitt.github.io/project/dagre-d3/latest/demo/sentence-tokenization.html http://cpettitt.github.io/project/dagre-d3/latest/demo/tcp-state-diagram.html
Минифицированный источник можно найти здесь: http://cpettitt.github.io/project/dagre-d3/latest/dagre-d3.min.js. Он работает примерно в 44K.
Ответ 2
Оказание ориентированных ациклических графов (и на самом деле выделение свойства направленности) является областью Sugiyama алгоритмов компоновки.
В основном они назначают слои (через топологическую сортировку) узлам, а затем вычисляют последовательность для узлов в слоях. Сначала с помощью простой эвристики для обратного цикла это хорошо работает и для циклических графиков. Graphviz DOT имеет реализацию этого макета под названием dot, который также является именем используемого формата файла, поэтому иногда возникает путаница когда упоминается DOT.
Конечно, есть и другие реализации алгоритма, даже кросс-скомпилированная версия Javascript точки доступна. Вероятно, наиболее полнофункциональное решение, доступное для Javascript, представляет собой коммерческую реализацию алгоритма в библиотеке yFiles. Поэтому, если это связано с коммерческим сценарием, вы можете взглянуть на соответствующую живую демонстрацию. Обратите внимание, что хотя yFiles имеет собственную реализацию рендеринга и редактора, вы все равно можете подключить код к d3.js, поскольку алгоритмы компоновки могут использоваться как автономные реализации, чтобы "просто" вычислить координаты узлов, граничные точки соединения, изгибы и метки. Эта конкретная реализация поддерживает большое количество дополнительных ограничений, таких как "Ограничения портов" (чтобы ограничить направление исходящих и входящих ребер, а также их точное местоположение в узлах), иерархически сгруппированные узлы (где каждый node может иметь parent node и родительский node "содержит" все его дочерние узлы), ограничения уровня и последовательности, ограничения маркировки границ, различные стили маршрутизации границ, маршрутизацию шины и многое другое.
Раскрытие информации: я работаю в компании, которая создает указанную библиотеку, однако на SO я не представляю своего работодателя.