Алгоритм малой перекрестной перекрестки

Question

Я хотел бы знать, есть ли какой-нибудь пример алгоритма макета минимального пересечения (не на основе силы) для графиков, поэтому я мог бы адаптировать его к d3.js.

Answer 1

Вычисление макета графика, который минимизирует пересечения кромок, является NP-hard, поэтому нет единого алгоритма; существуют разные алгоритмы с различными компромиссами. Ракурс, основанный на силе (Fruchterman–Reingold), является одним из подходов, многоуровневый (Sugiyama) является другим. Существуют также макеты для определенных типов графиков, таких как деревья (Reingold–Tilford) и небольшие миры (van Ham–van Wijk). Ограниченный макет, такой как Dig-CoLa (Dwyer–Koren), является еще одним классом алгоритма.

Если вам нужен алгоритм, который специально стремится минимизировать количество пересечений кромок, вы можете использовать simulated annealing. Хотя это в конечном итоге найдет правильный ответ, это может быть довольно медленным.